Новый ум короля: О компьютерах, мышлении и законах физики

Чтобы показать, как это может быть реализовано, нам потребуется какая-нибудь система нумерациимашин Тьюринга. Рассмотрим список инструкций, определяющих произвольную машину Тьюринга, например, одну из описанных выше. Мы должны в соответствии с некоторыми четкими правилами представить эти инструкции в виде последовательностей нулей и единиц. Это можно сделать, например, с помощью процедуры «сокращения», которую мы использовали ранее. Тогда, если мы закодируем символы R, L, STOP, «стрелка» (->) и «запятая», скажем, числами 2, 3, 4, 5 и 6 соответственно, то мы сможем записать их в виде «сокращений» 110, 1110, 11110, 111110 и 1111110. Цифры 0 и 1, кодируемые, соответственно, как 0и 10, могут быть использованы для записи строк этих символов, входящих в таблицу действий машины Тьюринга. Нам не нужны различные обозначения для «жирных» цифр 0и 1и для остальных цифр в таблице, поскольку расположение «жирных» цифр в конце двоичного кода является достаточным отличительным признаком. При этом 110 1, например, будет читаться как двоичное число 1101, представляемое на ленте последовательностью 1010010. в частности, 0 0будет читаться как 00, что без всякой двусмысленности можно закодировать как 0или вовсе опустить. Можно существенно сэкономить, если не кодировать «стрелки» и непосредственно предшествующие им символы, а воспользоваться цифровым упорядочением команд, позволяющим определить, какими должны быть эти символы. Правда, для этого надо убедиться в отсутствии «дырок» в получившемся порядке и добавить, где требуется, «немые» команды. (Например, машина Тьюринга XN +1не имеет команды, соответствующей коду 110 0, поскольку такая комбинация в ходе ее работы никогда не встречается. Следовательно, мы должны ввести в список команд немую команду, скажем 110 0 -> 0 0R, которая не вызовет каких бы то ни было изменений в работе машины. Сходным образом мы должны добавить немую команду 10 1 -> 0 0Rв список команд машины XN х 2.) Без таких «немых» команд кодирование последующих команд было бы нарушено. Как можно видеть, на самом деле мы не нуждаемся и в запятой в конце каждой команды, поскольку символов Lи Rвполне достаточно для отделения команд друг от друга. Поэтому мы просто будем использовать такую систему кодирования:

0для 0 или 0,

10для 1 или 1,

110для R,

1110для L,

11110для STOP.

В качестве примера выпишем команды для машины Тьюринга XN +1(с дополнительной немой командой 110 0 -> 0 0R). Опуская стрелки, цифры, непосредственно предшествующие им, и запятые, получим

Мы можем улучшить полученный результат, если опустим все 0 0и заменим каждые 0 1просто единицей в соответствии с тем, что говорилось ранее. Тогда мы получим строку символов

которая на ленте записывается как последовательность

Есть еще два способа немного сэкономить. Во-первых, всегда можно удалить код 110в начале записи (вместе с бесконечным участком пустой ленты, предшествующим этому коду). Он обозначает последовательность 0 0R, соответствующую начальной команде 0 0 -> 0 0R, которую я до сих пор неявно считал общей для всехмашин Тьюринга, поскольку она необходима для того, чтобы устройство, начав работу в произвольной точке слева от начала записи на ленте, могло перемещаться вправо до тех пор, пока не встретит первую непустую клетку. Во-вторых, точно так же всегда можно удалить код 110(и неявную бесконечную последовательность нулей, которая, по предположению, следует за ним) в конце записи, поскольку этой кодовой последовательностью должно заканчиваться описание любоймашины Тьюринга (во всех случаях список команд заканчивается командой R, Lили STOP). Получающееся двоичное число— это номермашины Тьюринга, который для XN + 1будет выглядеть так:

В обычной десятичной записи этот номер равен

450813704461563958982113775643437908.

Иногда машину с номером nмы, не вполне точно, будем называть n-ймашиной Тьюринга и обозначать ее T_n. В этом случае XN +1становится

450813704461563958982113775643437908 — й

машиной Тьюринга!

Кажется поразительным факт, что нам надо пробежать так долго вдоль «списка» машин Тьюринга, чтобы найти машину, выполняющую такую тривиальную операцию, как прибавление единицы к натуральному числу (в расширенном двоичном представлении). (Я не думаю, что моя система кодирования была в целом настолько неэффективна, хотя в ней и есть еще возможности для незначительных улучшений.) В действительности, есть машины Тьюринга и с меньшими номерами, которые представляют интерес, например UN +1с двоичным номером

101011010111101010,