14 мин чтенияМТмашина Тьюрингазадание 12КЕГЭ 2026исполнитель

Исполнитель МТ (машина Тьюринга) — модель КЕГЭ 2026

Новая модель задания 12: лента, состояния, таблица команд L/R/N/S. Трассировка вручную и на Python.

Открываем тему…

Что такое исполнитель МТ

С 2026 года в задании 12 демоверсии ФИПИ используется исполнитель МТ — упрощённая машина Тьюринга. Головка движется по бесконечной ленте, разделённой на ячейки. В каждой ячейке — один символ алфавита, включая пустой символ (часто обозначают Λ, a₀ или пробел). Время дискретно: на каждом такте головка читает текущий символ, находясь в одном из состояний qᵢ, выполняет команду из таблицы и переходит в новое состояние.

Алфавит A = {a₀, a₁, …, aₙ₋₁}, где a₀ — пустой символ.
Состояния Q = {q₀, q₁, …}; старт обычно в q₀.
На каждом такте головка обозревает ровно одну ячейку.
Программа — таблица: строки — состояния, столбцы — символы; в клетке — команда.

Формат команды

Команда из трёх частей через запятую: «записываемый_символ, движение, новое_состояние». Движение: L — влево, R — вправо, N — остаться на месте, S — завершить работу после записи (стоп). Сначала пишется символ, потом сдвиг (если не S), потом смена состояния.

ПримерОдин такт

Головка в q₀ над символом 1, команда в клетке (q₀, 1): 0, R, q₁. Что произойдёт?

Решение

В текущую ячейку запишется 0, головка сдвинется вправо, состояние станет q₁.

ПримерСтоп

Команда 1, S, q₀ при состоянии q₂ над Λ. Чем закончится такт?

Решение

В ячейку пишется 1, затем исполнение завершается (S). Новое состояние после стопа уже не используется.

Как решать задание 12 с МТ

Выпишите начальную ленту (непустые символы) и позицию головки; отметьте состояние q₀.
Пока нет S: найдите клетку (текущее состояние, текущий символ) → выполните команду.
Ведите «кадр»: лента + позиция + состояние. Для длинных лент моделируйте на Python.
Ответьте на вопрос: итоговая запись, сумма цифр, число тактов, количество единиц и т.п.

ПримерКороткая трассировка

Алфавит {Λ, 0, 1}. Старт: лента Λ101Λ, головка на левой 1, состояние q₀. Таблица: (q₀,1)→0,R,q₀; (q₀,0)→0,R,q₀; (q₀,Λ)→Λ,N,S. Чему равна сумма цифр после остановки?

Решение

q₀ над 1: пишем 0, вправо → лента Λ001Λ, головка на 0. q₀ над 0: пишем 0, вправо → снова 0. q₀ над 1: пишем 0, вправо → Λ000Λ, головка на Λ. q₀ над Λ: Λ,N,S — стоп. Сумма цифр 0.

ПримерМодель на Python

Как смоделировать МТ программой?

Решение

tape = list('101'); pos = 0; state = 'q0' rules = {('q0','1'): ('0','R','q0'), ('q0','0'): ('0','R','q0'), ('q0','Λ'): ('Λ','S','q0')} while True: sym = tape[pos] if 0 <= pos < len(tape) else 'Λ' write, move, state = rules[(state, sym)] if 0 <= pos < len(tape): tape[pos] = write elif write != 'Λ': if pos < 0: tape = [write] + tape; pos = 0 else: tape.append(write) if move == 'S': break if move == 'R': pos += 1 elif move == 'L': pos -= 1 print(''.join(tape))

ПримерТипичная ловушка

Чем «чётное двоичное число» отличается от «двоичной записи с чётным числом единиц»?

Решение

Число 1110₂ чётное (оканчивается на 0), но единиц в записи три — нечётно. В заданиях на маски и МТ внимательно читайте, что именно требуется.

← Сортировки, поиск и оценка сложности Кластеризация и анализ данных (задание 27) →