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

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

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

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

S0

∂ r₁ r₂ … r_m r_m+1 r_{m+2 …} r_n λ λ λ

Рис 1.8. Лента машины Т в выбранной момент времени.

Новая машина M_Tt начинает работу на пустой ленте и работает по следующей программе:

S₁ λ → r₁ R S₂

S₂ λ → r₂ R S₃

…

S_m λ → r_m R S_m+1

S_m+1 λ → x R S_m+2

S_m+2 λ → r_m+2 R S_m+3

_…

S_n λ → r_n L S_х

S_х r_n-1 → r_{n-1 L Sх}

S_х r_n-2 → r_{n-2 L Sх}

_…

S_х r_m+2 → r_m+2 L S_х

S_х х → r_m+1 L S₀

S₀ r_m → далее работа аналогично машине Т на ленте t,

где:

x – некоторая буква, в других случаях не встречающаяся на входной ленте t;

S_{1, …,} S_n, S_х – новые состояния машины M_Tt, которых не было в машине Т.

Т.о. машина M_Tt при запуске на пустой ленте эквивалента машине Т, работающей на ленте t, так как, по сути, машина M_Tt просто печатает копию ленты t на своей ленте, затем выбирает нужную позицию и после этого становится полностью идентичной машине Т. Значит M_Tt и Т - эквивалентные машины.

Предположим, что задача об остановке машины на чистой ленте алгоритмически разрешима, значит ее можно решить и применительно к машине M_Tt, начинающей работу на чистой ленте. Соответственно, такая задача решается и для машины Т на ленте 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) Теорема