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

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

если машина Т самоприменима, и в q00, если машина Т несамоприменима.

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

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

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

q01→q01С                                                                                            (1)

q00→q0* 0С                                                                                         (2).

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

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

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

 

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

 

Логика - доступно для всех