В новом задании № 12 нужно анализировать работу машины Тьюринга: следить за перемещением головки по ленте и понимать, как программа изменяет последовательность символов. В статье рассмотрим основные идеи и типовые задачи из ЕГЭ.
Термины, которые будем использовать: состояние, алгоритм исполнителя.
В чём смысл нового задания № 12
Машина Тьюринга — это математическая модель компьютера, придуманная ещё до того, как появились первые реальные ЭВМ. Представь бесконечную бумажную ленту, разделённую на ячейки. В каждой ячейке может быть записан какой-то символ (например, 0, 1, 2) или пустота (в заданиях ЕГЭ пустая ячейка обозначается греческой λ — «лямбда»).
По этой ленте двигается каретка (головка). Она умеет всего три вещи:
- Читать символ из ячейки, над которой стоит.
- Записывать в эту ячейку новый символ вместо старого.
- Сдвигаться на одну ячейку влево (L), вправо (R) или оставаться на месте (N).
В самом задании тебе дают таблицу (программу). Машина смотрит, в каком состоянии она находится (q0, q1 и так далее) и какой символ видит, а затем выполняет команду из таблицы.
Частые паттерны машины Тьюринга
Почти во всех задачах демоверсий и тренировочных вариантов прослеживаются одни и те же паттерны (шаблоны) поведения:
- Движение влево/вправо с заменой. Каретка встает с краю строки и идёт вглубь, превращая все 0 в 1. Как только она спотыкается о другой символ (например, 1 или пустоту), она либо меняет его на противоположный и останавливается, либо просто завершает работу.
- Пробег до ограничителя. Машина просто бежит по строке (например, вправо), ничего не меняя, пока не встретит нужный символ-ограничитель, чтобы там начать какую-то работу.
- Цепная реакция. Изменение одного символа запускает целую цепочку изменений.
Разбор типовых задач из ЕГЭ-2026
Разберём три главные разновидности этого задания. Программный код писать не будем — эти задачи великолепно решаются аналитически (в уме или на черновике).
Задача 1
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A={a0,a1,…,an–1}), включая специальный пустой символ a0.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q={q0,q1,…,qn–1}. В начальный момент времени головка находится в начальном состоянии q0.
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
| a0 | a1 | … | |
|---|---|---|---|
| q0 | команда | команда | … |
| q1 | команда | команда | … |
| … | … | … | … |
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце — возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ — состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми. Первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент — один из четырёх символов L, R, N, S. Символы L и R означают сдвиг в левую или правую ячейки соответственно, N — отсутствие сдвига, S — завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент — новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
Разберём команду: Строка 1, L, q1 для символа 0 означает «если видишь 0, замени его на 1, шагни ВЛЕВО (L) и останься в состоянии q1».
Как работает алгоритм. Каретка стоит справа и идёт влево. Пока она видит нули, она превращает их в единицы. Как только она встретит единицу, она заменит её на 0 и остановится (0, N, стоп). Если она дойдёт до пустоты (значит, единиц вообще не было), она просто остановится.
Анализируем результат. Нам нужно получить 343 нуля, при этом изначально была всего одна единица. Если каретка встретит единицу, эта единица превратится в ноль. Откуда возьмутся остальные 342 нуля? Они должны были остаться нетронутыми. Поскольку каретка шла справа налево, нетронутыми остаются только те нули, которые стояли левее единицы.
Составляем схему исходной строки:
Каретка идёт справа, превращает все X нулей в единицы, доходит до 1, превращает её в 0 и застывает. Итог: левые 342 нуля + один ноль на месте единицы = 343 нуля. Всё сходится!
Нам нужно максимальное количество нулей изначально, то есть нужно максимизировать X. Всего в строке 1000 символов. На левую часть и единицу уходит 342 + 1 = 343 символа. Значит, на долю правых нулей (X) остаётся максимум 1000 − 343 = 657 штук.
Всего нулей изначально: 342 (слева) + 657 (справа) = 999.
Ответ: 999.
Задача 2
На ленте исполнителя МТ в соседних ячейках записана последовательность из 800 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа работы исполнителя:
После выполнения программы на ленте оказалось, что в строке одинаковое количество чётных и нечётных цифр. Известно, что каждый из символов 0, 1 и 2 есть в исходной строке. Определите максимально возможное число единиц в исходной последовательности.
Перед нами есть четыре состояния: 0, 1, 2 и λ. Рассмотрим, как они взаимосвязаны:
- Все 0 будут заменяться на 2, затем шаг вправо.
- Все 1 будут заменяться на 2, затем шаг вправо.
- Все 2 будут заменяться на 1, затем шаг вправо.
В итоге исходные нули и единицы становятся двойками, а исходные двойки — единицами.
По условию в результате вышло равное количество чётных и нечётных чисел, то есть 400 единиц и 400 двоек. Кроме того, каждое число хотя бы раз встретилось в исходной строке. Тогда возьмём 399 единиц, один ноль и 400 двоек — это даёт максимум единиц при выполнении всех условий.
Ответ: 399.
Задача 3
На ленте в соседних ячейках записано двоичное представление числа 1097 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей слева к последовательности ячейке.
Программа работы исполнителя:
Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
По условию головка изначально стоит в пустой ячейке, ближайшей слева от числа, в состоянии q0.
Состояние q0. На символе λ выполняется команда λ, R, q1: головка оставляет пустоту, делает шаг вправо и переходит в q1. Теперь она стоит на самой первой (левой) единице числа.
Состояние q1.
- Для 0 выполняется 0, R, q1 (оставляет 0, идёт вправо).
- Для 1 выполняется 1, R, q1 (оставляет 1, идёт вправо).
Что это значит? Автомат просто пробегает всё число слева направо, ничего не меняя, пока не дойдёт до первой пустой ячейки λ справа от числа.
Наткнувшись на λ справа, автомат выполняет команду λ, L, q2 — оставляет пустоту, делает шаг влево (возвращается на самый последний, правый символ числа) и переходит в q2.
Состояние q2. Головка стоит на самом правом символе числа (у нас это 1).
И для 0, и для 1 команда одинаковая: λ, L, q3.
Что это значит? Автомат затирает последний символ (пишет вместо него λ), делает шаг влево (на предпоследний символ числа) и переходит в q3.
Состояние q3.
- Если видит 0, то выполняет λ, S, q3 (заменяет на λ и зависает на месте в бесконечном цикле).
- Если видит 1, то выполняет 1, S, q3 (оставляет 1 и зависает на месте в бесконечном цикле).
Посмотрим, что автомат сделал с числом 1097 = 100010010012:
- Прошёл до конца вправо.
- В состоянии q2 стёр последний символ (правую единицу).
- Сдвинулся влево на предпоследний символ (это 0).
- В состоянии q3 на этом нуле выполнил команду λ, S, q3, то есть стёр и этот ноль тоже, после чего остановился.
Таким образом, автомат просто отрезал два последних знака у исходного двоичного числа.
- Было: 100010010012.
- Стало: 1000100102.
В двоичной системе отбросить два последних знака — то же самое, что дважды поделить число на 2 нацело (то есть поделить на 4).
Переведём получившееся число обратно в десятичную систему:
100010010₂ = 256 + 16 + 2 = 274
(Или просто берём исходное число и делим нацело на 4: 1097 // 4 = 274).
Ответ: 274.
Задача 4
На ленте в соседних ячейках записано двоичное представление числа 2047 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.
Число 2047 в двоичной системе счисления — это 11 единиц подряд, так как 2047 — это 2 в 11-й степени минус 1. Строка на ленте выглядит как одиннадцать единиц.
В начальный момент головка находится в состоянии q0 на пустой ячейке λ справа от этого числа.
По команде для q0 и символа λ автомат выполняет λ, L, q1. Это означает, что он оставляет пустоту, сдвигается влево на самую правую единицу числа и переходит в состояние q1.
В состоянии q1 автомат обрабатывает само двоичное число, двигаясь справа налево. Для символа 1 выполняется команда 0, L, q1. То есть автомат превращает единицу в ноль и сдвигается левее, оставаясь в состоянии q1.
Поскольку наше число состоит только из единиц, автомат превратит самую первую встреченную правую единицу в ноль и сделает шаг влево. На следующей ячейке снова будет единица, он превратит её в ноль и опять шагнёт влево. Так он сделает со всеми одиннадцатью единицами исходного числа.
Когда автомат превратит последнюю левую единицу в ноль и сделает шаг влево, он окажется на пустой ячейке λ слева от числа.
Для символа λ в состоянии q1 прописана команда 1, L, q2. Это значит, что автомат запишет в эту пустую ячейку единицу, шагнет ещё левее и перейдёт в состояние q2.
В состоянии q2 на пустой ячейке λ срабатывает команда λ, S, q2, которая останавливает содержательную работу алгоритма.
В итоге все 11 единиц исходного числа превратились в нули, а слева от них на пустом месте записалась одна единица. Получилась двоичная строка, где идёт одна единица, а за ней 11 нулей.
Такая запись соответствует числу 2 в 11-й степени. Вычисляем это значение в десятичной системе: 2 в 11-й степени равно 2048.
Ответ: 2048.
Задача 5
На ленте исполнителя МТ в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей слева к последовательности ячейке.
Программа для исполнителя:
Определите наибольшее число, не превышающее 903, которое может получиться на ленте в результате работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
Сначала поймём, что программа делает со строкой. Возьмём произвольный пример и прогоним его по алгоритму: было: 0 0 0 1 1 1 0 → стало: 1 0 1 1 1 1 1 1 1 1 0.
Видно, что результат не зависит от конкретных цифр исходного числа. При любом наборе цифр все они заменяются на единицы, слева дописывается «1 0 1», а справа — «0».
Тогда начнём подбор количества единиц по центру, чтобы полученное число не превышало 903, но было максимально возможным: 1 0 1 1 1 1 1 1 1 0 = 776.
Ответ: 776.
Заключение
Задание № 12 почти всегда решается аналитически, без написания кода: достаточно понять по таблице, что делает автомат с каждым символом, и проследить его движение по ленте. Главное — аккуратно определить, откуда стартует головка и в какую сторону идёт, а затем выяснить общий эффект программы: что заменяется, что дописывается и где автомат останавливается. Дальше остаётся подставить нужное число или подобрать максимум по условию. Разобрав эти типовые шаблоны, ты сможешь быстро справляться практически с любым вариантом задания № 12.
Автор статьи
