Задание 12. Исполнитель МТ

Задание 12 демонстрационного варианта ЕГЭ-2027 (ФИПИ) – целиком, вместе с описанием исполнителя.

Индексы состояний ФИПИ печатает нижними ($q_0$), а в таблицах ниже и в виджете они написаны в строку (q0) – это одно и то же.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A = \lbrace a_0, a_1, \ldots, a_{n-1} \rbrace$), включая специальный пустой символ $a_0$.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q = \lbrace q_0, q_1, \ldots, q_{n-1} \rbrace$. В начальный момент времени головка находится в начальном состоянии $q_0$.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может изменить символ в текущей ячейке и переместиться в соседнюю ячейку слева или справа от неё. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из трёх символов «L», «R», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_3$.

Приведём пример выполнения программы, заданной таблично. На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «λ». В начальный момент времени головка находится на неизвестном расстоянии справа от самого правого символа «Z».

Программа

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».

Возможное начальное состояние исполнителя: … λ λ Z Z Z Z λ λ … , головка обозревает вторую справа ячейку с символом «λ» и находится в состоянии $q_0$.

Конечное состояние исполнителя после завершения выполнения программы: … λ λ X X X X λ λ … , головка обозревает ячейку слева от символов «X» и находится в состоянии $q_2$.

Выполните задание.

На ленте в соседних ячейках записано двоичное представление числа 2025 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.

Программа работы исполнителя:

Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

1. Нарисуйте ленту. Ряд клеток, в каждой ровно один символ. Впишите то, что дано: двоичную запись числа 2025 – 11111101001, по цифре в клетку. Слева и справа добавьте по три клетки и поставьте в них λ. Это не поля про запас: пустой символ – такой же символ ленты, машина его читает.
2. Поставьте стрелку и подпишите состояние. Стрелка сверху – это головка. «В ближайшей справа к последовательности ячейке» значит над первой пустой клеткой справа от числа. Над стрелкой напишите q0: начальное состояние.
3. Найдите клетку таблицы. Строка – то состояние, что подписано у стрелки. Столбец – тот символ, что стоит под стрелкой. На пересечении команда из трёх частей.
4. Выполните все три части по порядку. Первая – впишите этот символ в клетку под стрелкой, прежний зачеркните. Вторая – L сдвиньте стрелку на клетку влево, R вправо, S оставьте на месте. Третья – сотрите подпись состояния и напишите новую.
5. Во второй части стояло S – машина стоит. Иначе возвращайтесь к шагу 3: новое состояние, новый символ под стрелкой, новая клетка таблицы. Пустая клетка – тоже конец, но аварийный: такой пары в задаче не бывает, значит где-то сбились.
6. Прочитайте ответ с ленты. Всё, что стоит между крайними непустыми клетками, и есть результат. Спрашивают десятичное число – переведите.

Вот эти шаги для нашей задачи – ровно те строчки, которые появятся в тетради:

Середину можно не расписывать, когда рука набьётся. В строке q1 оба столбца с цифрами делают одно и то же: пишут тот же символ и идут влево. Значит весь этот кусок – «иди влево по числу, ничего не меняя», сколько бы цифр там ни было, и интересны только вход в проход (первый такт) и выход из него (такт 13). Но пока считаете такты по клеткам – пишите все: ошибка на одном такте уводит весь ответ.

Ниже – та же программа, только живая. Пройдите её по тактам и сверьте со своей тетрадью: жёлтым горит как раз та клетка таблицы, которую вы ищете на шаге 3.

После остановки на ленте 111111101001 – двоичная запись из 12 цифр.

Переводим в десятичную. Старшая единица – это $2^{11} = 2048$, остальное – исходное число: $2048 + 2025 = 4073$.

Ответ: 4073.

1. Прочитали таблицу неправильно. Ошиблись в исполнении команды.
2. Забыли, что S сначала пишет. Команда λ, S, q2 сперва кладёт символ в ячейку и только потом останавливает исполнителя. Здесь пишется пустой символ и на ответ это не влияет, но в задачах, где по S пишется цифра, это последняя цифра ответа.
3. Начали с цифры, а не с пустой ячейки. «Ближайшая справа к последовательности ячейка» – пустая, а не последняя цифра числа. Лишний или пропущенный такт разгона сдвигает всю трассировку.