Задача об остановке произвольной машины Тьюринга на пустой ленте алгоритмически неразрешима

Доказательство

Для каждой пары машина-лента (T-t) докажем наличие соответствующей задачи остановки на пустой ленте для некоторой другой машины, предположим MTt. Машина MTt строится непосредственно по описанию T и t, если диаграмму состояний Т дополнить последовательностью новых состояний.

Предположим, что для пары T, t в некоторый момент времени лента выглядит таким образом (рис.1.8):

S0
∂ r1 r2 … rm rm+1 rm+2 … rn λ λ λ

Рис 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) Теорема

Наши рекомендации