Анализировать программы для исполнителей и работать с моделью задания 12 — исполнителем «МТ» (машина Тьюринга) из демоверсии-2026.
Исполнители и машина Тьюринга
Классические исполнители и МТ в демоверсии-2026
В ЕГЭ по информатике встречаются задачи на анализ программ для формальных исполнителей. Классические исполнители — Робот (перемещается по клеточному полю, выполняет команды: вверх, вниз, влево, вправо, закрасить), Чертёжник (рисует отрезки на плоскости) и Редактор (работает со строкой символов). Главное — аккуратно трассировать каждый шаг программы, не пропуская ни одной команды.
В демоверсии-2026 задание 12 дано на исполнителя «МТ» (машина Тьюринга). МТ работает с бесконечной лентой, разбитой на ячейки. Каждая ячейка содержит символ или специальный символ λ (пустая ячейка). Головка в каждый момент стоит над одной ячейкой и находится в определённом состоянии (в демоверсии состояния обозначаются q0, q1 и т. д.).
Каждая команда МТ задаётся тройкой: [символ для записи в текущую ячейку], [действие], [новое состояние головки]. Действие может быть: L — сдвинуться влево, R — сдвинуться вправо, N — остаться на месте, S — остановиться после выполнения текущей команды. Программа МТ записывается в виде таблицы: в первой строке перечислены символы на ленте (включая λ), в первом столбце — состояния головки; строки данных соответствуют состояниям, столбцы — символам. На пересечении текущего состояния и текущего символа стоит команда.
Пример разбора. Пусть лента: λ 1 0 λ, головка над «1» в состоянии q0. Таблица: состояние q0, символ «1» → команда «0, R, q1» (записать 0, сдвинуться вправо, перейти в состояние q1). После выполнения: лента λ 0 0 λ, головка над «0» (бывшим средним), состояние q1. Следующая команда для символа «0» в состоянии q1 и т.д. Трассировка ведётся пошагово до команды с действием S (стоп после выполнения текущей команды).
Lesson notes
Классические исполнители и МТ в демоверсии-2026
В ЕГЭ по информатике встречаются задачи на анализ программ для формальных исполнителей. Классические исполнители — Робот (перемещается по клеточному полю, выполняет команды: вверх, вниз, влево, вправо, закрасить), Чертёжник (рисует отрезки на плоскости) и Редактор (работает со строкой символов). Главное — аккуратно трассировать каждый шаг программы, не пропуская ни одной команды.
В демоверсии-2026 задание 12 дано на исполнителя «МТ» (машина Тьюринга). МТ работает с бесконечной лентой, разбитой на ячейки. Каждая ячейка содержит символ или специальный символ λ (пустая ячейка). Головка в каждый момент стоит над одной ячейкой и находится в определённом состоянии (в демоверсии состояния обозначаются q0, q1 и т. д.).
Каждая команда МТ задаётся тройкой: [символ для записи в текущую ячейку], [действие], [новое состояние головки]. Действие может быть: L — сдвинуться влево, R — сдвинуться вправо, N — остаться на месте, S — остановиться после выполнения текущей команды. Программа МТ записывается в виде таблицы: в первой строке перечислены символы на ленте (включая λ), в первом столбце — состояния головки; строки данных соответствуют состояниям, столбцы — символам. На пересечении текущего состояния и текущего символа стоит команда.
Пример разбора. Пусть лента: λ 1 0 λ, головка над «1» в состоянии q0. Таблица: состояние q0, символ «1» → команда «0, R, q1» (записать 0, сдвинуться вправо, перейти в состояние q1). После выполнения: лента λ 0 0 λ, головка над «0» (бывшим средним), состояние q1. Следующая команда для символа «0» в состоянии q1 и т.д. Трассировка ведётся пошагово до команды с действием S (стоп после выполнения текущей команды).