В 2025 году разработчики ЕГЭ снова удивили выпускников: привычное задание №12 «Выполнение алгоритмов для исполнителя» полностью исчезло. На его месте появилось новое испытание — «Машина Тьюринга». Это звучит пугающе, но на самом деле всё не так страшно, если разобраться. В этой статье я расскажу, что именно изменилось, зачем в ЕГЭ ввели Машину Тьюринга и как теперь готовиться к этому заданию, чтобы не потерять баллы.
Задача №12 с ЕГЭ до 2026 года выглядела подобным образом:
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и и обозначают цепочки цифр.
заменить (v, w)
нашлось (v)
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (4555)
ЕСЛИ нашлось (25) ТО заменить (25, 4) КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (355) ТО заменить (355, 2) КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (4555) ТО заменить (4555, 3) КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке, в которой первая и последняя цифры - 3, а между ними стоит 100 цифр 5? В ответе запишите полученную строку.
Ответ: 453.
Задания такого формата стали для нас базой. Для решения требовалось буквально переписать код на язык Python. Условие менялось не сильно:
- найти наименьшее число «единиц», к примеру, которое могло быть в начальной строке;
- вывести полученную строку;
- подсчитать сумму цифр в получившейся строке;
- найти наименьшее количество цифр «два», при котором сумма цифр в получившейся строке будет равно 50 и т.д.
Задание много лет подряд было одинаковым и не доставляло труда для выпускников, которые легко забирали здесь свой первичный балл.
Но все изменилось с этого года! Помимо пакета программ Libre Office вместо Microsoft Office мы получаем принципиально новое задание, связанное с Машиной Тьюринга. Возможно, кто-то слышал о таком термине из известного фильма «Игра в имитацию», но речь не об этом.
Предлагаю разобраться вам в работе Машины Тьюринга на примере нового типажа заданий.
Пример задачи с сайта КЕГЭ от Евгения Джобса:
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов A={a0,a1,…,an–1}), включая специальный пустой символ a0.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний Q={q0,q1,…,qn–1}. В начальный момент времени головка находится в начальном состоянии q0.
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает j-й символ, находясь в i-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой.
Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «L», «R», «N», «S». Символы «L» и «R» означают сдвиг в левую или правую ячейки соответственно, «N» – отсутствие сдвига, «S» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.
Например, команда 0, L, q3 выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние q3.
Выполните задание
На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:
Известно, что количество символов 0 и 1 в исходной строке было одинаково, а сумма значений в исходной строке больше суммы значений в конечной строке на 200. Какое количество цифр 2 было в исходной строке?
Что мы получаем? Слишком длинное условие, но при этом оно крайне полезно. С помощью описания работы Машины Тьюринга мы можем понять принцип ее работы. Но предлагаю рассматривать рассмотреть все на рисунках, чтобы с большей точностью быть уверенным в понимании принципа работы Машины Тьюринга.
Чтобы рассмотреть все подробно, предлагаю для старта взять задачу попроще.
Теперь разложим всю картину по полочкам:
Лямбда слева и справа – пустые символы, между которыми расположено 1000 нулей. Головка расположена в ближайшей ячейке справа от последовательности, значит как раз на правой лямбде расположена головка (как показано на рисунке). При этом текущее состояние q0.
Теперь давайте разберем команды для различных состояний.
Для данной задачи у нас два состояния, каждое из которых имеет свою команду (поведение) в зависимости от элемента ячейки. Здесь все просто. Для каждого состояния мы имеем 3 параметра:
1) Элемент, который станет новым для ячейки, в которой стоит головка
2) Работа самой головки: перемещение влево/вправо на одну ячейку, либо же завершение работы, где L= Left (Влево), R= Right (Вправо), S= Stop (Конец, завершение), N= Not Rotate (Неподвижно, остается в той же ячейке)
3) Состояние головки (в этой задаче нам доступно 2 состояния головки)
Теперь давайте посмотрим на команды Машины Тьюринга при каждом из состояний головки:
- q0 – начальное состояние в начальном положении (ячейка пустого символа), тогда ячейка так и остается пустой, после чего головка двигается влево на 1 ячейку и переходит в состояние 1
- q1 – состояние головки при котором в зависимости от элемента в ячейке возможны разные команды:
- Если речь идет о пустом символе, то ячейка так и остается пустой, головка завершает свою работу, состояние остается таким же
- Если в ячейке находится единица, то вместо нее запишется ноль, программа завершается, состояние остается таким же
- Если в ячейке находится ноль, то вместо него запишется единица, головка двигается влево на одну ячейку, состояние головки остается прежним
Итог: программа нашей Машины меняет все нули на единицы, пока не наткнется на единицу, которая превратится в ноль, а программа завершится.
Как мы сказали, программа заменит все нули на единицы, а раз по условию у нас осталось 343 нуля и нам нужно как можно больше нулей, то аналитически мы можем сделать вывод, что для успешного выполнения задачи требуется 1 единица, которая имеет индекс 343. Почему именно 343? Индексация всегда начинается с нуля, а в нулевой ячейке у нас лежит пустой символ, именно поэтому ячейка с индексом 343 должна содержать в себе единицу. Начиная справа налево мы поменяем наши 657 нулей на единицы. И как только мы наткнемся на первую и единственную нашу единицу, согласно командам головки для нашего состояния, единица обратится в ноль, программа завершит свою работу и слева получается 343 нуля, что и требовалось по условию.
Ответ: 999
Как вы видите, решение обошлось лишь аналитикой и легкой математикой. Но это было лишь одна из самых легких задач. Переходите в мой телеграмм-канал, где скоро выйдет пост с полным разбором таких задач, как аналитическим методом, так и кодом на Python. Разберу все по полочкам.