Тьюринга на вычислимых числах - я не могу понять, как воспроизвести примеры

Question

Я только недавно начал читать некоторые статьи CS, и одной из первых была статья Тьюринга «О вычислимых числах», и там он приводит пример конфигураций машины для печати последовательности 010101. Я понимаю, как это должно работать, но я изо всех сил пытаюсь понять, почему у него есть два шага R в этих операциях:

m-config | symbol | operations | final m-config
         |  None  |     P0     |       b
    b    |   0    |   R, R, P1 |       b
         |   1    |   R, R, P0 |       b

Если я начну проходить через это, вот пара первых шагов:

Шаг 1: P0

Результат:

0

Шаг 1: R, R, P1

0 1

Шаг 2: R, R, P0

0 1 0

Шаг 3: R, R, P1

0 1 0 1

Так что в принципе все работает просто отлично, но в документе четко указано, что этот аппарат должен печатать 010101 без каких-либо пробелов на ленте. Но поскольку после печати мы всегда движемся два раза вправо, это означает, что мы всегда оставляем один пустой квадрат на ленте. Может кто-нибудь помочь мне понять, что я делаю не так?

Answer 1

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

Вычислительные машины.

Если a-machine печатает два вида символов, из которых первый тип (называемые цифры) полностью состоит из 0 и 1 (остальные называются символами второй вид), то машина будет называться вычислительной машиной. Если машина снабжена пустой лентой и приведена в движение, запуск из правильной начальной m-конфигурации, подпоследовательность символов напечатанные им, которые имеют первый вид, будут называться последовательность вычисляется на машине .

Аппарат в этом примере фактически печатает 0B1B0B1B0... на ленте, но вычисляемая последовательность определяется как подпоследовательность 0B1B0B1B0..., которая состоит только из 0 и 1, таким образом, 01010....
На практике Тьюринг допускает пробелы между двоичными цифрами.

Я позорно признаюсь, что никогда не читал оригинальную статью, но я полагаю, что это, возможно, используется для упрощения вычислений: учет пробелов между цифрами избавляет программиста / математиков от повторного выполнения (и скучного) шага.
В основном это позволяет использовать локальный блокнот, вы можете использовать столько ячеек, сколько вам нужно, рядом с цифрой, если вы удалите их, прежде чем перейти к следующей.