Каталог: Задание №12. Машина Тьюринга: пишем свой симулятор

Банк задач: 125 Формат ЕГЭ 2026 Повышенный (1 балл) 4-7 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №12

Тема кодификатора Исполнитель МТ: таблица состояний, лента, головка, перебор входных чисел

Сложность и баллы Повышенный (1 балл)

Рекомендуемое время 4-7 мин

Инструменты решения Python, Словарь table, while True, if / elif

На ленте записано двоичное число, головка стоит рядом, программа задана таблицей. Нужно узнать, что окажется на ленте, или подобрать исходное число. Записываем таблицу в словарь, пишем короткий цикл и перебираем числа.

Основные прототипы и разновидности

Тип 1: Что окажется на ленте

Дано число и программа. Запускаем симулятор и читаем результат.

Тип 2: Какое число было сначала

Известен результат или условие на него. Перебираем исходные числа и проверяем.

Тип 3: Сколько чисел подходит

Считаем, для скольких начальных чисел результат удовлетворяет условию. Тот же перебор, только вместо запоминания числа увеличиваем счётчик.

Теоретический фундамент и алгоритмы

Что от тебя хотят

У машины Тьюринга есть лента из ячеек, на ленте записаны символы (нули, единицы и пустое место λ), и есть головка, которая стоит над одной ячейкой. Ещё есть состояние (q1, q2, ...) и таблица программы. На каждом шаге машина смотрит на символ под головкой и на своё состояние и по таблице выполняет три действия.

Записывает новый символ в ячейку под головкой.
Сдвигает головку: L влево, R вправо, N остаётся, S останавливается.
Меняет состояние.

Как читать таблицу

Строки таблицы это состояния, столбцы это символы на ленте. В клетке записано три вещи: что писать, куда двигаться, в какое состояние перейти. Вот программа из досрочного ЕГЭ-2026, которая прибавляет единицу к двоичному числу (голова стоит справа от числа, на пустой ячейке):

	λ	0	1
q0	λ, L, q1
q1	1, L, q2	1, S, q1	0, L, q1
q2	λ, S, q2

В словаре Python каждая клетка превращается в одну запись: ключ это пара (состояние, символ), значение это тройка (что писать, куда двигаться, новое состояние).

Идея: один цикл вместо рисования ленты

Лента это список ячеек, головка это номер ячейки. Цикл повторяет три действия, пока не встретит S. Чтобы голова не вышла за край списка, ленту с обеих сторон «подкладываем» пустыми ячейками.

Порядок действий важен. Сначала запиши символ в текущую ячейку, и только потом сдвигай головку. Если сдвинуть до записи, ты перепишешь соседнюю ячейку.

Разбор 1: пошагово на числе 2047

На ленте записано двоичное представление числа 2047, головка стоит справа от него. Программа из таблицы выше. Какое число окажется на ленте после выполнения программы?

2047 это одиннадцать единиц подряд. Первое окно печатает ленту после каждого шага: головка идёт налево по единицам, превращая их в нули, доходит до пустой ячейки, пишет туда единицу и останавливается. Получается единица и одиннадцать нулей, то есть 2048: программа действительно прибавляет 1.

Разбор 2: подбор по условию

Другая программа: в q0 головка шагает влево с пустой ячейки, а в q1 каждый 0 меняет на 1, каждую 1 на 0 и идёт дальше влево, пока не дойдёт до λ. То есть она инвертирует все цифры.

После выполнения программы на ленте оказалась двоичная запись числа 156. Определите наибольшее число, меньшее 10000, которое могло быть записано на ленте до начала работы.

Запускаем программу для каждого числа от 1 до 9999, склеиваем ленту (выбрасываем λ) и переводим результат в десятичную систему. Если получилось 156, запоминаем число. Последнее запомненное и есть наибольшее: 8035. Проверка: 8035 это 1111101100011, после инверсии 0000010011100, ведущие нули не считаются, остаётся 156.

Условие вроде «найти наибольшее число меньше 10000» решается тем же перебором: запусти все числа, сохраняй подходящее и в конце выведи последнее.

Лайфхаки и фишки для ускорения

Совет

Головка стоит справа от числа, если в условии сказано «в ближайшей справа ячейке»: её номер это начало + длина числа.

Совет

Клетки таблицы без записи («—») в программе не встречаются. Если симулятор падает на KeyError, ты что-то переписал неверно.

Совет

Каждую клетку таблицы переписывай один раз и по порядку: строку за строкой. Перепутанная клетка самая частая ошибка.

Частые ошибки и экзаменационные ловушки

❌ Сдвинуть головку до записи
Символ запишется уже не в ту ячейку.

✅ Сначала tape[head] = new_symbol, потом сдвиг.

❌ Забыть сменить состояние
Машина останется в старом состоянии и пойдёт по другой строке таблицы.

✅ После записи всегда state = new_state.

❌ Писать if вместо elif в выборе движения
После head -= 1 следующий if может сработать ещё раз.

✅ Цепочка if / elif / elif: срабатывает ровно одна ветка.

❌ Не подложить пустые ячейки по краям
Головка уходит за левый край ленты, и Python падает или читает не с того конца.

✅ ["λ"] * 20 с обеих сторон: хватит любого числа шагов.

💀 ГРОБ №12: Длинная лента и большие числа

Числа в условии доходят до миллионов, и перебор в десять тысяч кажется слишком долгим.

Алгоритм решения: Симулятор работает за доли миллисекунды на число. Перебор до миллиона укладывается в несколько секунд, так что просто запусти его. Для этого лишнюю печать из цикла убери.

Практические задачи из банка КИМ (Всего: 125)

Решать в песочнице СмартКИМ

Задача #9127 №12 ЕГЭ

Каталог: Задание №12. Машина Тьюринга: пишем свой симулятор

Спецификация и суть задания №12

Основные прототипы и разновидности

Теоретический фундамент и алгоритмы

Что от тебя хотят

Как читать таблицу

Идея: один цикл вместо рисования ленты

Разбор 1: пошагово на числе 2047

Разбор 2: подбор по условию

Лайфхаки и фишки для ускорения

Частые ошибки и экзаменационные ловушки

Практические задачи из банка КИМ (Всего: 125)

Готовьтесь к ЕГЭ эффективно со СмартКИМ