ЕГЭ по информатике 2026, задание 12: исполнитель МТ

В 2026 году это главное содержательное изменение демоверсии. Линия осталась той же: умение исполнить алгоритм исполнителя с фиксированным набором команд. Уровень — повышенный, 1 балл, файл не нужен.

Новый сюжет — исполнитель МТ. ФИПИ прямо не советует решать его программой: легко потратить время и ошибиться в коде. Надёжный путь — несколько тактов вручную и формулировка, что машина делает с лентой.

В открытом банке прошлых лет ещё встречаются старые сюжеты: исполнитель Редактор со строкой «замени / нашлось». Их тоже стоит уметь, но на экзамене 2026 ориентируйтесь на МТ из демоверсии.

Как устроен МТ

Есть бесконечная лента из ячеек. В ячейке один символ алфавита, включая пустой «λ». Головка видит одну ячейку.

Программа — таблица. Строки — состояния q0, q1, … Столбцы — символы. В клетке команда из трёх частей:

символ, сдвиг, новое состояние

• первый элемент записывают в текущую ячейку, даже если он совпадает со старым;
• затем головка сдвигается: L влево, R вправо, N остаётся, S машина останавливается после этой команды;
• третий элемент — новое состояние, внутренняя память машины.

Пустая клетка таблицы означает, что такая пара «состояние + символ» в программе не задана. На экзамене до неё обычно не доходят, если следовать условию.

Состояние — это не «содержимое ленты». Лента — внешняя память, состояние — внутренняя. Одна и та же единица на ленте в q1 и в q2 обрабатывается разными командами.

Конспект

1. Найдите, где головка в начале и какое состояние. В демоверсии она часто стоит в ближайшей ячейке справа от последовательности, состояние q0.

2. Выполните 4–8 тактов на короткой ленте, например из четырёх символов. Рисуйте ленту и отмечайте головку стрелкой.

3. Сформулируйте словами, что делает машина: идёт влево и меняет нули на единицы до первой единицы, эту единицу гасит и останавливается, и тому подобное. Если фраза короткая и совпала с тактами — программа понята.

4. Дальше не моделируйте 1000 шагов. Примените правило к условию: сколько нулей останется, каким станет двоичное число, какое исходное число нулей максимально.

5. Разберите край: головка сразу видит λ, встречает сначала 1, в ленте нет нужной цифры. Краевые случаи часто и дают ответ.

6. Если спрашивают минимум или максимум исходного количества нулей, сначала опишите все ленты, которые после работы дают нужный результат, потом выберите экстремум.

Команда 0, L, q3 читается так: записать 0, сдвинуться влево, перейти в q3. Порядок именно такой: сначала запись, потом сдвиг.

Зачем не писать программу

Симулятор ниже годится только для тренировки на короткой ленте, чтобы сверить своё понимание таблицы. На экзамене перенос таблицы в код занимает дольше, чем ручной разбор, и одна перепутанная запятая даёт неверный ответ. ФИПИ рекомендует ручное исполнение.

# учебный симулятор, не для бланка экзамена
program = {
    ("q0", "λ"): ("λ", "L", "q1"),
    ("q1", "0"): ("1", "L", "q1"),
    ("q1", "1"): ("0", "N", "STOP"),
    ("q1", "λ"): ("λ", "N", "STOP"),
}

tape = {i: ch for i, ch in enumerate("1011")}
head = max(tape) + 1
state = "q0"
steps = 0
while state != "STOP" and steps < 10000:
    ch = tape.get(head, "λ")
    write, move, state = program[(state, ch)]
    tape[head] = write
    if move == "L":
        head -= 1
    elif move == "R":
        head += 1
    steps += 1

lo, hi = min(tape), max(tape)
print("".join(tape.get(i, "λ") for i in range(lo, hi + 1)))

Старый сюжет «Редактор», если попадётся в банке: пока в строке нашлось сочетание, заменяйте его. Цикл while и str.replace с лимитом 1. Следите, с начала строки или с конца ищет «нашлось».

Типичные ошибки

• Сдвиг сделали до записи символа.
• S приняли за «сдвиг», а не за останов.
• Пустой символ λ обработали как 0.
• Смоделировали только середину ленты и потеряли выход головки за край последовательности.