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

Поскольку мы хотели бы иметь возможность вводить в устройство и числовые данные, то нам потребуется некий способ описания обычных чисел (под которыми я здесь имею в виду целые неотрицательные числа 0, 1, 2, 3, 4….) как части входной информации. Для представления числа n можно было бы просто использовать строку из n единиц (хотя при этом могут возникнуть трудности, когда речь зайдет о нуле):

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(как и должно быть).