Новый ум короля: О компьютерах, мышлении и законах физики | страница 54

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

1 → 1,

2 → 11,

3 → 111,

4 → 1111,

5 → 11111 и т. д.

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

00 → 00R

01 → 11L

10 → 101R

11 → 11L

100 → 10100R

101 → 110R

110 → 1000R

111 → 111R

1000 → 1000R

1001 → 1010R

1010 → 1110L

1011 → 1101L

1100 → 1100L

1101 → 11L

1110 → 1110L

1111 → 10001L

10000 → 10010L

10001 → 10001L

10010 → 100R

10011 → 11L

10100 → 00.STOP

10101 → 10101R

Однако я бы порекомендовал такому читателю начать не с этого упражнения, а с чего-нибудь гораздо более простого, например, с машины Тьюринга UN + 1, которая просто прибавляет единицу к числу в унарном представлении:

00 → 00R

01 → 11R

10 → 01.STOP

11 → 11R

Чтобы убедиться в том, что UN +1 на самом деле производит такую операцию, давайте мысленно применим ее, скажем, к ленте вида

…00000111100000…,

соответствующей числу четыре. Мы будем полагать, что наше устройство сначала находится где-то слева от последовательности единиц. Находясь в исходном состоянии 0, оно считывает 0, в соответствии с первой инструкцией сохраняет его неизмененным, после чего перемещается на шаг вправо, оставаясь во внутреннем состоянии 0. Оно продолжает последовательно передвигаться вправо до тех пор, пока не встретит первую единицу. После этого вступает в силу вторая инструкция: устройство оставляет единицу как есть и сдвигается на шаг вправо, но уже в состоянии 1. В соответствии с четвертой инструкцией оно сохраняет внутреннее состояние 1, равно как и все считываемые единицы, двигаясь вправо до встречи с первым после набора единиц нулем. Тогда начинает действовать третья инструкция, согласно которой устройство заменяет этот нуль на