Автор статьи: Андрей Рогов
Введение
В 2026 году в демоверсии ЕГЭ по информатике была представлена новая вариация задания № 12. Вместо привычного исполнителя «Редактор», работающего с символьными строками, предлагают использовать исполнителя МТ. Явно это не указывается, но из дальнейшего описания становится понятно, что речь идёт о машине Тьюринга.
Машина Тьюринга
Машина Тьюринга — умозрительное устройство, с помощью которого можно реализовать универсального исполнителя: модель вычислений, задающую способ описания алгоритмов и их выполнения. Машина Тьюринга — абстрактная математическая модель, требующая понимания формальных языков, теории алгоритмов и дискретной математики.
В школьном курсе информатики этот исполнитель изучается в теме «Теория алгоритмов» вместе с другими универсальными исполнителями: машиной Поста и нормальными алгоритмами Маркова. Подробно исполнители рассматриваются при углублённом изучении предмета — впрочем, у задания № 12 повышенный уровень сложности. Возможно, именно с этим связано подробное описание исполнителя в самом задании (две страницы — длиннее, чем любое другое задание КИМ ЕГЭ по информатике).
В состав исполнителя входит три основных элемента:
- Бесконечная лента, разделённая на ячейки, выполняющая роль памяти исполнителя
- Каретка, позволяющая читать и записывать данные в ячейки; в КИМ ЕГЭ называется головкой (устройство ввода-вывода информации)
- Программируемый автомат (процессор), способный выполнять команды
В ячейках ленты могут быть записаны символы из заранее определённого алфавита. Как правило, в алфавите всегда есть символ, обозначающий пустоту. В задании ЕГЭ это греческая буква лямбда — λ.
Помимо выполнения команд, автомат также может находиться в одном из заранее определённых состояний. Они тоже заранее определены и обозначаются q0, q1, … qn. Состояния играют роль подзадач, из которых состоит алгоритм.
Интересен способ записи алгоритма. Это таблица, в которой прописано, что должен делать исполнитель в каждом состоянии при различных символах ленты. Впрочем, все универсальные исполнители (машина Тьюринга, машина Поста, нормальные алгоритмы Маркова) уникальны по способу записи алгоритмов и отличаются от привычных нам языков программирования.
Машина Тьюринга — более сложный исполнитель, чем представленный ранее в заданиях ЕГЭ Редактор, она требует развитого абстрактного мышления. Вариант задания с Редактором хорошо решался с помощью программирования и шаблонного кода. К представленному в демоверсии заданию с машиной Тьюринга нельзя применить переборное решение без анализа алгоритма. Это, несомненно, шаг к усложнению задания, но есть и плюсы. Даже без детального изучения машины Тьюринга полезно понимать, что это:
- теоретическая основа компьютеров, любую программу можно представить как машину Тьюринга
- доказательство, что некоторые задачи принципиально нельзя решить алгоритмически (проблема остановки)
- мост между математикой и программированием
На сайте К. Ю. Полякова представлен тренажёр для изучения машины Тьюринга. Но его описание отличается от представленного в КИМ ЕГЭ (например, работа состояний: в КИМ ЕГЭ q0 — это начальное состояние, а остановка производится по команде S, тогда как у Полякова q0 — это конечное состояние, в котором производится остановка). С тренажёром, описание которого совпадает с КИМ ЕГЭ (кроме описания команд, в тренажёре оно в виде строк, а не таблицы) можно познакомиться на сайте devinf.ru/mt/.
Рассмотрим несколько примеров программ для машины Тьюринга.
Программа 1. Поиск начала числа
Программа для машины Тьюринга составляется исходя из начальных условий:
- алфавит (возможный набор символов)
- состояние ленты (какие символы записаны в ячейки)
- начальное расположение каретки (конкретное расположение или область — слева от символов, над ними или справа)
Определим алфавит А = {0, 1, λ}, где λ означает пустую ячейку. На ленте записано двоичное число. Каретка находится справа от числа, на неизвестном расстоянии от последней цифры. Необходимо переместить каретку к последней (правой) цифре числа. Будем сдвигать каретку влево до тех пор, пока не встретится цифра.
Изначально машина находится в состоянии q0. Встречая символ λ, каретка оставляет символ на ленте, сдвигается влево и остаётся в этом же состоянии. Встретив 0 или 1 (поскольку мы не знаем, какой цифрой оканчивается число), каретка запишет это же число в ячейке, и машина остановится.
Программа 2. Поиск начала числа
Каретка находится в произвольном месте над одной из цифр числа. Необходимо переместить каретку к последней (правой) цифре числа. Будем сдвигать каретку вправо до тех пор, пока не встретим символ λ. После этого необходимо сдвинуть каретку влево. Поскольку нельзя одновременно сделать это и остановить машину, добавим второе состояние, в котором машина будет просто останавливаться.
Программа 3. Увеличение двоичного числа на единицу
Начальная ситуация аналогична предыдущей задаче. Состояние q0 необходимо для перемещения каретки к последней цифре числа. В состоянии q1 будем производить добавление единицы. Напомним правила сложения в двоичной арифметике: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10.
Поскольку мы прибавляем единицу, нас интересуют два случая: 0 + 1 = 1, 1 + 1 = 10. Если на ленте встретится 0, достаточно записать вместо него единицу. Но если встретится единица, необходимо записать вместо неё 0 и продолжить выполнение программы, поскольку единица перейдёт в следующий разряд. Машина будет останавливаться в двух случаях: встретив ноль и записав вместо него единицу или встретив λ и записав в ячейку единицу. Последняя ситуация возможна, если в числе были только единицы.
Решение заданий ЕГЭ требует не только понимания логики работы машины Тьюринга, но и анализа результата работы алгоритма для различных начальных состояний.
Задача 1. Демоверсия-2026
Проанализируем, что будет происходить с лентой при различных начальных состояниях. Состояние q0 необходимо только для сдвига каретки к началу числа. Все основные действия происходят в состоянии q1. Возьмём сначала предельные случаи: на ленте только нули или только единицы.
Если на ленте записаны одни нули, то машина будет менять их на единицы. В итоге каретка сдвинется до начала числа и остановится. Если на ленте записаны только единицы, машина заменит правую из них на ноль и остановится. Если на ленте будет ровно одна единица, а остальные символы — нули, то машина заменит эту единицу на ноль и остановится. При этом все нули, стоящие справа от этой единицы, будут заменены единицами, но все символы слева останутся нетронутыми.
Мы проанализировали работу машины и знаем, как она будет себя вести при различных начальных состояниях. Теперь необходимо определить, как можно добиться ситуации, приведённой в условии задачи: чтобы после выполнения программы на ленте осталось ровно 343 нуля.
Согласно нашему анализу программы, на ленте может добавиться только один ноль — тот, которым заменяется самая правая единица. Но все нули, стоящие справа от самой правой единицы, будут заменены единицами. Если после завершения программы осталось 343 нуля, изначально их должно быть как минимум 342, поскольку ещё один ноль может добавиться. Но их может быть больше, если они стояли правее первой единицы.
Например, при начальном состоянии ленты 000111000 конечным состоянием будет 000110111. Правые нули заменились на единицы, а правая единица стала нулём. Если считать записанное число двоичным, была произведена операция вычитания единицы.
Для того чтобы сделать начальное количество нулей максимальным, можно взять такую начальную расстановку: 0.010.0, т. е. 342 нуля слева от единицы и 657 нулей справа, всего 999. Все правые нули заменятся на единицы, а единица заменится на ноль, после чего машина остановится. Нулей будет 342 в начале, и ещё один ноль получится из единицы, всего 343.
Задача 2
Начальное положение каретки — одна из цифр числа. Обратим внимание на состояние q0. Если каретка смотрит на одну из цифр, 0 или 1, происходит сдвиг вправо без изменения символа и состояния. И только когда каретка окажется на ячейке с символом λ, произойдёт переход в состояние q1, при этом каретка будет указывать на последнюю цифру числа. Состояние q0 перематывает каретку в правый конец числа.
Рассмотрим состояние q1. Остановка происходит, когда каретка смотрит на ячейку, в которой λ или 0. И тот, и другой символ заменяются на 1. А вот единицы заменяются на 0, но каретка сдвигается влево. Следовательно, все единицы, идущие подряд с конца числа заменятся нулями, а первый встреченный ноль или символ λ — единицей, и машина остановится. Можно заметить, что алгоритм представляет собой прибавление единицы в двоичной записи.
Добавиться может только одна единица. А удалить можно все единицы, стоящие правее первого нуля справа. Поскольку нам необходимо максимальное количество единиц, имеет смысл располагать их именно так. Если исходная последовательность будет иметь вид 1…101…1, то все единицы справа от нуля заменятся на нули, а 0 заменится на 1, после чего машина остановится. Для того чтобы после выполнения программы на ленте осталось 672 единицы, слева от нуля должна стоять 671 единица, а справа — 327, всего 999.
Задача 3
Состояние q0, как и в предыдущей задаче, переносит каретку, не меняя число, но на этот раз перенос происходит в левую часть. Остановка машины случится тогда, когда каретка будет смотреть на λ либо на 0. Все единицы сохранятся. Первый встреченный слева направо ноль заменится на единицу. Всё, что стоит справа от этого нуля, останется без изменений.
В отличие от предыдущих задач, вопрос касается не исходной последовательности, а итоговой. Предположим, что вся исходная последовательность состоит из нулей. В этом случае крайний левый ноль заменится единицей и машина остановится. В итоговой последовательности окажется 999 нулей. Сделать большее количество нулей невозможно.
Задача 4
Рассмотрим алгоритм. Состояние q0 необходимо для того, чтобы каретка передвинулась в ячейку над числом. В состоянии q1 каретка перемещается влево, при этом заменяя единицы на нули и наоборот. Следовательно, алгоритм инвертирует число. Двоичная запись числа 321 = 101000001₂, после инверсии станет 010111110₂. После перевода в десятичную систему счисления получаем число 190.
Задача 5
Алгоритм аналогичен алгоритму в предыдущей задаче, это инверсия числа.
После работы алгоритма число на ленте 123₁₀ = 1111011₂. Следовательно, до инверсии число выглядело как *0000100₂, звёздочкой обозначено ненулевое количество единиц. Необходимо найти число, в котором будет такое количество единиц в начале, чтобы число не превышало 3000. Для решения можно последовательно прибавлять единицы до тех пор, пока результат не превысит 3000. Это можно сделать вручную либо написать небольшую программу.
S = '0000100'
while int(s, 2) < 3000:
s = '1' + s
print(int(s, 2), s)
Вывод программы
132 10000100
388 110000100
900 1110000100
1924 11110000100
3972 111110000100
Наибольшим подходящим числом будет 1924.
Заключение
Анализ новой вариации задания № 12 ЕГЭ по информатике (демоверсия-2026) позволяет сделать ряд важных выводов о трансформации экзаменационного материала и требованиях к подготовке учащихся.
Вместо привычного исполнителя «Редактор» представлена машина Тьюринга. Это существенно повышает уровень сложности задания, переводя его в категорию задач, требующих не шаблонного программирования, а аналитического мышления и умения работать с абстрактными моделями. Задание перестало быть «переборным», для его решения необходимо проанализировать логику работы машины и спрогнозировать результат для различных начальных состояний ленты.
Рекомендуем рассмотреть простые варианты — все нули, все единицы и далее поставить один ноль или единицу — и проанализировать изменения. Таким образом, обновлённое задание № 12 не просто усложняет экзамен, но и актуализирует подготовку, смещая акцент с механического программирования на осмысление алгоритмических моделей — ключевую компетенцию IT-специалиста.
При подготовке к заданию рекомендуем использовать несколько способов решения для каждой задачи. Также полезно решить подборку задач для практики.