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