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

5, 13, 0, 1, 1, 4.

В двоичном представлении она эквивалентна последовательности

101, 1101, 0, 1, 1, 100,

что на ленте можно записать с помощью операции расширения (обратной по отношению к описанной выше процедуре сокращения) как

…000010010110101001011001101011010110100011000…

Такое кодирование легко выполнить, если в исходной двоичной записи чисел провести следующие замены:

0 → 0

1 → 10

, → 110

и после этого добавить бесконечные последовательности нулей с обеих сторон вновь полученной записи. Чтобы сделать более понятной эту процедуру в применении к нашему примеру, разделим полученные двоичные числа пробелами:

0000 10 0 10 110 10 10 0 10 110 0 110 10 110 10 110 10 0 0 110 00.

Я буду называть этот способ представления (наборов) чисел расширенной двоичной записью. (Так, в частности, в расширенной двоичной форме записи число 13 выглядит как 1010010.)

Есть еще одно, последнее, замечание, которое надо сделать в связи с этой системой записи. Это не более, чем техническая деталь, но она необходима для полноты изложения[43]. Двоичная (или десятичная) запись натуральных чисел в некоторой степени избыточна в том смысле, что нули, расположенные слева от записи числа, «не считаются» и обычно опускаются, так что 00110010 представляет собой то же самое двоичное число, что и 110010 (а 0050 — то же самое десятичное число, что и 50). Эта избыточность распространяется и на нуль, который может быть записан и как 000, и как 00, и, конечно, как 0. На самом деле и пустое поле, если рассуждать логически, должно обозначать нуль! В обычном представлении это привело бы к большой путанице, но в описанной выше системе кодирования никаких затруднений не возникает: нуль между двумя запятыми можно записать просто в виде двух запятых, следующих подряд (''). На ленте такой записи будет соответствовать код, состоящий из двух пар единиц, разделенных одним нулем:

…001101100…

Тогда исходный набор из шести чисел может быть записан в двоичной форме как

101,1101''1,1,100,

и на ленте при кодировании в расширенной двоичной форме мы получим последовательность

…00001001011010100101101101011010110100011000.,

в которой на один нуль меньше по сравнению с предыдущим кодом того же набора.

Теперь мы можем рассмотреть машину Тьюринга, реализующую, скажем, алгоритм Евклида в применении к паре чисел, записанных в расширенной бинарной форме. Для примера возьмем ту же пару чисел — 6 и 8, которую мы брали ранее. Вместо прежней унарной записи

…0000011111101111111100000…

воспользуемся двоичным представлением 6 и 8, т. е. 110 и 1000, соответственно. Тогда эта пара имеет вид

6, 8, или в двоичной форме 110, 1000,

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

… 00000101001101000011000000….

Для этой конкретной пары чисел двоичная форма записи не дает никакого выигрыша по сравнению с унарной. Предположим, однако, что мы берем для вычислений (десятичные) числа 1 583 169 и 8610. В двоичной записи они имеют вид

110000010100001000001,

10000110100010.

На ленте при расширенном двоичном кодировании им будет соответствовать последовательность

… 001010000001001000001000000101101000001010010000100110

которая занимает менее двух строк, тогда как для унарной записи пары чисел «1 583 169, 8610» не хватило бы места на страницах этой книги!

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

Для того чтобы показать, каким образом машина Тьюринга может работать с числами в расширенном двоичном представлении, обратимся к значительно более простой, чем алгоритм Евклида, процедуре — просто прибавлению единицы к произвольному натуральному числу. Ее можно выполнить с помощью следующей машины Тьюринга (которую я назову XN + 1):

00 → 00R

01 → 11R

10 → 00R

11 → 101R

100 → 110L

101 → 101R

110 → 101.STOP

111 → 1000L

1000 → 1011L

1001 → 1001L

1010 → 1100R

1011 → 101R

1101 → 1111R

1110 → 111R

1111 → 1110R

И вновь некоторые дотошные читатели могут захотеть проверить, вправду ли эта машина Тьюринга действует так, как должна, если взять, скажем, число 167. Это число имеет двоичное представление 10100111 и записывается на ленте как

…0000100100010101011000…

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

167 + 1 = 168

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

10100111 + 1 = 10101000.

Таким образом, наша «прибавляющая единицу» машина Тьюринга должна превратить предыдущую запись на ленте в