Решение

7.8. Программы для вычисления

(1) если , то стираем y; конец.

(1) если , то стираем x; конец.

(2) заменяем единицы записи x на +,

(3) стираем первый + слева, находим последний блок единиц и применяем программу удвоения,

(4) повторяем эту операцию до тех пор, пока не исчезнут +,

(5) стираем один блок единиц,

(6) применяем программу сжатия.

(1) применяем программу удвоения,

(2) применяем программу .

= наибольшее y такое, что

(1) от x справа печатаем y = 1,

(2) дублируем x и y,

(3) возводим y + 1 в квадрат,

(4) вычисляем ,

(5) если , то стираем все, кроме y. Конец.

(6) если = 0, то в оригинале заменяем y на y + 1 и переходим к (2).