1 -> 1,

2 -> 11,

3 -> 111,

4 -> 1111,

5 -> 11111 и т. д.

Эта примитивная схема нумерации называется (хотя и довольно нелогично) унарной (единичной)системой. В этом случае символ 0мог бы использоваться в качестве пробела для разделения двух разных чисел. Наличие такого способа разделения для нас существенно, так как многие алгоритмы оперируют не отдельными числами, а множествамичисел. Например, для выполнения алгоритма Евклида наше устройство должно производить определенные действия над паройчисел Аи В. Соответствующая машина Тьюринга может быть легко записана в явном виде. В качестве упражнения заинтересованный читатель может проверить, что нижеследующий набор инструкций действительно описывает машину Тьюринга (которую я буду называть EUC), выполняющую алгоритм Евклида, если в качестве исходных данных использовать два «унарных» числа, разделенных символом 0:

0 0– > 0 0R

0 1– > 1 1L

1 0– > 10 1R

1 1– > 1 1L

10 0 ->1010 0R

10 1– > 11 0R

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 инструкций, половина из которых меняют запись на ленте.)