Как решать задание 12 ЕГЭ по информатике — Машина Тьюринга

О чём задание

С 2026 года в задании 12 используется Машина Тьюринга — абстрактный исполнитель с лентой, головкой и набором правил (до этого здесь был исполнитель Редактор). Нужно проследить выполнение программы и определить результат: посчитать оставшиеся символы определённого типа, найти минимальное или максимальное значение, определить исходные данные по результату и т.д.

Это одно из самых заметных изменений в КЕГЭ 2026 — подробный обзор всех новшеств есть в статье ЕГЭ по информатике 2026 — что изменилось. Задание стоит 1 первичный балл и относится к повышенному уровню сложности. Всего в экзамене 27 заданий на 235 минут, так что задерживаться на одном номере долго нельзя.

Как устроена Машина Тьюринга

Машина Тьюринга — это математическая модель вычислений, придуманная Аланом Тьюрингом в 1936 году. Она формализует само понятие «алгоритма»: доказано, что всё, что можно вычислить, можно вычислить на Машине Тьюринга. В ЕГЭ от этой теории остаётся только механика — но полезно понимать, что ты имеешь дело с абстракцией, которая лежит в основе всей теоретической информатики.

Компоненты модели:

• Лента — бесконечная последовательность ячеек, в каждой стоит символ из алфавита (обычно 0, 1 и пустой символ λ, но может включать и другие — например, a, b, *)
• Головка — указывает на текущую ячейку, может читать и писать
• Состояния — машина находится в одном из состояний (q0, q1, q2, q3...). Количество состояний всегда конечно
• Таблица переходов — для каждой пары (состояние, символ) указано: что записать, куда сдвинуть головку (L/R/N), в какое состояние перейти
• Стоп — машина останавливается, когда в команде направление сдвига — S (завершение работы)

Логика такая: смотрим текущее состояние + символ под головкой → находим строку в таблице → записываем → сдвигаемся → меняем состояние → повторяем.

Типы вопросов

1. Переведите результат в десятичную систему — на ленте остаётся двоичное число, нужно перевести
2. Сколько цифр X осталось на ленте? — посчитать количество определённых символов
3. Найдите сумму цифр на ленте — сложить все оставшиеся цифры
4. Найдите минимальное/максимальное значение — при каком входе достигается нужный результат

Пошаговый алгоритм решения

Шаг 1: Пойми начальное состояние

• Где стоит головка? (слева или справа от последовательности)
• Какое начальное состояние? (обычно q0 или q1)
• Что записано на ленте?

Шаг 2: Составь таблицу трассировки

Создай табличку:

Шаг	Состояние	Символ	Запись	Сдвиг	Новое состояние
1	q1	1	0	R	q2
2	q2	0	1	R	q1
...	...	...	...	...	...

Шаг 3: Выполняй пошагово

На каждом шаге:

1. Посмотри текущее состояние и символ под головкой
2. Найди строку в таблице переходов
3. Запиши новый символ в ячейку
4. Сдвинь головку (L — влево, R — вправо, N — на месте)
5. Перейди в новое состояние
6. Если направление сдвига — S, остановись

Шаг 4: Прочитай результат

После остановки — посмотри, что осталось на ленте, и ответь на вопрос задачи.

Пример трассировки: инверсия битов

Пусть на ленте записано 101, головка стоит на первой единице, начальное состояние q1. Таблица переходов:

Состояние	Символ	→ Записать	Сдвиг	Новое состояние
q1	1	0	R	q1
q1	0	1	R	q1
q1	λ	λ	S	—

Трассировка:

Шаг	Лента	Позиция	Состояние	Действие
0	101	1 (на 1)	q1	старт
1	001	2 (на 0)	q1	записали 0, R
2	011	3 (на 1)	q1	записали 1, R
3	010	4 (на λ)	q1	записали 0, R
4	010	4	—	λ → S, стоп

Итог: 010 — инвертированная версия входа. Паттерн простой: машина идёт вправо и инвертирует каждый бит, пока не встретит пустую ячейку.

Типовые алгоритмы в заданиях ЕГЭ

В реальных задачах ты встретишь ограниченный набор «кирпичиков» — если узнаёшь их, решать становится в разы быстрее:

• Инвертирование битов — 0 меняется на 1, 1 на 0. Ровно как в примере выше
• Инкремент двоичного числа — машина идёт справа налево, меняет 1 на 0 (перенос), встретив 0 — ставит туда 1 и останавливается
• Сложение двух двоичных чисел — числа разделены спецсимволом, машина «переносит» разряды и складывает их
• Подсчёт единиц/нулей — машина стирает символы одного типа, оставляя на ленте только нужные
• Копирование последовательности — машина читает символ, идёт в конец ленты, записывает его копию, возвращается за следующим
• Перенос разряда — типичная подзадача при инкременте и сложении

Если видишь, что состояния q1 и q2 «бегают» туда-сюда — скорее всего, машина копирует или переносит данные.

Как находить паттерн

Состояния в задачах ЕГЭ обычно имеют смысл, даже если он не назван явно:

• Поисковое состояние — машина движется вправо или влево, пока не встретит нужный символ (например, границу или *)
• Состояние переноса — машина «несёт» информацию с одного конца ленты на другой
• Состояние записи — короткое состояние, в котором что-то записывается и сразу переход
• Завершающее состояние — приводит к команде с сдвигом S

Чтобы отловить цикл:

1. Выпиши первые 10-15 шагов в таблицу
2. Посмотри, не повторяется ли пара (состояние, символ) в «похожей» позиции
3. Если повторяется — ты нашёл один виток цикла, и вся оставшаяся работа машины — это повторение этого витка

Важно: последовательности длинные

В реальных задачах на ленте бывает от 600 до нескольких тысяч символов (часто 1000). Выполнять вручную каждый шаг невозможно. Нужно:

1. Найти паттерн — после нескольких шагов часто видно закономерность (например, машина заменяет каждый второй символ)
2. Понять алгоритм — что именно делает машина? Инвертирует? Сдвигает? Считает?
3. Применить паттерн ко всей последовательности
4. Посчитать символы — если на ленте 600 нулей и 400 единиц, а машина «стирает» все единицы, то ответ: 600

Пример техники подсчёта: если в условии написано, что на ленте 1000 символов — 450 нулей, 550 единиц — и машина превращает 01 в 11, то после её работы нулей станет меньше ровно на столько, сколько пар 01 было в исходной строке. Часто задача сводится к арифметике без ручной трассировки.

Python для проверки

Дома полезно написать мини-симулятор, чтобы быстро сверять ручные трассировки с эталоном. Простейший вариант:

def turing(tape, start_state, head, rules):
    tape = list(tape)
    state = start_state
    steps = 0
    while steps < 100_000:
        symbol = tape[head] if 0 <= head < len(tape) else 'λ'
        if (state, symbol) not in rules:
            break
        write, move, new_state = rules[(state, symbol)]
        if 0 <= head < len(tape):
            tape[head] = write
        if move == 'L': head -= 1
        elif move == 'R': head += 1
        elif move == 'S': break
        state = new_state
        steps += 1
    return ''.join(tape), steps

rules = {
    ('q1', '1'): ('0', 'R', 'q1'),
    ('q1', '0'): ('1', 'R', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
}
print(turing('101', 'q1', 0, rules))  # ('010', 4)

Если ты пока не уверен, стоит ли писать такие штуки на Python или лучше перейти на C++, посмотри статью Python или C++ для ЕГЭ — для задания 12 Python хватает за глаза.

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

Ошибка 1: Потерял позицию головки. При трассировке обязательно отмечай, где стоит головка. Одна потерянная позиция — и весь дальнейший путь неверный.

Ошибка 2: Перепутал L и R. L — влево, R — вправо. Звучит очевидно, но под стрессом путают.

Ошибка 3: Не нашёл паттерн. Если после 10-15 шагов не видишь закономерность — попробуй сгруппировать шаги по состояниям: что происходит за один «цикл» работы машины?

Ошибка 4: Забыл про края ленты. Когда головка доходит до конца последовательности и встречает пустой символ (λ) — это отдельная строка в таблице переходов. Не пропускай её.

Подборка других распространённых промахов, из-за которых теряют баллы даже сильные ученики, — в статье Топ-5 ошибок на ЕГЭ по информатике.

Сколько времени тратить

Задание 12 — повышенной сложности (1 балл). Если быстро нашёл паттерн — 5-7 минут. Если паттерн неочевиден — до 10 минут, потом лучше пропустить и вернуться в конце.

Как тренироваться

• Сначала короткие ленты. Сделай 10-15 задач с лентой на 5-10 символов. Цель — научиться безошибочно читать таблицу переходов
• Потом — поиск паттерна. Переходи к лентам из 50-100 символов и тренируйся видеть цикл после 5-10 шагов
• Затем — длинные ленты. Задачи с лентой на 1000 символов, где решение сводится к формуле по количеству символов
• В финале — разные алгоритмы. Инвертирование, инкремент, сложение, копирование — пройди все типовые сценарии

Машина Тьюринга — чисто алгоритмическое задание, и чем больше вариантов ты прорешаешь, тем быстрее видишь паттерны. Если совсем с нуля — начни с пошагового плана подготовки. В TuteMe есть задачи на разные типы Машин Тьюринга с автоматической трассировкой и подробным разбором.

Попробовать бесплатно →