Глава 12. Лента автомата

Исследовательский аппарат прошёл внешний шлюз. Нужно восстановить карту подводных залов.

На бесконечной ленте записано двоичное число, остальные клетки пусты (_). Головка стоит на самом правом бите, состояние q. Таблица переходов (записать символ, сдвинуться, новое состояние):

L — влево, N — без сдвига, H — останов. Исходная запись:

11110010111111111

Сколько переходов выполнит машина до остановки? Переход в H тоже считается.