Page 60 - Textos de Matemática Vol. 38

52
PETER KOEPKE
ii.
iii.
iv.
if II(t) is the successor instruction S(n) then let I(t + 1) = I(t) + 1 and define R(t + 1) : ω → Ord by
Rk(t+1)= Rk(t)+1, ifk=n, Rk(t), if k ̸= n;
if II(t) is the transfer instruction T (m, n) then let I(t + 1) = I(t) + 1 and define R(t + 1) : ω → Ord by
Rk(t + 1) = Rm(t), if Rm(t) = Rn(t), Rk(t), if Rm(t) ̸= Rn(t);
if II(t) is the jump instruction J(m, n, q) then let R(t + 1) = R(t) and I(t + 1) = q, if k = n,
I(t)+1, ifk̸=n.
The computation is obviously recursively determined by the initial register con- tents R(0) and the program P. We call it the computation by P with input R(0). If the computation stops at length θ = β + 1 < ω then R(β) are the final register contents. In this case we say that P computes R(β)(0) from R(0) and write P : R(0) → R(β)(0).
3.2 Algorithms
It can be shown that the unlimited register machine is equivalent to the other standard models of computations like Turing machines. So a function f : ω → ω is computable by the URM iff it is Turing computable. In view of our later generalizations we present some arithmetic register programs:
Addition, computing gamma = alpha + beta: 0 alpha’:=0
1 beta’:=0
2 gamma:=0
3 if alpha=alpha’ then go to 7 4 alpha’:=alpha’+1
5 gamma:=gamma+1
6 goto3
7 if beta=beta’ then STOP 8 beta’:=beta’+1
9 gamma:=gamma+1
10 go to 7
Exercise 9. Write the addition program in the form P = I0 , I1 , . . . , Is−1 as in Defini- tion 3.1.