Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
… 0000011111101111111100000….
После того, как машина Тьюринга после большого числа шагов останавливается, мы получаем ленту с записью вида
…000011000000000000…,
при этом машина располагается справа от ненулевых цифр. Таким образом, найденный наибольший общий делитель равен 2(как и должно быть).
Исчерпывающее объяснение, почемумашина EUC(или UN х 2) на самом деле осуществляет действие, для которого она предназначена, включает в себя некоторые тонкости, и разобраться в нем, может быть, даже труднее, чем понять устройство самой машины — довольно обычная ситуация с компьютерными программами! (Чтобы полностью понять, почему алгоритмические процедуры делают то, что от них ожидается, необходима определенная интуиция. А не являются ли интуитивные прозрения сами алгоритмическими? Это один из вопросов, которые будут для нас важны в дальнейшем.) Яне буду пытаться дать здесь такое объяснение для приведенных примеров EUCили UN х 2. Читатель, шаг за
Двоичная запись цифровых данных
Унарная система чрезвычайно неэффективна для записи больших чисел. Поэтому мы по большей части будем использовать вышеописанную двоичнуюсистему. Однако, сделать это напрямую и попытаться читать ленту просто как двоичное число мы не сможем. Дело в том, что мы не имеем возможности сказать, когда кончается двоичное представление числа и начинается бесконечная последовательность нулей справа, которая отвечает пустой ленте. Нам нужен способ как-то обозначать конец двоичной записи числа. Более того, часто нам будет нужно вводить в машину несколькочисел, как, например, в случае с алгоритмом Евклида, когда требуется парачисел [42] . Но в двоичном представлении мы не можем отличить пробелымежду числами от нулей или строчек нулей, входящих в записи этих двоичных чисел. К тому же, помимо чисел нам может понадобиться и запись всевозможных сложных инструкций на той же ленте. Для того чтобы преодолеть эти трудности, воспользуемся процедурой, которую я буду в дальнейшем называть сокращениеми согласно которой любая строчка нулей и единиц (с конечным числом единиц) не просто считывается как двоичное число, но замещается строкой из нулей, единиц, двоек, троек и т. д. таким образом, чтобы каждое число в получившейся строчке соответствовало числу единиц между соседними нулями в исходной записи двоичного числа. Например, последовательность
42
Существует немало других известных в математике способов записи пар, троек и большего количества чисел в виде одного числа, но они менее удобны для наших целей. Например, формула 1/2 ((а + Ь)^2 + 3а + b) однозначно представляет пару (а, Ь) как одно натуральное число. Проверьте сами!
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.
Такая процедура дает нам, в частности, возможность указывать, где заканчивается запись числа (и тем самым отделять ее от бесконечной полосы пустой ленты справа), просто используя запятую в конце этой записи. Более того, она позволяет закодировать любую последовательность натуральных чисел, записанных в двоичной системе, как простую последовательность нулей и единиц, в которой для разделения чисел мы используем запятые. Посмотрим, как это сделать, на конкретном примере. Возьмем последовательность
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. На самом деле и пустое поле, если рассуждать логически, должно обозначать нуль! В обычном представлении это привело бы к большой путанице, но в описанной выше системе кодирования никаких затруднений не возникает: нуль между двумя запятыми можно записать просто в виде двух запятых, следующих подряд (''). На ленте такой записи будет соответствовать код, состоящий из двух пар единиц, разделенных одним нулем:
43
В изложенном выше я не вводил никакой метки для начала последовательности чисел (или инструкций и т. п.). Это совершенно не требуется для входных данных, поскольку все начинается в тот момент, когда считана первая единица. Однако для конечного результата может понадобиться что-то дополнительное, поскольку априориникто не может сказать, как долго придется двигаться по ленте, чтобы добраться до первой (т. е. самой левой!) единицы. Хотя при движении налево может встретиться длинная строка нулей, нет никаких гарантий, что еще дальшене встретится единица. В этом случае применимы различные подходы. Можно было бы всегда использовать специальную отметку (допустим, 6, записанную при помощи процедуры «сокращения»), чтобы указывать начало и завершение окончательного ответа. Но для простоты я в своем изложении буду придерживаться другой точки зрения, согласно которой мы всегда «знаем», сколько в действительности ленты обработало наше устройство (например, можно представить, что оно оставляет своего рода «след»), так что не обязательно просматривать ленту до бесконечности, чтобы убедиться в том, что весь ответ считан.
…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):
0 0– > 0 0R
0 1– > 1 1R
1 0– > 0 0R