Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A = {a0, a1, …, an−1}), включая специальный пустой символ a0. Время работы исполнителя делится на дискретные такты. На каждом такте головка находится в одном из состояний множества Q = {q0, q1, …, qn−1}. В начальный момент головка находится в начальном состоянии q0.
На каждом такте головка обозревает одну ячейку ленты (текущую). За один такт головка может переместиться в соседнюю ячейку справа или слева, не меняя символ, либо заменить символ в текущей ячейке без сдвига. После каждого такта головка переходит в новое состояние или остаётся в прежнем.
Программа исполнителя задаётся в табличном виде. В первой строке перечислены все возможные символы текущей ячейки, в первом столбце — возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ — состояние» невозможна, клетка остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый — записываемый в текущую ячейку символ; второй — один из символов «L», «R», «N», «S» («L»/«R» — сдвиг влево/вправо, «N» — без сдвига, «S» — завершение работы после выполнения команды); третий — новое состояние головки. Сдвиг происходит после записи символа. Например, команда «0, L, q3»: в текущую ячейку записывается «0», затем головка сдвигается влево и переходит в состояние q3.
Пример. На ленте записано неизвестное ненулевое количество подряд идущих символов «Z», остальные ячейки заполнены пустым символом «λ»; головка находится справа от самого правого «Z». Программа
λ Z
q0 λ,L,q0 X,L,q1
q1 λ,S,q1 X,L,q1
заменяет все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности «X».
Выполните задание. На ленте в соседних ячейках записано двоичное представление числа 1024 без ведущих нулей. Ячейки справа и слева заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей справа от последовательности ячейке. Программа исполнителя:
λ 0 1
q0 λ,L,q1
q1 λ,S,q1 1,L,q1 0,R,q2
q2 0,S,q2 0,R,q2 1,R,q2
Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.