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

Одна фаза — один проход

Самые простые программы номера 12 состоят из двух состояний.

Первое заводит головку на край. Второе делает всю работу за один проход.

Сквозное число этого урока — 88. В двоичной записи это 1011000. Оно будет проходить через все программы урока.

Разбор: программа вычитания единицы

Головка стоит справа от записи, на пустой клетке. Команда λ, L, q1 заводит её на младший разряд.

Дальше в q1 всего два правила:

• увидела 0 — записала 1, поехала влево;
• увидела 1 — записала 0 и встала.

Это заём при вычитании: хвостовые нули становятся единицами, ближайшая единица — нулём. При исходном положении головки в конце записи числа, происходит вычитание единицы.

Микропаттерн: 0→1,L и 1→0,S = вычесть единицу.

На ленте 1010111, то есть 87. Проверка: 88 − 1 = 87.

Та же таблица, одна буква иначе

Теперь смотри внимательно. Меняем в клетке для единицы S на L:

Головка больше не останавливается на первой единице. Она едет дальше и переворачивает каждый бит до конца ленты.

Было вычитание. Стала инверсия.

Из 1011000 получается 0100111 — это 39, а вовсе не 87.

Микропаттерн: ищи, где стоит S. Она отделяет «остановись на первом попавшемся» от «пройди всё».

Ведущий ноль: куда девается разряд

Исходная запись начинается с единицы — так устроена запись без ведущих нулей.

После инверсии на первом месте оказывается ноль. Лента 0100111 как число читается без него: 100111 = 39.

Поэтому «что записано на ленте» и «какое число на ленте» — разные вопросы. Перечитывай, о чём спросили.

Микропаттерн: инверсия всегда рождает ведущий ноль.

Проверь себя

Что проверить перед ответом

• Нашёл клетку с S? Записал ли символ из неё?
• Спросили число или последовательность символов?
• Если была инверсия — отбросил ли ведущий ноль при переводе в десятичную?