Чтобы показать, как это может быть реализовано, нам потребуется какая-нибудь система нумерации машин Тьюринга. Рассмотрим список инструкций, определяющих произвольную машину Тьюринга, например, одну из описанных выше. Мы должны в соответствии с некоторыми четкими правилами представить эти инструкции в виде последовательностей нулей и единиц. Это можно сделать, например, с помощью процедуры "сокращения", которую мы использовали ранее. Тогда, если мы закодируем символы R, L, STOP, "стрелка" (→) и "запятая", скажем, числами 2, 3, 4, 5 и 6 соответственно, то мы сможем записать их в виде "сокращений" 110, 1110, 11110, 111110 и 1111110. Цифры 0 и 1, кодируемые, соответственно, как 0 и 10, могут быть использованы для записи строк этих символов, входящих в таблицу действий машины Тьюринга. Нам не нужны различные обозначения для "жирных" цифр 0 и 1 и для остальных цифр в таблице, поскольку расположение "жирных" цифр в конце двоичного кода является достаточным отличительным признаком. При этом 1101, например, будет читаться как двоичное число 1101, представляемое на ленте последовательностью 1010010. в частности, 00 будет читаться как 00, что без всякой двусмысленности можно закодировать как 0 или вовсе опустить. Можно существенно сэкономить, если не кодировать "стрелки" и непосредственно предшествующие им символы, а воспользоваться цифровым упорядочением команд, позволяющим определить, какими должны быть эти символы. Правда, для этого надо убедиться в отсутствии "дырок" в получившемся порядке и добавить, где требуется, "немые" команды. (Например, машина Тьюринга XN +1 не имеет команды, соответствующей коду 1100, поскольку такая комбинация в ходе ее работы никогда не встречается. Следовательно, мы должны ввести в список команд немую команду, скажем 1100 → 00R, которая не вызовет каких бы то ни было изменений в работе машины. Сходным образом мы должны добавить немую команду 101 → 00R в список команд машины XN х 2.) Без таких "немых" команд кодирование последующих команд было бы нарушено. Как можно видеть, на самом деле мы не нуждаемся и в запятой в конце каждой команды, поскольку символов L и R вполне достаточно для отделения команд друг от друга. Поэтому мы просто будем использовать такую систему кодирования:
0 для 0 или 0,
10 для 1 или 1,
110 для R,
1110 для L,
11110 для STOP.
В качестве примера выпишем команды для машины Тьюринга XN +1 (с дополнительной немой командой 1100 → 00R). Опуская стрелки, цифры, непосредственно предшествующие им, и запятые, получим
Мы можем улучшить полученный результат, если опустим все 00 и заменим каждые 01 просто единицей в соответствии с тем, что говорилось ранее. Тогда мы получим строку символов
которая на ленте записывается как последовательность
Есть еще два способа немного сэкономить. Во-первых, всегда можно удалить код 110 в начале записи (вместе с бесконечным участком пустой ленты, предшествующим этому коду). Он обозначает последовательность 00R, соответствующую начальной команде 00 → 00R, которую я до сих пор неявно считал общей для всех машин Тьюринга, поскольку она необходима для того, чтобы устройство, начав работу в произвольной точке слева от начала записи на ленте, могло перемещаться вправо до тех пор, пока не встретит первую непустую клетку. Во-вторых, точно так же всегда можно удалить код 110 (и неявную бесконечную последовательность нулей, которая, по предположению, следует за ним) в конце записи, поскольку этой кодовой последовательностью должно заканчиваться описание любой машины Тьюринга (во всех случаях список команд заканчивается командой R, L или STOP). Получающееся двоичное число - это номер машины Тьюринга, который для XN + 1 будет выглядеть так:
В обычной десятичной записи этот номер равен
450813704461563958982113775643437908.
Иногда машину с номером n мы, не вполне точно, будем называть n-й машиной Тьюринга и обозначать ее Tn . В этом случае 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.
Наверное, принимая во внимание величины этих номеров, уже не вызовет удивления тот факт, что абсолютное большинство натуральных чисел не соответствует ни одной рабочей машине Тьюринга. Приведем перечень первых тринадцати машин Тьюринга в соответствии с принятой нумерацией: