Есть еще два способа немного сэкономить. Во-первых, всегда можно удалить код 110 в начале записи (вместе с бесконечным участком пустой ленты, предшествующим этому коду). Он обозначает последовательность 0 0R, соответствующую начальной команде 0 0 → 0 0R, которую я до сих пор неявно считал общей для всех машин Тьюринга, поскольку она необходима для того, чтобы устройство, начав работу в произвольной точке слева от начала записи на ленте, могло перемещаться вправо до тех пор, пока не встретит первую непустую клетку. Во-вторых, точно так же всегда можно удалить код 110(и неявную бесконечную последовательность нулей, которая, по предположению, следует за ним) в конце записи, поскольку этой кодовой последовательностью должно заканчиваться описание любой машины Тьюринга (во всех случаях список команд заканчивается командой R, L или STOP ). Получающееся двоичное число— это номер машины Тьюринга, который для XN + 1 будет выглядеть так:
В обычной десятичной записи этот номер равен
450813704461563958982113775643437908.
Иногда машину с номером n мы, не вполне точно, будем называть n- й машиной Тьюринга и обозначать ее T n . В этом случае XN +1 становится
450813704461563958982113775643437908 — й
машиной Тьюринга!
Кажется поразительным факт, что нам надо пробежать так долго вдоль «списка» машин Тьюринга, чтобы найти машину, выполняющую такую тривиальную операцию, как прибавление единицы к натуральному числу (в расширенном двоичном представлении). (Я не думаю, что моя система кодирования была в целом настолько неэффективна, хотя в ней и есть еще возможности для незначительных улучшений.) В действительности, есть машины Тьюринга и с меньшими номерами, которые представляют интерес, например UN +1 с двоичным номером
101011010111101010,
который в десятичной записи превращается всего лишь в 177 642. Значит, особенно тривиальная машина UN +1, которая просто дописывает 1 единицу в конце последовательности единиц, является 177 642- й машиной Тьюринга. Интересно, что «умножение на два» в списке машин Тьюринга попадает где-то между этими двумя машинами, причем и в унарном, и в расширенном двоичном представлении: номер XN х 2 равен 10 389 728 107, а номер UN х 2— 1492 923 420 919 872 026 917 547 669.
Наверное, принимая во внимание величины этих номеров, уже не вызовет удивления тот факт, что абсолютное большинство натуральных чисел не соответствует ни одной рабочей машине Тьюринга. Приведем перечень первых тринадцати машин Тьюринга в соответствии с принятой нумерацией:
Из этих машин T 0 просто перемещается вправо, стирая все, что ей попадается на пути, никогда не останавливаясь и не меняя направления движения. Машина Т 1 выполняет в сущности ту же операцию, но более громоздким путем, отступая на шаг назад каждый раз, когда она стирает очередную единицу на ленте. Так же как и T 0 , машина T 2 двигается вправо, никогда не останавливаясь, но относится к ленте более «почтительно», попросту оставляя всю информацию нетронутой. Эти машины не могут использоваться в качестве машин Тьюринга, поскольку никогда не останавливаются. T 3 — первая в этом списке «правильная» машина: она скромно прекращает действие после того, как изменяет первую (самую левую) единицу на нуль. T 4 сталкивается с серьезной проблемой. Найдя первую единицу на ленте, она переходит во внутреннее состояние, которое нигде не описано, и, следовательно, машина не имеет никаких команд для следующего шага. С той же проблемой сталкиваются T 8, T 9 и T 10 . С T 7 возникают трудности еще более фундаментального характера. Строка нулей и единиц, которой она представляется, включает последовательность из пяти единиц: 110111110. Интерпретации этой последовательности не существует, поэтому T 7 намертво застревает сразу же, как только доходит до первой единицы. (Я буду называть T 7 , равно как и любую другую машину T n , двоичное расширенное представлений которой содержит более четырех единиц, некорректно определенной .) Машины T 5, T 6 и T 12 испытывают те же трудности, что и T 0, T 1, T 2: они просто никогда не останавливаются. Все эти машины — T 0, T 1, T 2, T 5, T 6, T 7, T 8, T 9, T 10 и T 12 — совершенно бесполезные устройства! Только T 3 и T 11 являются функциональными машинами Тьюринга, да и то не слишком интересными. Причем T 11 даже скромнее, чем T 3 : натолкнувшись на первую же единицу, она останавливается и вообще ничего не меняет!