Самоприменимость МТ

Рассмотрим машины Тьюринга, внешние алфавиты которых содержат символы 0,1 (наряду с другими). Для каждой машины Тьюринга Т построим Код(Т), который является (0,1)-словом, и запустим машину Т в начальной конфигурации q₁Код(Т). Если машина Т останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой. Существуют как самоприменимые, так и несамоприменимые машины Тьюринга. Например, несамоприменимой будет машина Т1, у которой все команды имеют вид q_ia_j→q_ia_jС (в правых частях команд нет заключительного состояния), самоприменимой будет машина Т1, у которой все команды имеют вид q_ia_j→q₀a_jE (в правых частях всех команд имеется заключительное состояние). Проблема самоприменимости состоит в том, чтобы по любой машине Тьюринга Т определить, является ли она самоприменимой или нет. Будем считать, что машина Тьюринга М решает проблему самоприменимости, если для любой машины Т начальную конфигурацию q₁Код(Т) она переводит в q₀1,

если машина Т самоприменима, и в q₀0, если машина Т несамоприменима.

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

Доказательство (от противного).

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

q₀1→q₀1С (1)

q₀0→q₀* 0С (2).

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

Пусть Т – произвольная машина. Если Т – самоприменима, то начальная конфигурация q₁Код(Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q₀1, далее применяется команда (1), и машина М₀ никогда не остановится. Если Т – несамоприменима, то начальная конфигурация q₁Код(Т) перейдет с помощью команд машины М через конечное число шагов в конфигурацию q₀0, далее применяется команда (2), и машина М₀ остановится.

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

Теперь рассмотрим Код(М₀) и применим машину М₀ к начальной конфигурации q₁Код(М₀). Сама машина М₀ является либо самоприменимой, либо несамоприменимой. Если М₀ самоприменима, то по доказанному она никогда не остановится, начав с q₁Код(М₀), и потому она несамоприменима. Если М₀ несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q₁Код(М₀), и потому она самоприменима. Получили противоречие, которое является следствием допущения существования машины М₀, решающей проблему самоприменимости, что и требовалось доказать.

Дата добавления: 2014-01-15