Мой цикл копирования не заканчивается. Машина Тьюринга

Question

Я пытаюсь написать набор правил, который копирует набор тиков, однако длинное одно пространство рядом с исходным множеством, у меня есть цикл, который делает это, однако он не останавливается и не продолжается вперед и прерывает скопированные Предметы.

http://i.imgur.com/8cpaYkN.png

под отсечным картины следует сказать, 5 0 -> 1 Tick

Это основано на модели находится по адресу: http://en.wikipedia.org/wiki/Turing_machine_examples#A_copy_subroutine

Любое понимание?

изменить: он должен остановиться, когда достигнет среднего нуля между двумя рядами чисел, но мой продолжает двигаться.

редактировать:

Так моя программа проверяет наличие 1, если он находит, что превращает его в ноль и пропускает следующие из них до тех пор, пока не достигнет нуля, он пропускает ноль и следующие из них (которые там ни один из них не был в начале) и изменяет первый 0 на 1, затем он возвращает, пропуская единицы и нуль, а затем пропускает их до тех пор, пока не найдет первый нуль (тот, который был изменен) изменяет его на один а затем программные петли. Он должен остановиться, когда он достигнет нуля центра, который разделяет два числа.

Это как.

State 1, 0 -> state 1, 0 
State 1, 1 -> state 2, 1 [changes the first 1 to a 0] 
state 2, 1 -> state 2, 1 
state 2, 0 -> state 3, 0 
state 3, 1 -> state 3, 1 
state 3, 0 -> state 4, 1 (right) (goes back) [changes the first 0 to a 1] 
state 4, 1 -> state 4, 1 (right) 
state 4, 0 -> state 5, 0 (right) 
state 5, 1 -> state 5, 1 (right) 
state 5, 0 -> state 1, 1 (left) (loops) [changes the first changed 1 back] 

Если я делаю это для любой последовательности из них, он будет копировать их, однако, это не остановит цикл, и он будет продолжаться и после его завершения и разорвать копию.

Так что, если я вход:

0 0 1 1 1 0 0 0 0 0 0..... 

правила будут делать следующее:

0 0 1 1 1 0 0 0 0 0 0..... 
0 0 0 1 1 0 1 0 0 0 0..... 
0 0 1 0 1 0 1 1 0 0 0..... 
0 0 1 1 0 0 1 1 1 0 0..... 
0 0 1 1 1 0 1 1 1 0 0..... 

(. Он теперь должен остановиться, но он продолжает идти, испытывая новые скопированные входы)

Answer 1

Эта линия является неправильным:

State 1, 1 -> state 2, 1 [changes the first 1 to a 0] 

Это должно быть

State 1, 1 -> state 2, 0 [changes the first 1 to a 0] 

Но я немного озадачен, потому что я думаю, что эффект этой ошибки он будет продолжать расти число 1s в левой части ленты.

Эта процедура должна работать следующим образом:

Начиная с первой 1 на входе:

• Если текущий символ равен 0, остановка.
• Замените его нулем.
• Сканирование среднего нуля.
• Сканирование по существующим 1.
• Запишите a 1
• Отсканируйте назад для второго 0.
• Замените его на 1.
• Идите вправо один раз.
• Repeat

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

def machine(tape, program, start, pc): 
    head = start 
    while True: 
     if head < 0: 
      raise AssertionError('off tape') 
     if head >= len(tape): 
      tape.append(0) 
     cmd = program[pc, tape[head]] 
     if cmd == 'halt': return 
     newpc, write, move = cmd 
     tape[head], head, pc = write, head + move, newpc 
     print pc, head, tape 

L, R = -1, 1 
tape = [1, 1, 1, 0] 
program = { 
    (1, 0): 'halt', 
    (1, 1): (2, 0, R), 
    (2, 1): (2, 1, R), 
    (2, 0): (3, 0, R), 
    (3, 1): (3, 1, R), 
    (3, 0): (4, 1, L), 
    (4, 1): (4, 1, L), 
    (4, 0): (5, 0, L), 
    (5, 1): (5, 1, L), 
    (5, 0): (1, 1, R) 
} 

machine(tape, program, 0, 1)