О задании
В 2025/2026 учебном году задание 12 ЕГЭ по информатике заметно изменилось. Если раньше в нём фигурировал исполнитель Редактор, который просто заменял одни буквы другими в заданной строке, а решение сводилось к элементарному использованию строчного метода replace в Python.
Теперь подход полностью другой. Формально задание всё ещё связано с заменой символов в строке, но, по сути, это уже не Редактор в привычном виде. Вместо программирования требуется вручную пошагово моделировать работу абстрактной машины, фактически симулируя машину Тьюринга. Старые шаблонные решения на Python здесь больше не работают — задание решается только «на бумаге», через аккуратный разбор каждого шага алгоритма.
Поскольку появились эти задания совсем недавно, то у нас пока мало сведений для корректной типизации. Но тем не менее даже сейчас можно выделить два основных типа 12 заданий:
- В заданиях первого типа мы решаем «прямую задачу», то есть вычисляем результат работы алгоритма машины Тьюринга
- И как нетрудно догадаться в заданиях второго типа решается «обратная задача» — по данному результату работы алгоритма нужно найти исходное значение, которое было подано на вход
В свою очередь, эти два типа можем разделить еще на два, скажем так, «подтипа»:
- В первом случае предстоит найти двоичную запись какого-либо целого положительного числа
- Во втором случае же нужно найти количество единиц или нулей, поданных на вход алгоритма или получившихся в результате его работы
В целом, пока ничего сложного в решении этих заданий нет. И по опыту нововведений в прошлые года ЕГЭ можно сказать, что в этом, 2026, году 12 задания будут довольно простые и типовые. А дальше их ждёт все большее усложнение. Так что давайте уже сейчас научимся их решать и приступим к разбору алгоритма.
Алгоритм решения
Формат этой статьи будет несколько отличаться от предыдущих. Поскольку задание новое, то примеров для решения еще слишком мало. Мы в данной статье будем использовать только те, что были составлены авторами ЕГЭ и размещены в сборнике ЕГЭ по информатике за авторством Крылова С.С.
Так что здесь будет рассмотрено по одному заданию на каждый тип (расположены они будут не в предложенном выше порядке) и выведн базовый алгоритм действий, которые вам нужно предпринять в своих рассуждениях для успешного решения 12 задания.
Да, именно в рассуждениях, ведь здесь не будет никакого программного кода, и к верному ответу чаще всего мы будем приходить путём логических умозаключений.
Тип 1
Итак, перейдём уже к решению 12 заданий. Начнём с первого типа. Нумерация этого типа, конечно, довольно абстрактна. Просто это то задание, с которого будет проще погрузиться в данную тему. Здесь от нас потребуется найти исходное число, переданное на вход алгоритму машины Тьюринга.
Сразу отметим, что формулировка этих заданий просто огромная, в ней подробно описывается как работа самой машины, так и значения символов в таблице, по которой и строится программа этой машины. Здесь мы весь этот текст переписывать не будем, сосредоточимся на самом задании. А с работой машины Тьюринга вы можете познакомиться в прошлой статье.
«На ленте в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
После выполнения программы на ленте оказалась двоичная запись числа 88. Определите десятичное значение наименьшего числа, которое могло быть записано на ленте до начала работы программы.»
Начать следует, конечно, с самой программы, которая задана таблицей переходов. Вкратце пройдёмся по ней и научимся читать такие таблицы. Здесь все просто:
- Если головка указывает на пустую ячейку, обозначенную символом лямбда «λ», то происходит переход в состояние q1 и смещение влево.
- После смещения смотрим на символ, который расположен в этой ячейке. Если там 1, то заменяем его на 0 и двигаемся влево. Если же там 0, то заменяем на 1 и снова сдвигаемся влево.
- Это происходит до тех пор, пока мы снова не наткнёмся на пустую ячейку. Как только наткнулись на неё — программа завершается.
Таким образом, от начала и до конца всей числовой последовательности все единицы меняются на нули, а нули на единицы. Ничего не напоминает? Это же тот самый инвертор, который мы рассматривали в прошлой статье.
В таком случае давайте вспомним таблицу переходов, которую рассматривали тогда:
Согласитесь, она выглядит куда понятней? Но в тот раз головка машины Тьюринга у нас перемещалась вправо, и сначала не было никаких пустых символов. Давайте изменим таблицу согласно данному заданию.
У нас есть 4 действия:
- Если текущее состояние q0 и прочитан символ λ, то мы просто перемещаемся влево и меняем состояние на q1. Больше у q0 мы не вернёмся.
- Если текущее состояние q0 и прочитан символ 1, то заменяем его на 0, смещаемся влево и остаёмся в q1.
- Если текущее состояние q0 и прочитан символ 0, то заменяем его на 1, смещаемся влево и остаёмся в q1.
- Если текущее состояние q0 и прочитан символ λ, то останавливаем работу программы.
То есть от начала и до конца все цифры заменятся на противоположные: 0 на 1 и 1 на 0. Это уяснили, теперь переходим к самому заданию. После всех замен на ленте осталось число 88 в двоичном представлении. Сразу переведём его в двоичную систему, тут уже поступайте, как умеете — либо переводите вручную, либо через калькулятор, либо в Python. В любом случае вы получите результат 101 1000.
Теперь повернём время вспять и получим исходное число, которое должно было поступить на вход машины. Просто заменим 1 на 0 и 0 на 1: 010 0111.
Но в условии сказано, что ведущих нулей быть не должно, так что число 010 0111 не могло быть на ленте. Но какое тогда могло быть?
Очевидно, что перед первым нулём должна стоять какая-то из двух доступных нам цифр: 0 или 1. Ставить 0 не имеет смысла, значит, поставим 1: 1010 0111. Ведь при работе алгоритма эта «добавленная» единица все равно заменится на 0 и будет число 0101 1000 с ведущим нулём.
Но про ведущие нули в полученном числе в условии ничего не говорится. В условии четко сказано, что было получено число, десятичное значение которого 88. И сколько ведущих нулей ни добавляй, значение числа 88 в двоичной системе будет все тем же: 101 1000.
Значит, число 1010 0111 и является двоичной записью нашего ответа. Переведём его в десятичную и получим число 167, которое и запишем в ответ на это задание.
Тип 2
Теперь перейдём ко второму типу. Здесь от нас потребуется определить десятичное значение числа, двоичная запись которого оказалась на ленте машины Тьюринга после её работы. То есть теперь будем решать «обратную» задачу, представленной в прошлом примере. Но суть будет все та же: проанализировать таблицу переходов, понять алгоритм и применить его к двоичному значению данного в условии числа. Полученное таким образом двоичное число переводим в десятичную систему счисления и записываем в ответ.
Рассмотрим такую формулировку:
«На ленте в соседних ячейках записано двоичное представление числа 14 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
Определите десятичное значение числа на ленте после выполнения программы.»
Теперь у нас уже внушительная таблица сразу с четырьмя возможными состояниями. Давайте не будем её подробно разбирать, а просто будем действовать прямо по алгоритму: выписывать текущее состояние машины, смотреть на считанный символ и проводить операции по этой таблице.
Но для начала стоит перевести число 14 в двоичную систему счисления. Это будет число 1110. Здорово, всего 4 символа, давайте распишем по шагам работу алгоритма.
Изначально мы находимся в состоянии q0, и головка машины Тьюринга указывает на пустой символ — «λ».
По таблице переводим машину в состояние q1 и сдвигаем головку на одну ячейку влево.
Итак, мы в позиции q1 и считан символ 0. Ищем в таблице ячейку на пересечении строки q1 и столбца 0: «0, L, q3». Это значит, что символ 0 остаётся, состояние машины меняется на q3, и происходит сдвиг влево.
Теперь головка указывает на символ 1, а состояние машины q3. Ищем в таблице наше следующее действие: «1, L, q2». Снова оставляем число в ячейке таким же, меняем состояние машины на q2 и сдвигаемся влево.
Теперь смотрим в таблице на пересечение столбца 1 (сейчас головка указывает на ячейку с единицей) и строки с текущим состоянием — q2: «0, L, q3». Значит, меняем единицу на 0, состояние машины на q3 и сдвигаемся влево.
Снова состояние машины q3 и ячейка с единицей, порядок действий нам знаком: число оставляем, состояние меняем на q2 и сдвигаемся влево.
Теперь в ячейке, на которую указывает считывающая головка машины Тьюринга, пустой символ. Следовательно, пришло время завершить работу алгоритма. В итоге на ленте осталось число 1010.
Переводим его в десятичную систему счисления и получаем число 10. Его и запишем в ответ на это задание.
Тип 3
В следующих двух типах нам даётся последовательность из нескольких сотен нулей или единиц, записанных на ленте. Здесь уже не получится просто так симулировать работу машины Тьюринга и подсчитать на бумаге, что будет происходить с каждой ячейкой. Основной задачей будет выявить шаблон, по которому изменяются числа в последовательности.
То есть вам нужно увидеть определённые закономерности, которые указывают на цикличность работы алгоритма. Например, может быть так, что в итоговой последовательности повторяется какой-то шаблон из цифр: чередуются нули и единицы, чередуются тройки из единиц и нулей: «110 011 110 011» и так далее.
Начнём мы с заданий, в которых требуется определить количество нулей (единиц), которые остались на ленте после работы алгоритма. Рассмотрим такую формулировку:
«На ленте в соседних ячейках записана последовательность из 200 единиц. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
Определите число нулей на ленте после выполнения программы.»
Вам эта таблица не кажется знакомой? Да, это та же самая таблица, что была в прошлом примере. И мы уже знаем, как она работает.
Но давайте в ней получше разберёмся. Во-первых, уберём вообще столбец с нулём — у нас нет нулей по условию.
Во-вторых, сразу отметим, что первую единицу в последовательности мы оставим — потому что изначально машина находится в состоянии q1 и срабатывает команда «1, L, q2».
Далее нас перекидывает в q2, где 1 заменяется на 0 и состояние переключается на q3. В q3 единица остаётся, и состояние снова меняется на q2. И так продолжается до конца: у нас буквально будет чередование состояний q2 и q3, а следовательно, и единиц с нулями.
Здесь состояния машины отмечены цветом:
- Синим — состояние q1, в котором заменялась первая единица
- Оранжевым — q2, в котором единицы заменялись нулями
- Зелёным — q3, в котором единицы оставались единицами
Нетрудно выявить закономерность: у нас чередуются нули и единицы, а число символов в исходной последовательности чётное (200). Следовательно, в результате работы программы будет ровно 100 нулей и 100 единиц. Последовательность началась с единицы и закончилась нулём.
На этом решение завершено. Хоть мы и говорили в начале, что все 12 задания решаются только вручную, но если очень хочется, то можно написать программу на Python, которая симулирует работу этой машины Тьюринга. Заодно можно проверить себя. Выглядеть эта программа может так:
Подробно разбирать её мы не будем. Она буквально выполняет все команды, представленные в таблице переходов.
Что же, мы готовы дать ответ на это задание — число 100.
Тип 4
Ну и напоследок разберём самый сложный тип 12 заданий. Здесь нам нужно будет определить количество нулей (единиц) в исходной последовательности.
И все сложности заключаются именно в том, чтобы правильно понять алгоритм, по которому заменяются значения в последовательности. И решения многих заданий этого типа вам могут показаться слишком уже неправдоподобными. Как в детских загадках, ответ в которых лежит на поверхности, но ты пытаешься найти какой-то подвох. Далее вы поймёте, о чем идёт речь.
Формулировка у нас будет такая:
«На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 343 нуля. Определите максимально возможное число нулей в исходной последовательности.»
Внимательно посмотрите на таблицу. Программа у нас останавливается в двух случаях: когда считывает единицу или пустой символ. Второе нас не особо волнует.
И вся суть программы в замене нулей на единицу, пока на пути не встретится единица или пустой символ.
Что же получается, нам нужна всего одна единица здесь? И остальные 999 символов могут быть нулями?
Ну вообще да. И число 999 как раз и будет ответом. Но, как мы и говорили ранее, давайте найдём подвох — разберёмся почему достаточно лишь одной единицы.
Дело в том, что тут вся суть в том, на какой именно ячейке остановится программа. То есть если у нас будут все нули и одна единица, то программа будет «уничтожать» нули (заменяя их единицами) до тех пор, пока не наткнётся на ячейку с цифрой 1.
И в результате таких действий слева от этой единицы должно остаться ровно 342 нуля. Тогда мы получим, что после выполнения программы на ленте останется 343 нуля («левые» нули и единица, которая заменена на ноль) и 657 единиц.
Следовательно, единица должна быть на 658 ячейке (с правой стороны). Визуализировать эту последовательность можно так:
На этом мы и закончим разбор алгоритма решения 12 задания. В следующем году, скорее всего, появятся какие-либо новые формулировки или даже типы, и тогда мы снова вернёмся к этому заданию и дополним алгоритм.
Больше заданий данного типа с подробным решением вы можете найти в нашем тренажёре.