Как строка, которая не принадлежит языку ввода, может установить машину Тьюринга в бесконечный цикл?

Question

Как можно установить машину Тьюринга в бесконечный цикл, поместив строку, которая не принадлежит языку ввода, даже если она имеет состояние отклонения?

Answer 1

Рассмотрим TM, который выполняет следующее:

1. Прочитайте кассету с лентой. Если 0, прекратите прием. Если 1, напишите 1, двигайтесь вправо и войдите в состояние 2.
2. Прочитайте кассету с лентой. Если 0, остановить отклонить Если 1, напишите 1, переместитесь влево и войдите в состояние 1.

Эта машина принимает строки 0* + 10*. Он не принимает ничего в 11*, но он будет зацикливаться на такой строке навсегда.