Исполнитель МТ — это читающая и записывающая головка, перемещающаяся вдоль бесконечной ленты, разделённой на ячейки. В каждой ячейке находится один символ из алфавита {0, 1, λ}, где λ — пустой символ. На каждом такте головка обозревает текущую ячейку и в зависимости от своего состояния и обозреваемого символа выполняет команду: записывает символ в текущую ячейку, затем сдвигается влево (L), вправо (R), остаётся на месте, либо завершает работу (S), и переходит в новое состояние.
Программа исполнителя задана таблицей. В первой строке — обозреваемые символы, в первом столбце — состояния. На пересечении указана команда «записываемый символ, направление, новое состояние».
0 1 λ
q0 0,R,q0 1,R,q0 λ,L,q1
q1 1,S,q1 0,L,q1 1,S,q1
В начальный момент на ленте записано двоичное представление числа 8110 (без ведущих нулей): 1111110101110. Остальные ячейки заполнены символом λ. Головка находится над крайней левой ячейкой записи и пребывает в состоянии q0.
Определите число, двоичная запись которого окажется на ленте после завершения работы исполнителя. В ответе запишите это число в десятичной системе счисления.