Теория и реализация языков программирования



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


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

Перенумеруем все машины Тьюринга и все возможные входы над алфавитом

\Sigma
. Рассмотрим язык

L1={xi|xi не допускается Ti}

Ясно, что

L_1
не допускается никакой Tm. Допустим, что это не так. Пусть
L_1
допускается Tj . Тогда
x_j \in L_1
тогда и только тогда, когда
x_j
не допускается
T_j
. Но поскольку
T_j

допускает

L_1, x_j \in L_1
тогда и только тогда, когда допускается
T_j
, - противоречие. Так что
L_1
- не является рекурсивно перечислимым множеством.




Содержание  Назад  Вперед