Page 64 - Textos de Matemática Vol. 38

56 PETER KOEPKE
Definition 4.2. An n-ary partial function F : Ordn ⇀ Ord is (ordinal regis- ter) computable if there is a register program P such that for every n-tuple (α0,...,αn−1) holds
P : (α0,...,αn−1,0,0,...) → F(α0,...,αn−1).
Definition 4.3. A subset x ⊆ Ord is (ordinal register) computable if there is a
register program P and ordinals δ1, . . . , δn−1 such that for every α ∈ Ord holds P : (α,δ1,...,δn−1,0,0,...) → χx(α),
where χx is the characteristic function of x. 4.2 Ordinal algorithms
Since ordinal register machines are a straightforward extension of stan- dard register machines, all recursive functions can be computed by an ordinal register machine. The basic operations on ordinal numbers are ordinal register computable by the same URM programs that we used before:
Ordinal 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
Observe that at limit times this algorithm, by the lim inf rule, will nicely cycle back to the beginnings of loops 3 - 6 or 7 - 10 resp. and thus it will implement the recursion rule for addition at limit ordinals.
Ordinal decrement, 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