Задание 12. Информатика. ЕГЭ 2026. Апробация. 14.05.2026

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

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

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

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

	\(a_0\)	\(a_1\)	\(\ldots\)	\(a_n\)
\(q_0\)	команда	команда	\(\ldots\)	команда
\(q_1\)	команда	команда	\(\ldots\)	команда
\(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)
\(q_{n-1}\)	команда	команда	\(\ldots\)	команда

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

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

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

На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «\(Z\)», все остальные ячейки ленты заполнены пустым символом «\(\lambda\)». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «\(Z\)».

Программа

	\(\lambda\)	\(Z\)
\(q_0\)	\(\lambda , \, L, \, q_0\)	\(X, \, L, \, q_1\)
\(q_1\)	\(\lambda , \, S, \, q_1\)	\(X, \, L, \, q_1\)

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

Возможное начальное состояние исполнителя:

\(\ldots\)	\(\lambda\)	\(\lambda\)	\(Z\)	\(Z\)	\(Z\)	\(Z\)	\(\lambda\)	\(\lambda\)	\(\ldots\)
								\(\blacktriangle q_0\)

Конечное состояние исполнителя после завершения выполнения программы:

\(\ldots\)	\(\lambda\)	\(\lambda\)	\(X\)	\(X\)	\(X\)	\(X\)	\(\lambda\)	\(\lambda\)	\(\ldots\)
		\(\blacktriangle q_0\)

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

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

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

	\(\lambda\)	\(0\)	\(1\)
\(q_0\)	\(\lambda , \, R, \, q_1\)
\(q_1\)	\(\lambda , \, L, \, q_2\)	\(0, \, R, \, q_1\)	\(1, \, R, \, q_1\)
\(q_2\)		\(\lambda, \, L, \, q_3\)	\(\lambda, \, L, \, q_3\)
\(q_3\)		\(\lambda, \, S, \, q_3\)	\(1, \, S, \, q_3\)

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

com = {('q0', 'l'): 'l,R,q1',
       ('q1', 'l'): 'l,L,q2', ('q1', '0'): '0,R,q1', ('q1', '1'): '1,R,q1',
                              ('q2', '0'): 'l,L,q3', ('q2', '1'): 'l,L,q3',
                              ('q3', '0'): 'l,S,q3', ('q3', '1'): '1,S,q3',}

move = {'L': -1, 'R': 1, 'S': 0}
state = 'q0'
m = 'L'
b = 'l'
s = ['l'] * 4 + list(bin(1097)[2:]) + ['l'] * 4
p = 3
while m != 'S':
    b, m, state = com[(state, s[p])].split(',')
    s[p] = b
    p += move[m]
n = int(''.join([c for c in s if c != 'l']), 2)
print(n)