Модуль: Вопрос 12. Машина Тьюринга

Когда состояний больше двух

Два состояния — это «зашёл и сделал». А если нужно сначала доехать до нужного места? Тогда появляется отдельное состояние на каждую фазу.

Читать такую таблицу построчно бесполезно. Читай по состояниям.

Как узнать фазу поиска

Фаза поиска выглядит очень характерно: в состоянии для 0 и для 1 стоит одна и та же команда вида «сам символ, сдвиг, то же состояние».

Головка едет и ничего не меняет. Она просто ищет край.

Выход из фазы — команда на λ: там меняется состояние, а часто и направление.

Микропаттерн: одинаковые команды для 0 и 1 = проматывание, а не работа.

Разбор реальной задачи (ЕГКР, декабрь 2025)

На ленте двоичная запись числа 2028, головка слева. Программа:

Разбираем по состояниям:

• q0 — заход: с пустой клетки шагнули вправо, на старший разряд;
• q1 — поиск: 0→0,R и 1→1,R — едем вправо через всё число, ничего не трогая. На λ за правым краем пишем 0 и идём в q2;
• q2 — пишем ещё один 0, идём в q3;
• q3 — на λ стоп.

Итог: справа к числу приписаны два нуля.

А приписать справа ноль в двоичной записи — это умножить на 2. Два нуля — на 4.

11111101100 → 1111110110000, то есть 2028 → 8112. Проверка: 2028 · 4 = 8112. Шагов программа сделала 15.

Микропаттерн: дописать k нулей справа = умножить на 2^k.

Ловушки многофазных программ

Первая: посчитать состояния и решить, что программа сложная. Число состояний говорит о числе фаз, а не о сложности. Три фазы «доехал — дописал — встал» проще, чем два состояния с хитрым условием.

Вторая: пропустить, что на λ может стоять не λ. В разобранной задаче именно там пишется 0 — и лента становится длиннее.

Третья: забыть, что клетка пустая не по ошибке. Если для пары «состояние — символ» команды нет, значит при работе она не встретится. Это подсказка, а не пробел.

Проверь себя

Регламент для многофазной таблицы

• Выпиши состояния столбиком и подпиши каждое одним словом: заход, поиск, запись, стоп.
• Найди, где меняется направление — это границы фаз.
• Проверь, пишет ли программа что-нибудь на месте λ: если да, лента удлиняется.
• Только после этого начинай считать.