Задача разрешимости

Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров^[1].

Например, проблема «даны два числа: ${\displaystyle x}$ и ${\displaystyle y}$; делится ли ${\displaystyle x}$ на ${\displaystyle y}$ без остатка?» является проблемой разрешимости. Ответ может быть дан либо «да», либо «нет» и зависит от значений ${\displaystyle x}$ и ${\displaystyle y}$. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы из примера выше должна определять совокупность действий, которые следует предпринять для проверки делимости нацело ${\displaystyle x}$ на ${\displaystyle y}$ для данных чисел. Один из таких алгоритмов — деление столбиком — изучается в начальной школе. Остаток, равный нулю, означает ответ «да», в противном случае — «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.

Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы ответом к задаче было бы «да» или «нет».

Исследования в области теории рекурсии часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи.

См. также

• Проблема разрешения
• Алгоритмическая разрешимость

Примечания

1. Том Стюарт. Теория вычислений для программистов. — Litres, 2015-06-24. — С. 329. — 386 с. — ISBN 9785457831230.

Литература

• Мальцев А. И., Алгоритмы и рекурсивные функции, Наука, 1986.
• Daniel Kroening & Ofer Strichman, Decision procedures, Springer, ISBN 978-3-540-74104-6
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1