№12ID 561Никита ПономаревВариант 17 из 171 первичный баллСложная
Условие

№ 12Машина Тьюринга

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

Команда достигла орбитальной станции и собирает детали для ремонта навигации.

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

СостояниеЧитаетсяЗаписатьСдвигНовое состояние
q10Lq
q01NH
q_1NH

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

1000111111

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

Автор: Никита Пономарев