Условие задачи
Написать программу для машины с неограниченными регистрами для вычисления функции f(x,y)=x+y (x>0, y>=0, в начальный момент значение x находится в регистре R1, а значение y - в регистре R2; программа должна завершать работу за конечное время и в момент завершения регистр R1 должен содержать значение x+y).
Теоретические сведения
Машина с неограниченными регистрами (МНР).
Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.
Допустимые команды:
Z(n) - обнуление регистра Rn.
S(n) - увеличение числа в регистре Rn на 1.
T(m,n) - копирует содержимое Rm в регистор Rn.
I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет
следующая.
Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.
Написать и отладить программу.
Ответ
Алгоритм программы.
Программа.
1. Z(3);
2. I(2,3,6);
3. S(1);
4. S(3);
5. I(1,1,2); //безусловный переход на команду 2
6. T(1,1);//ничего не делать результат получен
1) Вычислить геделев номер программы, созданной в рамках 1-го задания.
Пусть произвольная программа для МНР. Определим взаимно однозначное отображение следующим образом:
