Ввод — машина Тьюринга и входная строка w .
Проблема — Завершает ли машина Тьюринга вычисление строки w за конечное число шагов? Ответ должен быть либо да, либо нет.
Доказательство. Сначала мы предположим, что такая машина Тьюринга существует для решения этой проблемы, а затем покажем, что она противоречит самой себе. Мы будем называть эту машину Тьюринга остановочной машиной, которая выдает «да» или «нет» за конечное время. Если машина для остановки останавливается за конечное время, вывод будет «да», в противном случае — «нет». Ниже приведена блок-схема машины для остановки.
Теперь мы спроектируем инвертированную стопорную машину (HM) ‘ как —
-
Если H возвращает YES, то цикл навсегда.
-
Если H возвращает NO, тогда остановите.
Если H возвращает YES, то цикл навсегда.
Если H возвращает NO, тогда остановите.
Ниже приводится блок-схема «инвертированная Остановка машины» —
Кроме того, машина (HM) 2, сам ввод которой построен следующим образом:
- Если (HM) 2 останавливается на входе, петля навсегда.
- Остальное, остановка
Здесь у нас есть противоречие. Следовательно, проблема остановки неразрешима .