Невозможность создания универсальной машины Тьюринга с одним состоянием

Теперь покажем, что нельзя построить универсальную машину Тьюринга, использующую одну ленту и только одно внутреннее состояние.

Допустим, что такая машина существует. Если записать подходящее «описательное число» конечной длины на куске ленты (оставив прочую часть ленты пустой) и поместить считывающую

головку в соответствующий квадрат, то машина будет вычислять любое вычислимое число и, в частности, вычислимые иррациональные числа, например У 2. Покажем, что это невозможно.

Согласно первоначальному замыслу Тьюринга, при вычислении последовательные знаки (скажем, в двоичном представлении) записываются машиной на определенной последовательности квадратов ленты (например, на четных квадратах, тогда как нечетные предназначаются для промежуточных вычислений). Приводимое ниже доказательство исходит из вычисления У 2 в таком виде, хотя будет ясно, что, изменив доказательство, можно принять во внимание и другие разумные интерпретации «вычисления

Ввиду иррациональности У 2 двоичные знаки его разложения не станут повторяться периодически. Поэтому, если показать для машины с одним состоянием, что или 1) во всех ее квадратах, кроме конечного числа, будет в конце концов записан один и тот же символ, или 2) во всех квадратах, кроме конечного числа, символы будут без конца сменяться, то тем самым будет получен желаемый результат.

Сначала возьмем ленту, пустую и бесконечную в обе стороны от описательного числа для Если считывающая головка приходит на пустой квадрат, то она должна или остановиться здесь на все время, или же передвинуться вправо либо влево. Так как имеется лишь одно состояние, то ее поведение не зависит от предшествовавшего вычисления. В первом случае считывающая головка никогда не отойдет дальше, чем на один квадрат, от описательного числа, и вся лента, кроме конечного отрезка, будет постоянно пуста. Если же головка передвигается влево с некоторого пустого квадрата, то или левая бесконечная часть пустой ленты не участвует в вычислении и поэтому не требует рассмотрения, или, если она участвует в вычислении, считывающая головка с этого времени беспрерывно движется влево, записывая во всех квадратах, ранее пустых, один и тот же символ. Следовательно, лента становится одинаковой всюду слева от некоторого конечного отрезка и пустой справа от него и не может хранить записи числа Аналогичное положение возникает при движении головки вправо от первоначально пустого квадрата. Поэтому двусторонне бесконечная лента ничуть не лучше односторонней, и можно из соображений симметрии предположить, что лента односторонне бесконечна вправо от описательного числа.

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

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

Теперь поместим считывающую головку в квадрат описательного числа, являющийся начальным для предполагаемого вычисления Спустя некоторое время считывающая головка, возможно, выйдет из части ленты, где записано описательное число. Возвратим ее в последний квадрат описательного числа. Спустя некоторое время она, возможно, опять выйдет. Продолжим этот процесс до тех пор, пока возможно. Число выходов головки равно или целому числу или Это число назовем числом отражений для данного описания

Если конечно и (может быть то спустя конечное время считывающая головка застрянет в части ленты, где первоначально находилось описательное число. Изменится лишь конечная часть пустой ленты, и машина не вычислит

Если как так и 5 бесконечны, то считывающая головка будет возвращаться неограниченное число раз в часть ленты с описательным числом. Экскурсии в первоначально пустую часть будут или ограничены по длине, или нет. Если они ограничены, то изменится лишь конечная часть пустой ленты, как и в предыдущем случае. Если же нет, то вся лента, кроме конечной части, будет обрабатываться считывающей головкой неограниченное число раз. Так как имеется только одно состояние и алфавит символов конечен, то символ, записываемый в квадрате, который посещается неограниченное число раз, должен или стать постоянным (одним и тем же для всех таких квадратов), или изменяться циклически бесконечное число раз. В первом случае вся первоначально пустая лента становится одинаковой и не может изображать Во втором случае она непрерывно изменяется и не может изображать никакого результата вычисления.

Если то считывающая головка в конце концов уйдет в первоначально пустую часть ленты и там останется. Можно показать, что в этом случае символы в первоначально пустой части становятся, за исключением конечного их числа, одинаковыми. В самом деле, либо головка передвигается вправо из первого пустого квадрата во второй пустой квадрат по меньшей мере раз, либо нет. В последнем случае спустя конечное время считывающая головка остается в бывшем первом пустом квадрате, и вся лента, кроме конечной части, остается пустой. Если же головка уходит вправо раз, то она не вернется в первый квадрат, первоначально пустой, ибо есть число отражений для пустой ленты. В этом первом квадрате будет записан результат действий над пустым квадратом приходах головки слева и приходах справа). Во втором первоначально пустом квадрате в конце, концов будет записан тот же самый постоянный символ, потому что ко второму квадрату применимо такое же рассуждение, как и к первому. Во всех случаях машина работает на той же самой ленте (бесконечном ряде пустых квадратов) и приходит одно и то же число раз справа и соответственно слева. Тем самым все возможные случаи исчерпаны и доказательство завершено.