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