01000101101010110100011101010111100110
превратится в
Мы теперь можем считывать числа 2, 3, 4… как метки или инструкции определенного рода. Действительно, пусть 2 будет просто «запятой», указывающей на пробел между двумя числами, а числа 3, 4, 5… могли бы по нашему желанию символизировать различные инструкции или необходимые обозначения, как, например, «минус», «плюс», «умножить», «перейти в позицию со следующим числом», «повторить предыдущую операцию следующее число раз», и т. п. Теперь у нас есть разнообразные последовательности нулей и единиц, разделенные цифрами большей величины. Эти последовательности нулей и единиц будут представлять собой обычные числа, записанные в двоичной форме. Тогда записанная выше строка (при замене двоек «запятыми») примет вид:
(двоичное число 1001) запятая (двоичное число 11) запятая….
Используя обычные арабские числа «9», «3», «4», «0» для записи соответствующих двоичных чисел 1001, 11, 100 и 0, получаем новую запись всей последовательности в виде: 9, 3, 4 (инструкция 3) 3 (инструкция 4) 0.
Такая процедура дает нам, в частности, возможность указывать, где заканчивается запись числа (и тем самым отделять ее от бесконечной полосы пустой ленты справа), просто используя запятую в конце этой записи. Более того, она позволяет закодировать любую последовательность натуральных чисел, записанных в двоичной системе, как простую последовательность нулей и единиц, в которой для разделения чисел мы используем запятые. Посмотрим, как это сделать, на конкретном примере. Возьмем последовательность
5, 13, 0, 1, 1, 4.
В двоичном представлении она эквивалентна последовательности
101, 1101, 0, 1, 1, 100,
что на ленте можно записать с помощью операции расширения(обратной по отношению к описанной выше процедуре сокращения) как
…000010010110101001011001101011010110100011000…
Такое кодирование легко выполнить, если в исходной двоичной записи чисел провести следующие замены:
0 → 0
1 → 10
, → 110
и после этого добавить бесконечные последовательности нулей с обеих сторон вновь полученной записи. Чтобы сделать более понятной эту процедуру в применении к нашему примеру, разделим полученные двоичные числа пробелами:
0000 10 0 10 110 10 10 0 10 110 0 110 10 110 10 110 10 0 0 110 00.
Я буду называть этот способ представления (наборов) чисел расширенной двоичной записью. (Так, в частности, в расширенной двоичной форме записи число 13 выглядит как 1010010.)
Есть еще одно, последнее, замечание, которое надо сделать в связи с этой системой записи. Это не более, чем техническая деталь, но она необходима для полноты изложения [43]. Двоичная (или десятичная) запись натуральных чисел в некоторой степени избыточна в том смысле, что нули, расположенные слева от записи числа, «не считаются» и обычно опускаются, так что 00110010 представляет собой то же самое двоичное число, что и 110010(а 0050 — то же самое десятичное число, что и 50). Эта избыточность распространяется и на нуль, который может быть записан и как 000, и как 00, и, конечно, как 0. На самом деле и пустое поле, если рассуждать логически, должно обозначать нуль! В обычном представлении это привело бы к большой путанице, но в описанной выше системе кодирования никаких затруднений не возникает: нуль между двумя запятыми можно записать просто в виде двух запятых, следующих подряд (''). На ленте такой записи будет соответствовать код, состоящий из двух пар единиц, разделенных одним нулем:
…001101100…
Тогда исходный набор из шести чисел может быть записан в двоичной форме как
101,1101''1,1,100,
и на ленте при кодировании в расширенной двоичной форме мы получим последовательность
…00001001011010100101101101011010110100011000.,
в которой на один нуль меньше по сравнению с предыдущим кодом того же набора.
Теперь мы можем рассмотреть машину Тьюринга, реализующую, скажем, алгоритм Евклида в применении к паре чисел, записанных в расширенной бинарной форме. Для примера возьмем ту же пару чисел — 6 и 8, которую мы брали ранее. Вместо прежней унарной записи
…0000011111101111111100000…
воспользуемся двоичным представлением 6 и 8, т. е. 110 и 1000, соответственно. Тогда эта пара имеет вид
6, 8, или в двоичной форме 110, 1000,
43
В изложенном выше я не вводил никакой метки для начала последовательности чисел (или инструкций и т. п.). Это совершенно не требуется для входных данных, поскольку все начинается в тот момент, когда считана первая единица. Однако для конечного результата может понадобиться что-то дополнительное, поскольку