Задание 12 ЕГЭ: машина Тьюринга и исполнитель Редактор — гайд с примерами

Что проверяет задание

Задание 12 проверяет умение формально выполнять алгоритм, заданный для абстрактного исполнителя, шаг за шагом, без ошибок в трактовке правил. В экзамене встречаются два основных исполнителя: машина Тьюринга (МТ) и исполнитель Редактор, работающий со строками символов. Задание проверяет не знание «хитрых» формул, а способность аккуратно смоделировать работу программы, увидеть закономерность в её поведении и применить эту закономерность к большим объёмам данных, которые невозможно протрассировать полностью вручную.

Как выглядит формулировка и сколько баллов

Задание находится в части 1, оценивается в 1 балл, ответ — целое число, калькулятор не нужен, но нужна аккуратность. Условие почти всегда содержит: полное описание правил исполнителя (алфавит, состояния, формат команды), иллюстративный пример работы программы на маленькой ленте или строке, и собственно вопрос: дана лента/строка большой длины (сотни-тысячи символов), известен результат после выполнения программы, требуется найти характеристику исходных данных — максимальное или минимальное количество символов определённого вида. Программа исполнителя из года в год похожа почти буквально, меняются только числа, поэтому важно один раз разобраться в логике конкретного шаблона.

Что нужно знать

Машина Тьюринга:

• Алфавит $A=\{a_0,a_1,\dots,a_{n-1}\}$, где $a_0=\lambda$ — пустой символ.
• Множество состояний $Q=\{q_0,q_1,\dots,q_{m-1}\}$, начальное состояние всегда $q_0$.
• Команда в ячейке таблицы — тройка (записываемый символ; сдвиг $L/R/N$; новое состояние); команда с завершением помечается $S$.
• Порядок символов в заголовке таблицы совпадает с порядком, в котором алфавит перечислен в условии (например $\lambda,1,0$, а не привычные $\lambda,0,1$) — это нужно проверять каждый раз.
• Сдвиг головки происходит после записи символа в текущую ячейку.
• Работа завершается только по команде с символом $S$.

Исполнитель Редактор:

• Хранит одну строку символов; программа состоит из команд «заменить (a, b)» — заменить первое найденное вхождение подстроки $a$ на $b$, и логической проверки «нашлось(a)».
• Типичная конструкция: ПОКА нашлось(a) ЗАМЕНИТЬ (a, b) — выполняется, пока подстрока $a$ встречается в строке.
• Замена всегда происходит по самому левому вхождению, после чего поиск начинается заново с начала строки.

Общее: задачи почти всегда просят связать длину/состав исходных данных с длиной/составом результата через одну переменную-параметр (например, длину серии одинаковых символов у края последовательности); итоговый ответ — целое число, значит все промежуточные величины должны быть целыми.

Методы решения

1. Пошаговая трассировка. Подходит для понимания правила работы программы. Берём короткую ленту, например 5 символов, и выполняем такт за тактом, фиксируя состояние, положение головки и содержимое ленты.

2. Формулировка обобщённого правила словами. После трассировки 3–4 тактов замечаем шаблон: программа «движется до первого символа X и останавливается» или «заменяет один тип символов на другой, пока не встретит границу». Мини-пример: если в состоянии $q_1$ команда для 0 — «записать 1, сдвиг $R$, остаться в $q_1$», а для 1 — «записать 0, стоп» — правило: «идём вправо, превращая нули в единицы, до первой единицы, которую превращаем в 0» — классический инкремент двоичного числа.

3. Введение параметра длины серии и вывод формулы. Обозначаем через $t$ длину подряд идущих «проходимых» символов от края до первого «стопового» символа. Выражаем итоговое количество нужных символов через начальное количество и $t$: $Z_1=Z_0+t-1$ или $Z_1=Z_0-t+1$ (знак зависит от направления замены).

4. Перебор граничных значений параметра для поиска экстремума. Параметр $t$ движется в допустимых границах $0\le t\le N-1$, нужно найти, при каком $t$ выражение для $Z_0$ достигает нужного экстремума без выхода за ограничения (например $Z_0\le N-1$, целочисленность).

5. Для Редактора — пошаговое применение цикла замен. Каждую замену рассматриваем как один шаг, отслеживаем изменение длины строки и нужных символов, пока условие «нашлось(a)» не станет ложным. Мини-пример: строка aaab, команда «пока нашлось(ab) заменить(ab,ba)» — буква b сдвигается влево на одну позицию за шаг, после трёх повторений строка становится baaa.

Алгоритм решения по шагам

1. Прочитать описание исполнителя и зафиксировать реальный порядок столбцов/строк таблицы — порядок алфавита часто отличается от привычного и меняет смысл программы.
2. Определить начальное состояние головки, её начальное положение и направление движения.
3. Вручную выполнить 3–5 тактов на коротком примере, чтобы понять, что именно делает программа: движение до границы, замена символов, подсчёт и т.п.
4. Сформулировать правило работы программы словами.
5. Ввести параметр (обычно длину серии одинаковых символов у края) и выразить конечный результат через исходные данные и этот параметр.
6. Определить допустимый диапазон параметра с учётом длины всей последовательности и целочисленности.
7. Подставить границы диапазона и выбрать значение параметра, дающее нужный максимум или минимум искомой величины.
8. Проверить согласованность ответа: сумма нулей и единиц (или всех символов) должна равняться $N$.

Разбор примеров

Пример 1. Лента содержит $N=1000$ символов (нули и единицы), головка стоит справа от последовательности в состоянии $q_0$. Столбцы таблицы идут в порядке $\lambda,1,0$. Команда $q_0$ при $\lambda$ — сдвиг влево в $q_1$ (вход в последовательность). В $q_1$: при $\lambda$ — стоп; при 1 — записать 0, стоп; при 0 — записать 1, сдвиг влево, остаться в $q_1$.

Программа двигается влево от правого края, превращая нули в единицы, пока не встретит первую единицу — она превращается в 0, работа останавливается (если единиц нет вообще, головка доходит до левого края и останавливается на $\lambda$).

Пусть $t$ — число нулей подряд у правого края перед первой единицей. После выполнения эти $t$ нулей стали единицами (минус $t$ нулей), а следующая единица стала нулём (плюс 1 ноль): $$Z_1=Z_0-t+1.$$ По условию $Z_1=343$, значит $Z_0=342+t$. Ограничение: слева от найденной единицы должно остаться место для оставшихся $Z_0-t$ нулей среди $N-t-1$ позиций, то есть $Z_0-t\le N-t-1$, откуда $Z_0\le N-1=999$. Подставляя $Z_0=342+t\le 999$, получаем $t\le 657$, максимум $Z_0=999$ достигается при $t=657$. Ответ: 999.

Пример 2. Та же логика, $N=600$, $Z_1=233$. По формуле $Z_0=232+t$, ограничение $Z_0\le N-1=599$. Максимум достигается при $t=367$, давая $Z_0=599$. Ответ: 599.

В обоих примерах максимум оказался равным $N-1$ — это естественно: предельный случай — вся последовательность из нулей, кроме одной единицы у левого края, которая после работы программы становится нулём, а все остальные нули становятся единицами.

Пример 3. $N=400$, головка стоит слева от последовательности, движение вправо. Столбцы $\lambda,1,0$. $q_0$ при $\lambda$ — сдвиг вправо в $q_1$. В $q_1$: при $\lambda$ — стоп; при 1 — записать 0, сдвиг вправо, остаться в $q_1$; при 0 — записать 1, стоп.

Правило: двигаясь вправо, превращаем единицы в нули, пока не встретим первый ноль — он превращается в единицу, работа останавливается.

Пусть $s$ — число единиц подряд у левого края перед первым нулём. Эти $s$ единиц становятся нулями (плюс $s$ нулей), а следующий ноль становится единицей (минус 1 ноль): $$Z_1=Z_0+s-1,\qquad Z_0=Z_1-s+1.$$ По условию $Z_1=168$, значит $Z_0=169-s$. Требуется минимальное число единиц, то есть максимальное $Z_0$ (так как $Z_0+ones=N$). Максимум $Z_0$ достигается при минимальном $s$, а минимально возможное $s=0$ (первый символ слева сразу равен 0). Тогда $Z_0=169$, единиц $=400-169=231$. Ответ: 231.

Типичные ошибки и ловушки

• Перепутан порядок столбцов таблицы: если алфавит перечислен как $\lambda,1,0$, а не $\lambda,0,1$, легко приписать команду не тому символу — это меняет весь смысл программы.
• Забыто, что сдвиг выполняется после записи символа, а не перед ней.
• Не учтён случай, когда программа доходит до противоположного края ленты ($\lambda$) без остановки на «рабочем» символе — формула через $t$ (или $s$) для этого случая неприменима, нужен отдельный разбор.
• При поиске экстремума не проверяются ограничения на параметр (целочисленность, $0\le t\le N-1$) — можно получить формально «красивое», но недостижимое число.
• Путают «количество символов на ленте после выполнения» с «количеством оставшихся неизменных символов».
• Для Редактора забывают, что после каждой замены поиск подстроки начинается заново с начала строки, а не с места последней замены.
• Путают, что именно требуется найти — количество нулей, единиц или длину строки, и как эта величина связана с параметром роста/убывания.

Как готовиться

Начинать стоит с разбора эталонного примера программы из условия — это подсказка о логике всей серии задач года. Полезно вручную протрассировать программу на ленте из 8–10 символов, чтобы увидеть закономерность самостоятельно, а не запоминать готовое правило. Затем нужно решить 10–15 задач с разными числовыми данными на одну и ту же программу — так вырабатывается навык быстро находить формулу связи между исходными и итоговыми величинами. Отдельно стоит потренироваться на «обратных» задачах (дан результат — найти исходные данные) и на задачах с исполнителем Редактор, где важна аккуратность в подсчёте повторений цикла. После решения каждой задачи полезно проверять ответ на уменьшенном примере: подставить найденные числа в маленьком масштабе и убедиться, что логика программы действительно даёт заявленный результат.