Машина Тьюринга: лента, головка, правила

Зачем это в ЕГЭ.
Задание 12 проверяет умение анализировать работу машины Тьюринга. Даёт 1 первичный балл. Встречается практически в каждом варианте ЕГЭ, так как является одним из базовых вопросов по теории алгоритмов.

Главная идея.
Машина Тьюринга — это абстрактная модель вычислений, состоящая из бесконечной ленты, головки и набора команд. Ключ к решению — внимательно отслеживать состояние машины и её перемещения по ленте на каждом шаге.

Алгоритм (чеклист).
1. Прочитай начальное состояние ленты и положение головки.
2. Определи текущее состояние машины и символ под головкой.
3. Найди соответствующую команду в таблице переходов.
4. Выполни команду: запиши новый символ, измени состояние и перемести головку.
5. Повторяй шаги 2-4, пока машина не остановится.
6. Проверь результат: убедись, что машина остановилась в конечном состоянии.

Опоры (кратко).
- Машина Тьюринга: лента, головка, таблица переходов.
- Команда: $(q_i, a) \rightarrow (q_j, b, D)$, где $D$ — направление (L/R/S).
- Остановка машины: достигнуто конечное состояние или команда отсутствует.

Пример 1 (базовый подтип)
Шаг 1. Начальное состояние: лента "101", головка на первом символе, состояние $q_0$.
Шаг 2. Читаем символ "1" в состоянии $q_0$.
Шаг 3. Находим команду: $(q_0, 1) \rightarrow (q_1, 0, R)$.
Шаг 4. Записываем "0", переходим в состояние $q_1$, двигаем головку вправо.
Шаг 5. Читаем символ "0" в состоянии $q_1$.
Шаг 6. Находим команду: $(q_1, 0) \rightarrow (q_2, 1, S)$.
Шаг 7. Записываем "1", переходим в состояние $q_2$, останавливаемся.
Шаг 8. Результат: лента "001", машина остановилась в состоянии $q_2$.

Пример 2 (подтип с циклом)
Шаг 1. Начальное состояние: лента "111", головка на первом символе, состояние $q_0$.
Шаг 2. Читаем символ "1" в состоянии $q_0$.
Шаг 3. Находим команду: $(q_0, 1) \rightarrow (q_0, 0, R)$.
Шаг 4. Записываем "0", остаёмся в состоянии $q_0$, двигаем головку вправо.
Шаг 5. Читаем символ "1" в состоянии $q_0$.
Шаг 6. Повторяем команду: $(q_0, 1) \rightarrow (q_0, 0, R)$.
Шаг 7. Записываем "0", остаёмся в состоянии $q_0$, двигаем головку вправо.
Шаг 8. Читаем символ "1" в состоянии $q_0$.
Шаг 9. Повторяем команду: $(q_0, 1) \rightarrow (q_0, 0, R)$.
Шаг 10. Записываем "0", остаёмся в состоянии $q_0$, двигаем головку вправо.
Шаг 11. Машина выходит за пределы ленты, останавливается.
Шаг 12. Результат: лента "000", машина остановилась за пределами ленты.

Типичные ошибки.
1. Неверное направление движения головки. Путают "L" и "R".
2. Пропуск шагов. Не отслеживают каждый шаг машины.
3. Ошибка в конечном состоянии. Не проверяют, остановилась ли машина.
4. Неправильное чтение символа. Путают символы на ленте.
5. Неверная интерпретация команд. Неправильно применяют таблицу переходов.

Дальше.
Переходи к решению задач с более сложными таблицами переходов и циклами.