Question

Найти результат применения машины Тьюринга к записи на ленте.

Answer 1

q1 - указатель. В начале программы указывает на второй элемент последовательности

Программа говорит, что если указатель q1 указывает на единицу, то надо ее исправить на единицу и сместиться вправо... т.е. указатель будет двигаться вправо до тех пор, пока не встретит ноль.
Таким образом в конце выполнения первого правила указатель q1 сместится в конец последовательности (до нуля)

Далее, если указатель q1 показывает на ноль, то меняем ноль на единицу, меняем указатель q1 на q2 и сдвигаемся влево.
После выполнения второго правила получаем последовательность 0111111 и указатель q2 на предпоследнюю единицу.

Третьим правилом q2 - сдвигается влево до достижения нуля
После его выполнения получаем последовательность 0111111 и указатель q2 на первый ноль

Четвертое правило заменяет указатель q2 на q0 и сдвигается вправо

Таким образом получаем в конце программы последовательность 0111111  и  указатель q0 на первую единицу.