Методы доказательства алгоритмической неразрешимости

Существуют два метода доказательства неразрешимости.

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

Второй, косвенный метод состоит в следующем. Показывается, что разрешимость исследуемой проблемы влечёт разрешимость проблемы, о которой уже известно, что она неразрешима. Метод сведения часто бывает более удобным, чем прямой метод.

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

Пример

Самопримени́мость в теории алгоритмов — свойство алгоритма успешно завершаться на данных, представляющих собой формальную запись этого же алгоритма.

Задача распознавания самоприменимости является алгоритмически неразрешимой и сводится к тому, чтобы найти алгоритм, позволяющий за конечное число шагов по формальной записи некоего алгоритма узнать, является ли он самоприменимым или нет. Хотя эта задача несколько искусственна и не представляет самостоятельного интереса, но часто используется для того, чтобы доказать неразрешимость других, более сложных задач. Общий метод для подобных выводов состоит в том, что из предположения о существовании алгоритма, решающего некую задачу, выводится существование алгоритма, решающего задачу распознавания самоприменимости.