Проблема остановки машины Тьюринга

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

Если машина Т, запущенная в начальной конфигурации q_ia_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, и потому она самоприменима. Получили противоречие, следовательно проблема самоприменимости алгоритмически неразрешима, что и требовалось доказать.

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

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

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

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

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

• а) Отсутствие общего метода решения задачи
• б) Информационная неопределенность задачи
• в) Логическая неразрешимость (в смысле теоремы Гёделя о неполноте)