Задача об остановке произвольной машины Тьюринга на пустой ленте алгоритмически неразрешима
Доказательство
Для каждой пары машина-лента (T-t) докажем наличие соответствующей задачи остановки на пустой ленте для некоторой другой машины, предположим MTt. Машина MTt строится непосредственно по описанию T и t, если диаграмму состояний Т дополнить последовательностью новых состояний.
Предположим, что для пары T, t в некоторый момент времени лента выглядит таким образом (рис.1.8):
| S0 |
Рис 1.8. Лента машины Т в выбранной момент времени.
Новая машина MTt начинает работу на пустой ленте и работает по следующей программе:
S1 λ → r1 R S2
S2 λ → r2 R S3
…
Sm λ → rm R Sm+1
Sm+1 λ → x R Sm+2
Sm+2 λ → rm+2 R Sm+3
…
Sn λ → rn L Sх
Sх rn-1 → rn-1 L Sх
Sх rn-2 → rn-2 L Sх
…
Sх rm+2 → rm+2 L Sх
Sх х → rm+1 L S0
S0 rm → далее работа аналогично машине Т на ленте t,
где:
x – некоторая буква, в других случаях не встречающаяся на входной ленте t;
S1, …, Sn, Sх – новые состояния машины MTt, которых не было в машине Т.
Т.о. машина MTt при запуске на пустой ленте эквивалента машине Т, работающей на ленте t, так как, по сути, машина MTt просто печатает копию ленты t на своей ленте, затем выбирает нужную позицию и после этого становится полностью идентичной машине Т. Значит MTt и Т - эквивалентные машины.
Предположим, что задача об остановке машины на чистой ленте алгоритмически разрешима, значит ее можно решить и применительно к машине MTt, начинающей работу на чистой ленте. Соответственно, такая задача решается и для машины Т на ленте t, что есть противоречие с доказанным в Теореме 1.5.(1) утверждением о том, что для произвольной машины Т задача остановки при обработке произвольного слова t алгоритмически неразрешима. Отсюда следует, что задача об остановке машины на чистой ленте алгоритмически неразрешима, Q.E.D.
Т.1.5.(4) Теорема
Задача о печатании данного символа на чистой ленте точно один раз алгоритмически неразрешима.
Доказательство
Без ограничения общности, возьмем знак «0». Итак, машина Тьюринга Т работает на чистой ленте. Преобразуем ее в новую машину Тьюринга D. Если Т не содержит в своем алфавите знака «0», то D просто совпадает с T. Если T имеет этот знак в своем алфавите, то в алфавите машины D знак «0» будет заменен любым знаком, ранее не входящим в алфавит машины. Очевидно, что D остановится тогда, когда остановится Т.
Построим машину Е, которая работает как D вплоть до ее остановки. После этого машина Е печатает «0» и тоже останавливается.
Т.о. получим, что символ «0» печатается точно один раз в том случае, если произвольная машина Т останавливается на чистой ленте. Значит, задача о печатании ровно одного нуля равносильна задаче об остановке машины на чистой ленте. Поскольку задача останова алгоритмически неразрешима, то и задача о печатании символа точно один раз тоже неразрешима, Q.E.D.
Т.1.5.(5)Теорема
Задача о печатании данного символа на чистой ленте бесконечно много раз алгоритмически неразрешима.
Доказательство
Без ограничения общности, возьмем знак «0». Итак, машина Тьюринга Т работает на чистой ленте. Преобразуем ее в новую машину Тьюринга D. Если Т не содержит в своем алфавите знака «0», то D просто совпадает с T. Если T имеет этот знак в своем алфавите, то в алфавите машины D знак «0» будет заменен любым знаком, ранее не входящим в алфавит машины. Очевидно, что D остановится тогда, когда остановится Т.
Построим машину Е, которая работает как D вплоть до ее остановки. После этого машина Е переходит в состояние А и печатает «0» бесконечно много раз (Al ® 0RA).
Т.о. получим, что символ «0» печатается бесконечно много раз в том случае, если произвольная машина Т останавливается на чистой ленте. Значит, задача о печатании бесконечно большого числа нулей равносильна задаче об остановке машины на чистой ленте. Поскольку задача останова алгоритмически неразрешима, то и задача о печатании символа бесконечно много раз тоже не разрешима,Q.E.D.
Т.1.5.(6) Теорема