Page 62 - Textos de Matemática Vol. 38

54 PETER KOEPKE
4 Ordinal computations
The URM is based on the operations x := 0 and x := x+1 on natural numbers. An obvious generalisation from the perspective of transfinite ordinal theory is to extend such calculations to the class Ord of all ordinal numbers an let registers contain arbitrary ordinals. At limit ordinals one defines the program states and the registers contents by appropriate limit operations which may be viewed as inferior limits. Note that we shall use exactly the same programs for ordinal computations as for computations with natural numbers.
This notion of ordinal (register) computability obviously extends stan- dard register computability. By the Church-Turing thesis many operations on natural numbers are ordinal computable. The ordinal arithmetic opera- tions (addition, multiplication, exponentiation) and Go¨del’s pairing function G : Ord × Ord → Ord are also ordinal computable.
4.1 Ordinal register machines - ORMs
Definition 4.1. Let P = I0, I1, . . . , Is−1 be an URM program. A pair
I : θ → ω,R : θ → (ωOrd)
is an (ordinal register) computation by P if the following hold:
a) θ is a successor ordinal or θ = Ord; θ is the length of the computation;
b) I(0) = 0; the machine starts in state 0;
c) Ift<θandI(t)̸∈s={0,1,...,s−1}thenθ=t+1;themachinestopsif the machine state is not a program state of P;
d) If t < θ and I(t) ∈ state(P) then t+1 < θ; the next configuration is determined by the instruction II(t) :
i. if II(t) is the zero instruction Z(n) then let I(t+1) = I(t)+1 and define R(t + 1) : ω → Ord by
Rk(t+1)= 0, ifk=n, Rk(t), if k ̸= n;
ii. 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;