ЕГЭ по информатике, 11 класс · Машина Тьюринга · 12. В формате ЕГЭ
Машина Тьюринга — 3
Сложность: средняя~6 мин
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на ячейки. В каждой ячейке находится ровно один символ, включая пустой символ λ. На каждом такте головка обозревает одну ячейку, может изменить символ в ней и сдвинуться на соседнюю ячейку влево или вправо, после чего переходит в новое состояние. Программа задаётся таблицей: на пересечении состояния и символа — команда из трёх элементов через запятую: записываемый символ; L, R — сдвиг влево или вправо, S — остановка после выполнения команды; новое состояние. В начальный момент головка находится в состоянии q0.
На ленте в соседних ячейках записано двоичное представление числа 455 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.
Программа работы исполнителя:
| λ | 0 | 1 |
|---|
| q0 | λ, L, q1 | | |
| q1 | λ, S, q1 | 0, L, q1 | 1, L, q2 |
| q2 | λ, S, q2 | 1, L, q2 | 0, L, q2 |
Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.
