Page 61 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 53
Observe that the function n → n−˙ 1 is not a basic function of the URM. It can, however, be programmed as follows:
Decrementation, computing beta = alpha -˙ 1:
0 alpha’:=0
1 beta:=0
2 if alpha=alpha’ then STOP 3 alpha’:=alpha’+1
4 if alpha=alpha’ then STOP 5 beta:=beta+1
6 goto3
Multiplication, computing gamma = alpha * beta: 1 beta’:=0
2 gamma:=0
3 if beta=beta’ then STOP
4 beta’:=beta’+1
5 gamma:=gamma + alpha 6 goto3
Exercise 10. Write a program for division with remainder.
We interpret the program line gamma:=gamma + alpha as a macro, i.e., the above addition program has to be substituted for that line with reasonable modifications of variables, registers and line numbers. Also transfer of arguments and values between variables has to be arranged. This could, e.g., be achieved as follows:
Multiplication, computing gamma = alpha * beta: 1 beta’:=0
2 gamma:=0
3 if beta=beta’ then STOP
4 beta’=beta’+1
5 alpha’’:=0
6 beta’’:=0
7 gamma’:=0
8 gamma=alpha’’ then go to 12 9 alpha’’=alpha’’+1
10 gamma’=gamma’+1
11 go to 8
12 if alpha=beta’’ then go to 16 13 beta’’=beta’’+1
14 gamma’=gamma’+1
15 go to 12
16 gamma:=gamma’
17 go to 3