11 0 → 100 0R
11 1 → 11 1R
100 0 → 100 0R
100 1 → 101 0R
101 0 → 111 0L
101 1 → 110 1L
110 0 → 110 0L
110 1 → 1 1L
111 0 → 111 0L
111 1 → 1000 1L
1000 0 → 1001 0L
1000 1 → 1000 1L
1001 0 → 10 0R
1001 1 → 1 1L
1010 0 → 0 0.STOP
1010 1 → 1010 1R
Однако я бы порекомендовал такому читателю начать не с этого упражнения, а с чего-нибудь гораздо более простого, например, с машины Тьюринга UN + 1, которая просто прибавляет единицу к числу в унарном представлении:
0 0 → 0 0R
0 1 → 1 1R
1 0 → 0 1.STOP
11 → 1 1R
Чтобы убедиться в том, что UN +1на самом деле производит такую операцию, давайте мысленно применим ее, скажем, к ленте вида
…00000111100000…,
соответствующей числу четыре. Мы будем полагать, что наше устройство сначала находится где-то слева от последовательности единиц. Находясь в исходном состоянии 0, оно считывает 0, в соответствии с первой инструкцией сохраняет его неизмененным, после чего перемещается на шаг вправо, оставаясь во внутреннем состоянии 0. Оно продолжает последовательно передвигаться вправо до тех пор, пока не встретит первую единицу. После этого вступает в силу вторая инструкция: устройство оставляет единицу как есть и сдвигается на шаг вправо, но уже в состоянии 1. В соответствии с четвертой инструкцией оно сохраняет внутреннее состояние 1, равно как и все считываемые единицы, двигаясь вправо до встречи с первым после набора единиц нулем. Тогда начинает действовать третья инструкция, согласно которой устройство заменяет этот нуль на 1, перемещается на один шаг вправо (вспомним, что команда STOPэквивалентна R.STOP) и останавливается. Тем самым к последовательности из четырех единиц прибавляется еще одна, превращая — как и требовалось — 4в 5.
В качестве несколько более трудного упражнения можно проверить, что машина UN х 2, определяемая набором инструкций
0 0 → 0 0R
0 1 → 1 0R
1 0 → 10 1L
1 1 → 1 1R
10 0 → 11 0R
10 1 → 100 0R
11 0 → 0 1.STOP
11 1 → 11 1R
100 0 → 101 1L
100 1 → 100 1R
101 0 → 10 1L
101 1 → 101 1L
удваиваетунарное число, как и должно быть, судя по ее названию.
Чтобы понять, как работает машина 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.
Такая процедура дает нам, в частности, возможность указывать, где заканчивается запись числа (и тем самым отделять ее от бесконечной полосы пустой ленты справа), просто используя запятую в конце этой записи. Более того, она позволяет закодировать любую последовательность натуральных чисел, записанных в двоичной системе, как простую последовательность нулей и единиц, в которой для разделения чисел мы используем запятые. Посмотрим, как это сделать, на конкретном примере. Возьмем последовательность
5, 13, 0, 1, 1, 4.
В двоичном представлении она эквивалентна последовательности
101, 1101, 0, 1, 1, 100,
что на ленте можно записать с помощью операции расширения(обратной по отношению к описанной выше процедуре сокращения) как
…000010010110101001011001101011010110100011000…
Такое кодирование легко выполнить, если в исходной двоичной записи чисел провести следующие замены:
0 → 0
1 → 10
, → 110
и после этого добавить бесконечные последовательности нулей с обеих сторон вновь полученной записи. Чтобы сделать более понятной эту процедуру в применении к нашему примеру, разделим полученные двоичные числа пробелами:
42
Существует немало других известных в математике способов записи пар, троек и большего количества чисел в виде одного числа, но они менее удобны для наших целей. Например, формула ½((а + Ь)² + 3а + b) однозначно представляет пару (а, Ь) как одно натуральное число. Проверьте сами!