Исполнитель МТ работает с бесконечной лентой, разделённой на ячейки. В каждой ячейке находится символ 0, символ 1 или пустой символ λ. Головка исполнителя находится в одном из состояний q0, q1 и обозревает одну ячейку.
Программа задаётся таблицей. Строка таблицы соответствует текущему состоянию головки, столбец — символу в обозреваемой ячейке. Команда состоит из трёх элементов: записываемого символа, действия головки и нового состояния. Действие L означает сдвиг на одну ячейку влево, R — на одну ячейку вправо, S — остановку. Сначала выполняется запись символа, затем действие головки. Прочерком отмечены неиспользуемые сочетания состояния и символа.
На ленте в соседних ячейках записано двоичное представление числа 1535 без ведущих нулей. Все остальные ячейки пусты. В начальный момент головка находится в состоянии q0 в пустой ячейке непосредственно справа от записи числа.
Исполнитель МТ работает с бесконечной лентой, разделённой на ячейки. В каждой ячейке находится символ 0, символ 1 или пустой символ λ. Головка исполнителя находится в одном из трёх состояний q0, q1, q2 и обозревает одну ячейку.
Программа задаётся таблицей. Строка таблицы соответствует текущему состоянию головки, столбец — символу в обозреваемой ячейке. Команда состоит из трёх элементов: записываемого символа, действия головки и нового состояния. Действие L означает сдвиг на одну ячейку влево, R — на одну ячейку вправо, S — остановку. Сначала выполняется запись символа, затем действие головки.
Выполните задание
На ленте в соседних ячейках записано двоичное представление числа 1535 без ведущих нулей. Все остальные ячейки пусты. В начальный момент головка находится в состоянии q0 и обозревает крайнюю левую цифру записи числа.
| Состояние |
λ |
0 |
1 |
| q0 |
λ, L, q1 |
0, R, q0 |
1, R, q0 |
| q1 |
1, R, q2 |
1, R, q2 |
0, L, q1 |
| q2 |
1, S, q2 |
0, R, q2 |
1, R, q2 |
Определите число, двоичная запись которого останется на ленте после завершения программы. Ответ запишите в десятичной системе счисления.