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

64 = (2 х З ³) + З ²+ 1; см. главу 4).

Используя двоичную запись для внутренних состояний, можно представить вышеприведенную инструкцию, описывающую машину Тьюринга, следующим образом:

Здесь я к тому же сократил R.STOPдо STOP, поскольку мы вправе считать, что L.STOPникогда не происходит, так как результат последнего шага вычислений, будучи частью окончательного ответа, всегда отображается слева от устройства.

Предположим, что наше устройство находится во внутреннем состоянии, представленном бинарной последовательностью 11010010, и процессу вычисления соответствует участок ленты, изображенный на предыдущем рисунке. Пусть мы задаем команду

11010010 0– > 11 1L.

Та цифра на ленте, которая в данный момент считывается (в нашем случае цифра «0»), показана «жирным» символом справа от последовательности нулей и единиц, обозначающих внутреннее состояние.

В частично описанном выше примере машины Тьюринга (который я выбрал более-менее произвольно) считанный «0»был бы тогда замещен на «1», внутреннее состояние поменялось бы на «11»и устройство переместилось бы на один шаг влево:

Теперь устройство готово к считыванию следующей цифры, снова «0». Согласно таблице, оно оставляет этот «0»нетронутым, но изменяет свое внутреннее состояние на «100101» и передвигается по ленте назад, т. е. на один шаг вправо. Теперь оно считывает «1»и находит где-то ниже в таблице инструкцию, которая определяет изменение внутреннего состояния и указывает, должна ли быть изменена считанная цифра и в каком направлении по ленте должно дальше двигаться устройство. Таким образом устройство будет действовать до тех пор, пока не достигнет команды STOP. В этой точке — после еще одного шага вправо — раздастся звонок, оповещающий оператора о том, что вычисления завершены.

Мы будем считать, что машина всегда начинает с внутреннего состояния «0»и что вся лента справа от устройства изначально пуста. Все инструкции и данные подаются в устройство с правой стороны. Как упоминалось ранее, эта информация всегда имеет форму конечной строки из нулей и единиц, за которой следует пустая лента (т. е. нули). Когда машина получает команду STOP, результаты вычислений оказываются на ленте слева от считывающего устройства.

Поскольку мы хотели бы иметь возможность вводить в устройство и числовые данные, то нам потребуется некий способ описания обычных чисел (под которыми я здесь имею в виду целые неотрицательные числа 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и расположена слева, а лента выглядит следующим образом: