В демоверсии ЕГЭ 2026 года появилась новая модель задания 12. Раньше здесь работал исполнитель Редактор: он заменял одни фрагменты строки другими, а решение часто сводилось к методу replace в Python.
Теперь перед нами машина Тьюринга. Формально она тоже меняет символы, но делает это совсем иначе: видит только одну ячейку ленты, выполняет одну команду и передвигает головку на один шаг.
На первый взгляд такая таблица выглядит серьёзно. Состояния q0, q1, q2, стрелки, пустой символ λ — кажется, будто нужно сразу удерживать в голове всю программу. На самом деле этого не требуется.
В каждый момент нас интересуют только две вещи: текущее состояние машины и символ прямо под головкой. Они указывают на одну ячейку таблицы, а в ней уже записано следующее действие.
Поэтому задание 12 — не про «накидать шаблонный код и решить». Здесь важнее спокойно пройти алгоритм шаг за шагом и не потерять состояние машины. Зачастую нескольких первых шагов достаточно, чтобы увидеть всю закономерность.
Все встречающиеся формулировки удобно разделить сначала на две большие группы:
В прямой задаче известна исходная лента, а нам нужно определить результат работы машины.
В обратной задаче известен результат, а мы восстанавливаем исходную запись или количество символов в ней.
Внутри этих групп встречаются задачи либо на двоичное число, либо на количество нулей и единиц. Так и получаются четыре практических типа, которые мы разберём в этой статье.
Тип 1. По известному результату восстановить наименьшее или наибольшее исходное число.
Тип 2. По заданному числу определить содержимое ленты после выполнения программы.
Тип 3. Для длинной одинаковой последовательности найти количество нулей или единиц в результате.
Тип 4. По условию о результате восстановить максимальное или минимальное количество символов в исходной последовательности.
Названия типов здесь условные. Гораздо важнее не запомнить номер, а понять, движемся мы от исходной ленты к результату или пытаемся восстановить исходную ленту по результату.
Как читать одну команду
Перед большим разбором давайте потренируемся на одной ячейке таблицы. Допустим, машина находится в состоянии q2, под головкой записана единица, а в таблице стоит команда «0, L, q3».
Читаем её слева направо. Сначала вместо единицы записываем 0. Затем буква L велит передвинуть головку на одну ячейку влево. После этого машина переходит в состояние q3.
Если бы вместо L стояла буква R, головка пошла бы вправо. Буква S в рассматриваемых заданиях означает остановку: новый символ записывается, но следующего шага уже не будет.
Пустой символ λ — тоже полноценный символ таблицы. Именно по нему машина понимает, что дошла до края записи. Поэтому пустые ячейки слева и справа от числа нельзя мысленно отбрасывать.
И ещё один важный момент: состояние относится не ко всей строке, а к текущему шагу. После перехода в q3 следующую команду мы ищем уже в строке q3, даже если головка оказалась над такой же единицей.
Алгоритм решения
Формат этой статьи немного отличается от привычных разборов с готовым кодом. Машину Тьюринга прежде всего нужно понять вручную, поэтому основная работа будет происходить в наших рассуждениях.
Перед каждым примером действуем по одному и тому же плану:
Выписываем исходную ленту (не все 100+ символов, естественно), начальное состояние и положение головки. Не забываем о пустых ячейках λ по краям.
Смотрим, какой символ сейчас находится под головкой, и находим его столбец в таблице.
Находим строку текущего состояния. На пересечении строки и столбца получаем единственную нужную нам команду.
Выполняем команду по порядку: записываем новый символ, двигаем головку, меняем состояние или останавливаемся.
Для короткой ленты рисуем следующий шаг полностью. Для длинной выполняем несколько шагов и ищем повторяющийся цикл.
После остановки отдельно проверяем нетронутую часть ленты и только потом переводим двоичное число или считаем символы, в зависимости от условия задания.
Если лента короткая, не пытайтесь угадывать результат по таблице целиком. Четыре–пять аккуратно нарисованных состояний обычно надёжнее одного слишком быстрого рассуждения.
Если же на ленте сотни символов, полная трассировка бессмысленна. Тогда первые шаги нужны нам как эксперимент: по ним мы замечаем блок, который дальше повторяется без изменений (тот самый цикл).
Тип 1
Итак, перейдём к первому типу. Начнём с обратной задачи: результат работы машины уже известен, а нам нужно восстановить наименьшее число, которое могло находиться на ленте до запуска.
Полное описание машины в условии обычно занимает много места. Это нормально: значительная часть текста просто напоминает устройство ленты и обозначения. Нам же прежде всего нужна таблица переходов.
На ленте в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
λ
1
0
q0
λ, L, q1
q1
λ, S, q1
0, L, q1
1, L, q1
После выполнения программы на ленте оказалась двоичная запись числа 88. Определите десятичное значение наименьшего числа, которое могло быть записано на ленте до начала работы программы.
Начать стоит, конечно, с самой программы машины Тьюринга. Давайте переведём таблицу на обычный язык и посмотрим, что она делает с записью:
Если машина находится в q0 и видит справа от числа пустую ячейку λ, она оставляет λ, сдвигается влево и переходит в q1.
В состоянии q1 единица заменяется нулём, после чего головка движется влево и остаётся в q1.
В состоянии q1 ноль заменяется единицей. Головка снова движется влево, а состояние не меняется.
Когда в состоянии q1 машина встречает пустую ячейку λ слева от числа, программа останавливается.
Получается знакомый по прошлой статье инвертор: он проходит запись справа налево и заменяет каждую цифру на противоположную. Нули становятся единицами, а единицы — нулями.
В предыдущей статье мы рассматривали похожую таблицу, только головка двигалась слева направо:
Согласитесь, в таком виде идея заметнее. В текущей задаче направление другое и перед первым шагом машина стоит на пустой ячейке, поэтому таблица выглядит так:
Теперь уже можно не следить за каждой цифрой отдельно. Мы поняли общий смысл программы: вся двоичная запись инвертируется. Осталось аккуратно применить это правило в обратную сторону.
После работы на ленте находится двоичная запись числа 88. Переводим число в двоичную систему и получаем 1011000₂.
Если просто инвертировать семь цифр, получится 0100111. Но такая строка не может быть исходной записью положительного числа: по условию перед первой значащей единицей не должно быть ведущего нуля.
На этом месте легко решить, что подходящего входа вообще нет. Но давайте вспомним, что в условии дано числовое значение результата, а не точное количество занятых ячеек.
Строки 1011000 и 01011000 обозначают одно и то же число 88. Ведущий ноль не меняет значение результата, зато после обратной инверсии он превратится в значащую единицу.
Добавляем к результату один ведущий ноль: 01011000. Инвертируем все восемь цифр и получаем исходную запись 10100111.
Почему добавляем именно один ноль? Нам нужно наименьшее исходное число. Без дополнительного нуля запись недопустима, а каждый следующий ведущий ноль после инверсии даст ещё одну единицу слева и сделает число больше.
Теперь решим прямую задачу. Исходное число известно, поэтому ничего восстанавливать назад не нужно: запускаем машину в начальном состоянии и честно проходим программу до остановки.
Общий принцип тот же: проанализировать таблицу переходов, понять алгоритм и применить его к двоичному значению данного в условии числа. Здесь особенно полезно не смотреть на неё целиком, а каждый раз задавать себе два вопроса: в каком мы состоянии и какой символ видит головка?
На ленте в соседних ячейках записано двоичное представление числа 14 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
λ
1
0
q0
λ, L, q1
q1
1, L, q2
0, L, q3
q2
λ, S, q2
0, L, q3
1, L, q2
q3
λ, S, q3
1, L, q2
0, L, q3
Определите десятичное значение числа на ленте после выполнения программы.
Сначала переводим 14 в двоичную систему: 1110₂. Здорово, символов всего четыре, поэтому можем без спешки расписать каждый шаг и заодно потренироваться читать таблицу.
Вначале машина находится в состоянии q0, а головка указывает на пустую ячейку λ справа от числа.
На пересечении q0 и λ видим команду перехода в q1 со сдвигом влево. Пустая ячейка остаётся пустой, а головка перемещается к последнему нулю числа 1110.
Теперь состояние q1, под головкой 0. Команда «0, L, q3» оставляет ноль без изменений, передвигает головку влево и переводит машину в q3.
Головка оказалась над единицей, а состояние стало q3. В ячейке q3 + 1 записано «1, L, q2»: единица сохраняется, затем переходим на одну ячейку влево и меняем состояние на q2.
Снова видим единицу, но состояние уже другое — q2. Поэтому команда тоже другая: «0, L, q3». Единицу заменяем нулём, двигаемся влево и возвращаемся в q3.
Осталась крайняя левая единица. В состоянии q3 она не меняется: выполняется команда «1, L, q2». После сдвига головка впервые выходит за пределы числа.
Под головкой теперь пустой символ λ, текущее состояние — q2. Соответствующая команда завершает работу программы. Больше ни одна ячейка не изменится.
Прочитаем результат слева направо: 1010₂. Переводим его в десятичную систему и получаем 8 + 2 = 10. Ответ: 10.
Обратите внимание, что одинаковая единица в двух соседних ячейках обрабатывалась по-разному. Причина только в состоянии машины: сначала было q3, затем q2. Именно поэтому состояния нельзя пропускать в записи решения.
Тип 3
В следующих задачах на ленте уже не четыре символа, а несколько сотен одинаковых нулей или единиц. Рисовать сотни шагов мы, конечно, не будем. Теперь наша цель — заметить цикл.
Цикл появляется, когда после нескольких переходов машина возвращается к уже знакомому исходному состоянию и снова видит такой же символ. Дальше тот же набор команд начнёт повторяться.
Например, если в состоянии q2 единица превращается в 0 и машина переходит в q3, а в q3 следующая единица сохраняется и возвращает нас в q2, каждая пара исходных единиц даст один ноль.
Сначала проверяем этот вывод на двух-трёх парах, а уже потом переносим его на всю длинную последовательность. Так мы не угадываем закономерность, а действительно выводим её из таблицы.
Таблица вам уже знакома: это та же программа, которую мы только что проследили для числа 14. Но теперь исходная лента состоит исключительно из единиц.
Значит, столбец 0 во время обработки самой последовательности вообще не используется. Он есть в таблице, но ни разу не понадобится: машине просто не встретится исходный ноль.
Первую справа единицу машина читает в состоянии q1. Команда «1, L, q2» оставляет её единицей и переводит машину в q2.
Следующую единицу машина видит уже в q2, поэтому заменяет её нулём и переходит в q3. Третью единицу состояние q3 оставляет без изменений и снова возвращает нас в q2.
Дальше повторяется одна и та же пара действий: q2 создаёт ноль, q3 сохраняет единицу. Вот он, нужный нам цикл длины два шага.
На рисунке состояния отмечены цветом:
синим — q1, в котором первая справа единица осталась единицей;
оранжевым — q2, в котором очередная единица заменяется нулём;
зелёным — q3, в котором единица сохраняется.
В каждой обработанной паре символов появляется ровно один ноль. Число 200 чётное, поэтому вся последовательность делится на 100 пар: 200 / 2 = 100.
Следовательно, после работы на ленте будет 100 нулей и 100 единиц. Ответ: 100.
А что было бы при 201 единице? Тогда получили бы 100 полных пар и ещё один крайний символ. Его пришлось бы разобрать отдельно по состоянию, которое осталось после сотой пары.
Это полезное правило для любых циклов: сначала считаем полные блоки, затем обязательно проверяем остаток. Если длина делится на размер блока без остатка, дополнительного шага нет.
На экзамене такой пример быстрее решается вручную. Но при желании рассуждение можно проверить небольшой программой, которая повторяет именно найденный нами цикл:
tape = list('1' * 200)
state = 'q1'
for i in range(199, -1, -1):
if state == 'q1':
tape[i] = '1'
state = 'q2'
elif state == 'q2':
tape[i] = '0'
state = 'q3'
elif state == 'q3':
tape[i] = '1'
state = 'q2'
print(tape)
print(f"Количество нулей: {tape.count('0')}")
Цикл range идёт по индексам справа налево, потому что именно так движется головка. Переменная state хранит текущее состояние, а список tape играет роль ленты.
Эта программа не заменяет разбор таблицы. Сначала мы поняли закономерность вручную, а затем записали её в коде. Если таблица изменится, ветви программы тоже придётся составлять заново.
Тип 4
Ну и напоследок разберём самый хитрый тип. Здесь известен результат работы, а найти нужно максимальное или минимальное количество нулей либо единиц в исходной последовательности.
Такие задачи иногда напоминают детскую загадку: ответ оказывается очень простым, но мы долго ищем скрытый подвох. Чтобы не гадать, выясним, какую часть ленты машина вообще успевает изменить.
На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
λ
1
0
q0
λ, L, q1
q1
λ, S, q1
0, S, q1
1, L, q1
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.
Сначала разберём таблицу. В состоянии q1 машина меняет каждый встреченный ноль на единицу и продолжает двигаться влево.
Как только под головкой появляется единица, машина записывает вместо неё 0 и останавливается. Команда с S не означает «ничего не делать»: символ сначала меняется, и только после этого работа завершается.
Если единицы на ленте вообще нет, машина заменит все 1000 нулей единицами и остановится на пустой ячейке слева. Тогда в результате не останется ни одного нуля, а по условию их должно быть 343.
Значит, хотя бы одна единица в исходной последовательности обязательна. А раз требуется максимальное число нулей, попробуем оставить ровно одну единицу и заполнить нулями остальные 999 ячеек.
Осталось подобрать положение этой единственной единицы. Машина идёт справа налево, поэтому все нули справа от неё превратятся в единицы. Нули слева машина вообще не успеет затронуть.
Сама единица при встрече превратится в новый ноль. Значит, итоговое количество нулей складывается из нетронутых нулей слева и одного нуля, появившегося на месте единицы.
Нам нужно получить 343 нуля. Один из них создаёт машина, следовательно, слева от единственной единицы должны оставаться ещё 342 нуля.
Всего на ленте 1000 ячеек: 342 нуля слева, затем одна единица и 657 нулей справа. Проверяем сумму: 342 + 1 + 657 = 1000.
Во время работы 657 правых нулей станут единицами, исходная единица станет нулём, а 342 левых нуля сохранятся. В результате получим ровно 342 + 1 = 343 нуля.
Если считать ячейки справа налево, единственная единица находится на 658-м месте: перед ней по ходу движения расположены 657 нулей.
В исходной последовательности было 342 + 657 = 999 нулей. Больше получить нельзя, потому что вариант из 1000 нулей не удовлетворяет условию результата. Ответ: 999.
Итоги
Мы разобрали четыре формулировки нового задания 12, но во всех них машина работает одинаково: читает один символ в одном состоянии и выполняет одну команду из таблицы.
На короткой ленте лучше не торопиться и сделать полную трассировку. Записывайте состояние рядом с головкой: одна и та же цифра в q2 и q3 может привести к совершенно разным действиям.
На длинной ленте выполните несколько шагов и найдите цикл. Посчитайте, сколько полных блоков помещается в последовательности, а затем отдельно разберите остаток.
В обратных задачах следите за тем, что именно дано: точная строка или числовое значение. Ведущий ноль не меняет значение двоичного числа, но после инверсии может превратиться в значащую единицу.
В задачах на максимум или минимум сначала определите место остановки. Всё, что находится дальше него, машина не затронет, и именно эта нетронутая часть часто позволяет получить наибольший ответ.
Всегда проверяйте три момента: в каком состоянии находится машина, какой символ сейчас под головкой и успела ли выполниться замена перед остановкой. Большинство ошибок возникает именно здесь.
На этом мы закончили разбор основных типов задания 12 ЕГЭ по информатике. Попрактиковаться в чтении таблиц переходов и трассировке машины Тьюринга можно в нашем тренажёре.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
