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

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

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

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

См. также

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

Примечания

Литература

• Мальцев А. И. , Алгоритмы и рекурсивные функции , Наука, 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