Проблема остановки машины Тьюринга

Input - Машина Тьюринга и входная строка w.

Problem - Завершает ли машина Тьюринга вычисление строки wза конечное количество шагов? Ответ должен быть либо да, либо нет.

Proof- Сначала мы предположим, что такая машина Тьюринга существует для решения этой проблемы, а затем покажем, что она противоречит сама себе. Мы будем называть эту машину ТьюрингаHalting machineкоторый дает ответ «да» или «нет» за конечный промежуток времени. Если остановившаяся машина завершает работу за конечный промежуток времени, на выходе будет «да», в противном случае - «нет». Ниже приведена блок-схема останавливающейся машины -

Теперь создадим inverted halting machine (HM)’ как -

• Если H возвращает YES, затем цикл повторяется навсегда.

• Если H возвращает NO, затем останавливается.

Ниже приведена блок-схема «перевернутой остановки машины».

Далее машина (HM)₂ который сам по себе построен следующим образом -

• Если (HM) ₂ останавливается при вводе, цикл будет бесконечным.
• В противном случае остановитесь.

Здесь мы получили противоречие. Следовательно, проблема остановки заключается вundecidable.