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, которую мы брали ранее. Вместо прежней унарной записи
