Как решать задание 12 ЕГЭ по информатике — Машина Тьюринга
О чём задание
С 2026 года в задании 12 используется Машина Тьюринга — абстрактный исполнитель с лентой, головкой и набором правил (до этого здесь был исполнитель Редактор). Нужно проследить выполнение программы и определить результат: посчитать оставшиеся символы определённого типа, найти минимальное или максимальное значение, определить исходные данные по результату и т.д.
Как устроена Машина Тьюринга
- Лента — бесконечная последовательность ячеек, в каждой стоит символ из алфавита (обычно 0, 1 и пустой символ λ, но может включать и другие)
- Головка — указывает на текущую ячейку
- Состояния — машина находится в одном из состояний (q0, q1, q2, q3...)
- Таблица переходов — для каждой пары (состояние, символ) указано: что записать, куда сдвинуть головку (L/R/N), в какое состояние перейти
- Стоп — машина останавливается, когда в команде направление сдвига — S (завершение работы)
Типы вопросов
- Переведите результат в десятичную систему — на ленте остаётся двоичное число, нужно перевести
- Сколько цифр X осталось на ленте? — посчитать количество определённых символов
- Найдите сумму цифр на ленте — сложить все оставшиеся цифры
- Найдите минимальное/максимальное значение — при каком входе достигается нужный результат
Пошаговый алгоритм решения
Шаг 1: Пойми начальное состояние
- Где стоит головка? (слева или справа от последовательности)
- Какое начальное состояние? (обычно q0 или q1)
- Что записано на ленте?
Шаг 2: Составь таблицу трассировки
Создай табличку:
| Шаг | Состояние | Символ | Запись | Сдвиг | Новое состояние |
|---|---|---|---|---|---|
| 1 | q1 | 1 | 0 | R | q2 |
| 2 | q2 | 0 | 1 | R | q1 |
| ... | ... | ... | ... | ... | ... |
Шаг 3: Выполняй пошагово
На каждом шаге:
- Посмотри текущее состояние и символ под головкой
- Найди строку в таблице переходов
- Запиши новый символ в ячейку
- Сдвинь головку (L — влево, R — вправо, N — на месте)
- Перейди в новое состояние
- Если направление сдвига — S, остановись
Шаг 4: Прочитай результат
После остановки — посмотри, что осталось на ленте, и ответь на вопрос задачи.
Важно: последовательности длинные
В реальных задачах на ленте бывает от 600 до нескольких тысяч символов (часто 1000). Выполнять вручную каждый шаг невозможно. Нужно:
- Найти паттерн — после нескольких шагов часто видно закономерность (например, машина заменяет каждый второй символ)
- Понять алгоритм — что именно делает машина? Инвертирует? Сдвигает? Считает?
- Применить паттерн ко всей последовательности
Типичные ошибки
Ошибка 1: Потерял позицию головки. При трассировке обязательно отмечай, где стоит головка. Одна потерянная позиция — и весь дальнейший путь неверный.
Ошибка 2: Перепутал L и R. L — влево, R — вправо. Звучит очевидно, но под стрессом путают.
Ошибка 3: Не нашёл паттерн. Если после 10-15 шагов не видишь закономерность — попробуй сгруппировать шаги по состояниям: что происходит за один «цикл» работы машины?
Ошибка 4: Забыл про края ленты. Когда головка доходит до конца последовательности и встречает пустой символ (λ) — это отдельная строка в таблице переходов. Не пропускай её.
Сколько времени тратить
Задание 12 — повышенной сложности (1 балл). Если быстро нашёл паттерн — 5-7 минут. Если паттерн неочевиден — до 10 минут, потом лучше пропустить.
Тренировка
Машина Тьюринга — чисто алгоритмическое задание, и чем больше вариантов ты прорешаешь, тем быстрее видишь паттерны. В TuteMe есть задачи на разные типы Машин Тьюринга с автоматической трассировкой и подробным разбором.