Разбор задания №12 ЕГЭ по информатике 2026 (Машина Тьюринга)
Основные понятия
Машина Тьюринга работает по таблице переходов. Таблица содержит:
- Состояния (q0, q1, q2…)
- Символы на ленте (0, 1, λ — пустой символ)
- Действия при встрече символов
Структура таблицы переходов
Таблица выглядит так:
| Состояние/Символ | λ | 0 | 1 |
|---|---|---|---|
| q0 | действие | действие | действие |
| q1 | действие | действие | действие |
Что означает каждая ячейка таблицы
Каждое действие состоит из трёх частей:
- Какой символ записать
- Куда сдвинуть головку (L — влево, R — вправо, S — остаться)
- В какое состояние перейти
Пример записи: λ, L, q1 означает:
- Записать пустой символ
- Сдвинуться влево
- Перейти в состояние q1
Пошаговый алгоритм решения
- Анализ начальных условий
- Определить начальное состояние
- Найти начальную позицию головки
- Разбор таблицы переходов
- Для каждого состояния определить правила
- Выписать все возможные действия
- Моделирование работы
- Записать начальное состояние ленты
- Применить правила из таблицы
- Отслеживать изменения
Пример разбора таблицы
Рассмотрим таблицу:
| Состояние/Символ | λ | 0 | 1 |
|---|---|---|---|
| q0 | λ,L,q1 | 0,S,q1 | 1,L,q1 |
| q1 | стоп | 1,S,q1 | 0,L,q1 |
Разбор:
- В состоянии q0 при символе λ: записать λ, сдвиг влево, перейти в q1
- В состоянии q1 при символе 0: записать 1, остаться, остаться в q1
- При встрече стоп-состояния — завершение работы
Практический пример решения
Дано:
- Лента: 10001
- Начальное состояние: q0
- Головка справа
Решение:
- Читаем правый λ → действие из q0/λ
- Выполняем записанное действие
- Повторяем до стоп-состояния
Важные моменты при решении
- Внимательно читайте условие о начальной позиции
- Следите за состоянием головки
- Фиксируйте каждое изменение на ленте
- Проверяйте условия остановки
Типичные ошибки
- Неправильное определение начального состояния
- Путаница с направлениями движения
- Пропуск условий остановки
- Ошибки при записи промежуточных состояний
Совет
Решайте задачу пошагово, записывая каждое изменение состояния ленты и позиции головки. Это поможет избежать ошибок и найти правильный ответ.