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

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

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

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

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