Исполнитель МТ (машина на ленте): чтение программы

Исполнитель МТ — это головка, которая ходит по бесконечной горизонтальной ленте, разделённой на ячейки. В каждый момент головка обозревает ровно одну ячейку; другой памяти у машины нет — ни переменных, ни счётчиков.

Символы ленты — это данные. На ленте используются 0 и 1 (рабочие символы, из них состоит запись) и λ — пустой символ, которым заполнены все ячейки справа и слева от строки. λ нужен, чтобы у записи был явный край: дойдя до него, головка понимает, что вышла за пределы строки. Машина пишет символ в текущую ячейку, затирая прежнее значение. Число в МТ — это просто последовательность символов в соседних ячейках.

Состояние q — это режим исполнителя. Это не символ на ленте, а внутренняя пометка самой машины: «в каком режиме я работаю сейчас». Удобно представлять состояния как разные режимы работы: есть режим старта, с которого машина начинает работу, рабочие режимы, в которых выполняется основная часть алгоритма, и режимы, из которых машина завершает работу.

Состояний конечное число, но их может быть сколько угодно — столько, сколько нужно алгоритму. Рабочих режимов бывает несколько, и завершающих тоже может быть несколько: остановиться можно из разных состояний и по разным условиям. Например, во втором билете остановка на λ возможна из q2 или q3 — это два разных завершающих режима. Для удобства режимы просто обозначили буквой и цифрой — q0, q1, q2, … Это только имена: смысл не в номере, а в том, что машина делает в этом режиме.

Состояние — одна величина, но именно оно позволяет машине помнить контекст между тактами и вести себя по-разному в похожих ситуациях. В задачах стартовый режим — обычно q0.

Таблица программы смотрит на пару — состояние и символ. Это важная деталь: таблица берёт не только обозреваемый символ, а пару «текущее состояние + символ под головкой» и по ней находит команду. Строка таблицы — текущее состояние q, столбец — обозреваемый символ (0, 1 или λ), на их пересечении — команда. Поэтому состояние и нужно: один и тот же символ 1 в состояниях q1 и q2 может обрабатываться по-разному, и без состояния машина не знала бы, какую строку таблицы взять.

Состояние и позиция головки — разные вещи. Кроме состояния, у машины есть позиция головки — какая именно ячейка обозревается сейчас. Её называют отдельно: состояние = q («в каком режиме работает исполнитель»), а положение головки — «где на ленте он стоит». Полное описание системы на данный момент — это содержимое ленты, позиция головки и текущее состояние, но команду определяет только пара «состояние + символ под головкой».

Команда и один такт. В клетке таблицы записано три вещи: какой символ записать, как сдвинуться (L — влево, R — вправо, N — остаться на месте, S — остановиться) и в какое состояние перейти. Такт выполняется по порядку:

1. посмотреть на символ под головкой;
2. по паре «текущее состояние + этот символ» найти команду в таблице;
3. записать символ в текущую ячейку;
4. сдвинуться (L, R или N) или остановиться (S);
5. перейти в новое состояние.

Старт и остановка. В начальный момент головка стоит в ближайшей ячейке справа от строки, на символе λ, а машина — в стартовом состоянии. Работа заканчивается командой S (или когда для пары «состояние + символ» команды в таблице нет). После остановки на ленте остаётся результат: его читают слева направо и при необходимости переводят в десятичную запись.

Аналогия: символы — это буквы на бумаге, состояние — «на каком шаге алгоритма я нахожусь», а таблица — инструкция, что делать на каждом шаге при каждой прочитанной букве. Ниже — живая анимация: выберите готовую программу или введите свою ленту.

Имя ничего не значит. q0, q1, q2 — просто ярлыки; смысл состояния целиком в его строке таблицы. Переименуй q1 в q2 согласованно по всей таблице — поведение не изменится. Разница между состояниями — не в номере, а в том, что они делают.

Два состояния разные, если ведут себя по-разному. Сравнивают строки: если для одного и того же символа команды отличаются (пишут разное, идут в разные стороны, переходят в разные состояния) — это разные режимы. Если строки совпадают — состояния взаимозаменяемы: их можно слить, и программа станет короче.

Состояния нужны не «для разнообразия», а чтобы помнить контекст. У машины нет памяти, кроме ленты, а на каждом такте она видит только пару «состояние + символ». Если действие должно зависеть от того, что было раньше, эту информацию кладут в состояние — по сути, состояние это «на каком шаге алгоритма я сейчас».

Первый пример — две встречи одного и того же λ. В «Инверторе» q0: λ → λ, L, q1 и q1: λ → λ, S, q1. Головка дважды видит λ: сначала стартовый λ справа (надо войти в строку, L), потом λ на левом крае (надо остановиться, S). Символ один и тот же, а действия разные. Одним состоянием это не описать: при λ → L машина уедет влево навсегда, при λ → S встанет сразу. Значит, q0 и q1 функционально необходимы, а не «для разнообразия».

Второй пример — память о предыдущем символе. Во втором билете (q1, q2, q3) q2 и q3 обрабатывают одну и ту же 1 по-разному: в q2 она становится 0, в q3 остаётся 1. Так можно только потому, что состояние помнит, что было прочитано раньше.

Третий пример — две фазы. В том же «Инверторе» q0 только заходит в строку, q1 переворачивает. Два состояния = две фазы: «войти» и «работать».

Итог: состояние — это фаза (ветка) алгоритма, а q0 — стартовое по соглашению, не «главное». Сколько разных контекстов нужно различать — столько и состояний.

В каждой клетке таблицы записана команда из трёх частей, всегда в одном порядке: что записать — как сдвинуться — в какое состояние перейти. Читаем слева направо: «запиши …, шагни …, перейди в …».

Что записать (первая часть):

• λ — стереть: записать пустой символ;
• 0 — записать 0;
• 1 — записать 1.

Как сдвинуться (вторая часть): L — влево, R — вправо, N — остаться на месте, S — остановиться.

Куда перейти (третья часть): состояние, например q1; при S состояние уже неважно — машина встала.

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

• λ, L, q1 — стереть символ, сдвинуться влево, перейти в q1;
• 0, L, q1 — записать 0, идти влево, перейти в q1;
• 1, L, q2 — записать 1, идти влево, перейти в q2;
• 1, R, q2 — записать 1, идти вправо, перейти в q2;
• 0, N, q3 — записать 0, остаться на месте, перейти в q3;
• λ, S, q1 — стереть символ и остановиться.

Важное: первая часть не обязана совпадать с прочитанным символом: тот же — машина «переписывает» его, другой — заменяет, λ — стирает. Пустая клетка в таблице означает, что для этой пары «состояние + символ» команды нет — машина останавливается.

За один такт головка сдвигается ровно на одну ячейку (или остаётся на месте): L — на одну влево, R — на одну вправо, N — не двигается, S — работа заканчивается. Перепрыгнуть через ячейку или уехать сразу на несколько за один такт нельзя.

Направление не обязано быть всё время одним и тем же. Команды могут чередовать L и R, поэтому головка ходит туда-сюда. «Двигаться всегда в одну сторону» правило не требует — важно лишь, что за такт шаг не больше одной ячейки.

Лента бесконечна в обе стороны: «выйти за край» головка не может — за пределами записи стоят пустые символы λ. За такт меняется ровно одна ячейка — та, что под головкой.

Головка может зациклиться. Если программа возвращает машину в ту же конфигурацию — то же состояние, та же ячейка, то же содержимое ленты, — дальше всё повторяется бесконечно. Пример: q0: 0 → 0, R, q1 и q1: 0 → 0, L, q0 — на ленте из нулей машина бегает между двумя ячейками и никогда не остановится.

В задачах ЕГЭ программа обычно останавливается (ответ конечен), но формально незавершающаяся программа возможна — это проверяют прогоном. Наш демонстратор защищён пределом тактов: если остановки долго нет, он пишет, что машина не останавливается.