Доказательство неразрешимости проблемы остановки

Проблема остановки машины Тьюринга – это проблема построения такого алгоритма, который мог бы определить закончится или нет вычисление по некоторой задаче. Оказывается, что в общем случае такой алгоритм нельзя построить в принципе, то есть невозможно найти алгоритм, позволяющий по произвольной машине Тьюринга Т и произвольной ее начальной конфигурации q _i a _j определить придет ли машина Т в заключительное состояние q ₀, если начнет работу в этой конфигурации.

Если машина Т, запущенная в начальной конфигурации q _i a _j, останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой.

Теорема.

Не существует машины Тьюринга М, решающей проблему самоприменимости, то есть проблема самоприменимости алгоритмически неразрешима.

Доказательство.

Предположим противное, то есть. пусть существует машина Тьюринга Т, решающая проблему самоприместимости в указанном выше смысле. Построим новую машину Т₀, добавив новое состояние q ₀* и объявив его заключительным, а также добавив новые команды для состояния q ₀, которое было заключительным в Т:

q ₀ a ₁→ a ₁С q ₀ (1)

q ₀ a ₂→ a ₂ С q ₀ (2)

…q ₀ a _n→ a _n С q ₀ * (n)

Рассмотрим теперь работу машины T₀.

Пусть M – произвольная машина. Если M – самоприменима, то начальная конфигурация q ₁ a _i перейдет с помощью команд машины T через конечное число шагов в конфигурацию q ₀ a ₁, далее применяется команда (1), и машина T₀ никогда не остановится. Если M – несамоприменима, то начальная конфигурация q ₁ a _i перейдет с помощью команд машины T через конечное число шагов в конфигурацию q ₀ a _n, далее применяется команда (n), и машина T₀ остановится.

Таким образом, машина T₀ применима к кодам несамоприменимых машин Т и неприменима к кодам самоприменимых машин Т.

Теперь применим машину T₀ к начальной конфигурации q ₁ a _i. Сама машина T₀ является либо самоприменимой, либо несамоприменимой. Если T₀ самоприменима, то по доказанному она никогда не остановится, начав с q ₁ a _i, и потому она несамоприменима. Если T₀ несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q ₁ a _j, и потому она самоприменима. Получили противоречие, следовательно проблема самоприменимости алгоритмически неразрешима, что и требовалось доказать.

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

Неразрешимости логики первого порядка

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