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