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

Я только недавно начал читать некоторые статьи по 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

Результат:

Шаг 1: Р, Р, П1

0 1

Шаг 2: R, R, P0

0 1 0

Шаг 3: Р, Р, 1 изн.

0 1 0 1

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

computer-science turing-machines

Jefim 12.03.2019 источник

comment

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

Ответы (1)

arrow_upward
1
arrow_downward

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

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

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

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

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

Margaret Bloom 13.03.2019