На ленте в соседних ячейках записана последовательность из 350 символов, среди которых могут быть только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности. Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 100 нулей. Определите минимально возможное число нулей в исходной последовательности.
Решение:
Сначала все 0 станут 1, а все 1 станут 0(В q1)
Но потом мы начнем движение слева-направо(В q2)
Все 1 становятся 0, пока не встретится 0. После встречи с 0 он заменяется на единицу и программа останавливается.
Значит в конечной строке было 100 нулей и 350 - 100 = 250 единиц. Если один ноль заменился на единицу, значит в предпоследнем запуске было 101 ноль и 249 единиц. Из состояния q1 вспомним, что все нули поменялись на единицу, а значит нулей изначально могло быть 249.