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

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

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

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

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

Ясно, что

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

допускает

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

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

---

---