Новый ум короля: О компьютерах, мышлении и законах физики - [28]
В качестве несколько более трудного упражнения можно проверить, что машина UN х 2, определяемая набором инструкций
00 → 00R
01 → 10R
10 → 101L
11 → 11R
100 → 110R
101 → 1000R
110 → 01.STOP
111 → 111R
1000 → 1011L
1001 → 1001R
1010 → 101L
1011 → 1011L
удваивает унарное число, как и должно быть, судя по ее названию.
Чтобы понять, как работает машина EUC, нужно явным образом задать пару подходящих чисел, скажем, 6 и 8. Как и ранее, изначально машина находится во внутреннем состоянии 0 и расположена слева, а лента выглядит следующим образом:
… 0000011111101111111100000….
После того, как машина Тьюринга после большого числа шагов останавливается, мы получаем ленту с записью вида
…000011000000000000…,
при этом машина располагается справа от ненулевых цифр. Таким образом, найденный наибольший общий делитель равен 2 (как и должно быть).
Исчерпывающее объяснение, почему машина EUC (или UN х 2) на самом деле осуществляет действие, для которого она предназначена, включает в себя некоторые тонкости, и разобраться в нем, может быть, даже труднее, чем понять устройство самой машины — довольно обычная ситуация с компьютерными программами! (Чтобы полностью понять, почему алгоритмические процедуры делают то, что от них ожидается, необходима определенная интуиция. А не являются ли интуитивные прозрения сами алгоритмическими? Это один из вопросов, которые будут для нас важны в дальнейшем.) Яне буду пытаться дать здесь такое объяснение для приведенных примеров EUC или UN х 2. Читатель, шаг за шагом проверив их действие, обнаружит, что я незначительно изменил обычный алгоритм Евклида, чтобы получить более компактную запись в рамках используемой схемы. И все же описание EUC остается достаточно сложным, включая в себя 22 элементарные инструкции для 11 различных внутренних состояний. В основном эти сложности носят чисто организационный характер. Можно отметить, например, что из этих 22 инструкций только 3 в действительности изменяют запись на ленте! (Даже для UN х 2 я использовал 12 инструкций, половина из которых меняют запись на ленте.)
Двоичная запись цифровых данных
Унарная система чрезвычайно неэффективна для записи больших чисел. Поэтому мы по большей части будем использовать вышеописанную двоичную систему. Однако, сделать это напрямую и попытаться читать ленту просто как двоичное число мы не сможем. Дело в том, что мы не имеем возможности сказать, когда кончается двоичное представление числа и начинается бесконечная последовательность нулей справа, которая отвечает пустой ленте. Нам нужен способ как-то обозначать конец двоичной записи числа. Более того, часто нам будет нужно вводить в машину несколько чисел, как, например, в случае с алгоритмом Евклида, когда требуется пара чисел[42]. Но в двоичном представлении мы не можем отличить пробелы между числами от нулей или строчек нулей, входящих в записи этих двоичных чисел. К тому же, помимо чисел нам может понадобиться и запись всевозможных сложных инструкций на той же ленте. Для того чтобы преодолеть эти трудности, воспользуемся процедурой, которую я буду в дальнейшем называть сокращением и согласно которой любая строчка нулей и единиц (с конечным числом единиц) не просто считывается как двоичное число, но замещается строкой из нулей, единиц, двоек, троек и т. д. таким образом, чтобы каждое число в получившейся строчке соответствовало числу единиц между соседними нулями в исходной записи двоичного числа. Например, последовательность
01000101101010110100011101010111100110
превратится в
Мы теперь можем считывать числа 2, 3, 4… как метки или инструкции определенного рода. Действительно, пусть 2 будет просто «запятой», указывающей на пробел между двумя числами, а числа 3, 4, 5… могли бы по нашему желанию символизировать различные инструкции или необходимые обозначения, как, например, «минус», «плюс», «умножить», «перейти в позицию со следующим числом», «повторить предыдущую операцию следующее число раз», и т. п. Теперь у нас есть разнообразные последовательности нулей и единиц, разделенные цифрами большей величины. Эти последовательности нулей и единиц будут представлять собой обычные числа, записанные в двоичной форме. Тогда записанная выше строка (при замене двоек «запятыми») примет вид:
(двоичное число 1001) запятая (двоичное число 11) запятая….
Используя обычные арабские числа «9», «3», «4», «0» для записи соответствующих двоичных чисел 1001, 11, 100 и 0, получаем новую запись всей последовательности в виде: 9, 3, 4 (инструкция 3) 3 (инструкция 4) 0.
Такая процедура дает нам, в частности, возможность указывать, где заканчивается запись числа (и тем самым отделять ее от бесконечной полосы пустой ленты справа), просто используя запятую в конце этой записи. Более того, она позволяет закодировать любую последовательность натуральных чисел, записанных в двоичной системе, как простую последовательность нулей и единиц, в которой для разделения чисел мы используем запятые. Посмотрим, как это сделать, на конкретном примере. Возьмем последовательность
