ЕГЭ, вариант 1 · 12. Машина Тьюринга

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на ячейки. В каждой ячейке находится ровно один символ, включая пустой символ λ. На каждом такте головка обозревает одну ячейку, может изменить символ в ней и сдвинуться на соседнюю ячейку влево или вправо, после чего переходит в новое состояние. Программа задаётся таблицей: на пересечении состояния и символа — команда из трёх элементов через запятую: записываемый символ; L, R — сдвиг влево или вправо, S — остановка после выполнения команды; новое состояние. В начальный момент головка находится в состоянии q0. На ленте в соседних ячейках записано двоичное представление числа 1699 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами λ. В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке. Программа работы исполнителя:Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.