Решение: Работа машины Тьюринга
На ленте в соседних ячейках записано двоичное представление числа 1514 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Определите результат выполнения программы. Запишите получившееся число в десятичной системе счисления.
| Состояние / символ | λ | 0 | 1 |
|---|---|---|---|
| q₀ | λ, L, q₁ | ||
| q₁ | λ, R, q₂ | 0, L, q₁ | 1, L, q₁ |
| q₂ | λ, R, q₃ | ||
| q₃ | 1, S, q₃ | 1, S, q₃ |
Решение по шагам
6 шаговПредставим число 1514 в двоичной системе счисления.
$$1514 = 2^{10}+2^8+2^7+2^6+2^5+2^3+2^1 = 10111101010_2$$В состоянии q₀ головка с пустой ячейки справа сдвигается влево и переходит в состояние q₁.
В состоянии q₁ головка движется влево по всей двоичной записи. Дойдя до пустой ячейки слева, она сдвигается вправо и переходит в состояние q₂.
Первая цифра записи равна 1. В состоянии q₂ она заменяется на λ, а головка переходит вправо в состояние q₃.
Вторая цифра исходной записи равна 0. В состоянии q₃ она заменяется на 1, после чего машина останавливается.
$$10111101010_2 \rightarrow 1111101010_2$$Переведём получившееся число в десятичную систему.
$$1111101010_2 = 512+256+128+64+32+8+2 = 1002$$Где здесь ошибаются
Не учитывать, что первая единица стирается в состоянии q₂.
Забыть заменить следующую за ней цифру 0 на 1 в состоянии q₃.
Перепутать направление движения головки при обработке пустой ячейки.