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

       

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


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

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

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

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

Ясно, что

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

допускает

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



Содержание раздела