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

Лента, головка, состояние

Представь бесконечную полосу бумаги в клетку. В каждой клетке ровно один символ. Над одной клеткой висит головка — она читает символ и может его переписать.

Головка помнит ровно одно: своё состояние. Больше у неё памяти нет.

Вот и весь исполнитель.

Как читать таблицу

Что вообще может задать поведение такой машины? Список правил? Слишком длинно. Остаётся одно. Таблица.

Строки — состояния. Столбцы — что головка видит. На пересечении — что делать.

Команда всегда из трёх частей: что записать, куда сдвинуться, в какое состояние перейти.

Пустая клетка не значит «ничего не делай». Она значит: такого не случится.

Разбор команды

Команда 0, L, q3 читается слева направо, как приказ из трёх пунктов:

1. в текущую клетку записать 0;
2. сдвинуться на одну клетку влево;
3. перейти в состояние q3.

Порядок жёсткий: сначала пишем, потом едем. Не наоборот.

Буква S — главная ловушка номера

Две буквы сдвига понятны: L влево, R вправо,.

А S — это стоп. И вот здесь теряют балл.

S не означает «просто остановись». S означает: запиши символ, и только потом остановись. Запись происходит всегда.

Команда 0, S, q1 на клетке с единицей — это «замени 1 на 0 и стой». Кто прочитает её как «стой», потеряет одну замену и придёт к ответу, отличающемуся на единицу.

Микропаттерн: S = запись + стоп.

Проверь себя

Регламент чтения таблицы

До решения:

• подчеркни в условии, с какой стороны стоит головка — слева или справа;
• найди начальное состояние: это первая строка таблицы;
• посмотри, в каких клетках стоит S — там программа кончается.

Во время:

• читай таблицу по состояниям, а не по строкам подряд: каждое состояние — это одна фаза работы;
• на каждом шаге держи в голове три вещи: символ под головкой, состояние, позицию.

Перед записью ответа:

• перечитай вопрос. Спрашивают число? количество нулей? число шагов?