Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке ленты находится ровно один символ из алфавита исполнителя, включая специальный пустой символ «λ», обозначающий пустую ячейку.
Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.
Каждая команда состоит из трёх элементов, записанных через запятую. Первый элемент — символ алфавита, который следует записать в текущую ячейку (он может совпадать с тем, который уже там записан). Второй элемент — один из символов «L», «R», «N», «S»: символы «L» и «R» означают сдвиг головки на одну ячейку влево или вправо соответственно, символ «N» означает отсутствие сдвига, а символ «S» означает, что после выполнения текущей команды работа исполнителя завершается. Сдвиг головки происходит после записи символа в текущую ячейку. Третий элемент — новое состояние, в которое переходит головка после выполнения команды.
Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.
Выполните задание. На ленте исполнителя МТ в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальном состоянии q0 головка обозревает ближайшую пустую ячейку: слева от записи, если первая команда сдвигает головку вправо (R), и справа от записи, если влево (L).
Программа работы исполнителя:
{2}
После выполнения программы на ленте оказалась двоичная запись числа {3}. Определите десятичное значение наибольшего числа, меньшего, чем {1}, которое могло быть записано на ленте до начала работы программы. Ответ запишите в десятичной системе счисления.