Описывая действие машина Тьюринга

Question

Я пытаюсь ответить на третью часть на следующий вопрос:

я нарисовал следующую диаграмму состояний:

В соответствии с решением машина «добавляет 1 к двоичному числу с наименее значимым битом в крайнем левом положении на ленте». Я не уверен, что это значит и не может понять, почему это так.

С входом 111 машина Тьюринга выдает 0001. В этом случае упомянутое выше решение будет означать, что машина добавляет 1 к 111, поскольку его младший значащий бит 1 (?) Находится в крайнем левом положении на ленте , Однако это даст 1000. Если решение правильное, то оно должно означать 000 +1, но я не понимаю, как это происходит?

Как я могу рассуждать об этой машине Тьюринга?

Answer 1

Токарный станок выполняет двоичное добавление. Номера просто записываются с LSB в левой позиции (I.e. назад). Таким образом, 111 == 1110 не 0111, а 111 + 1 == 0001 не 1000.

В q0 ленточная головка находится на 0 (или пуста), то она просто заменяет 0 на 1 идет до конца ленты и принимает. Это явно добавляет 1.

В q0, если в ленте содержится 1, мы заменим 1 на 0. Переход от q2 к q2 несет 1. Переходы от q2 до q3 и q2 к q1 «завершают» операцию переноса (на вашей диаграмме отсутствует переход от q2 к q3 формы _; 1, R).

Так что ответ правильный.