1, то оно должно перейти в состояние 13, оставить на ленте тот же символ 1 и переместиться по ленте на один квадрат влево. Последняя же инструкция 259 1→ 0 0R.STOP говорит о том, что если устройство находится в состоянии 259 и считывает с ленты 1, то оно должно вернуться в состояние 0, стереть с ленты 1, т.е. записать в текущий квадрат 0, переместиться по ленте на один квадрат вправо и прекратить вычисления.
Вместо номеров 0, 1, 2, 3, 4, 5…. для обозначения внутренних состояний мы можем — и это более соответствовало бы знаковой системе нанесения меток на ленту — прибегнуть к системе нумерации, построенной только на символах «0» и «1». Состояние n можно было бы обозначить просто последовательностью из n единиц, но такая запись неэффективна. Вместо этого мы используем двоичную систему счисления, ставшую теперь общепринятой:
0→ 0,
1→ 1,
2→10,
3→ 11,
4→100,
5→ 101,
6→ 110,
7→ 111,
8→1000,
9→1001,
10→ 1010,
11→ 1011,
12→ 1100 и т.д.
Здесь последняя цифра справа соответствует «единицам» точно так же, как и в стандартной (десятичной) системе записи, но цифра прямо перед ней показывает число «двоек», а не «десятков». В свою очередь третья цифра справа относится не к «сотням», а к «четверкам»; четвертая — к «восьмеркам», а не к «тысячам» и т.д. При этом разрядность каждой последующей цифры (по мере продвижения влево) дается соответственной степенью двойки: 1, 2, 4 (= 2 х 2), 8 (= 2 х 2 х 2), 16 (= 2х2х2х2), 32 (= 2x2x2х2х2). (В дальнейшем нам будет иногда удобно использовать в качестве основания системы счисления числа, отличные от «2» и «10». Например, запись десятичного числа 64 по основанию «три» даст 2101, где каждая цифра теперь — некоторая степень тройки:
64 = (2 х З 3) + З 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 и расположена слева, а лента выглядит следующим образом:
… 0000011111101111111100000….
После того, как машина Тьюринга после большого числа шагов останавливается, мы получаем ленту с записью вида
…000011000000000000…,
при этом машина располагается справа от ненулевых цифр. Таким образом, найденный наибольший общий делитель равен 2(как и должно быть).
Исчерпывающее объяснение, почему машина EUC(или UN х 2) на самом деле осуществляет действие, для которого она предназначена, включает в себя некоторые тонкости, и разобраться в нем, может быть, даже труднее, чем понять устройство самой машины — довольно обычная ситуация с компьютерными программами! (Чтобы полностью понять, почему алгоритмические процедуры делают то, что от них ожидается, необходима определенная интуиция. А не являются ли интуитивные прозрения сами алгоритмическими? Это один из вопросов, которые будут для нас важны в дальнейшем.) Яне буду пытаться дать здесь такое объяснение для приведенных примеров EUC или UN х 2. Читатель, шаг за шагом проверив их действие, обнаружит, что я незначительно изменил обычный алгоритм Евклида, чтобы получить более компактную запись в рамках используемой схемы. И все же описание