Page 65 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 57
Note that by the liminf rule, at limit times t, the register contents will be α′ = β = t. The program computes the ordinal predecessor function
α−˙1= β, ifα=β+1, α, else.
Ordinal computability is closed under compositions:
Theorem 4.4. Let f(v0,...,vn−1) and g0(w⃗),...,gn−1(w⃗) be computable func- tions on the ordinals. Then the composition h(w⃗) = f(g0(w⃗),...,gn−1(w⃗)) is ordinal register computable.
The ordinal exponentiation function α → βα will be important for the sequel:
Ordinal exponentiation, computing gamma = beta ** alpha: 1 gamma:=1
2 alpha’:=0
3 if alpha=alpha’ then STOP
4 gamma=gamma * beta 5 alpha’=alpha’+1
6 goto3
The Go¨del pairing function is also ordinal computable:
Goedel pairing, computing gamma = G(alpha,beta): 0 alpha’:=0
1 beta’:=0
2 eta:=0
3 flag:=0
4 gamma:=0
5 if 6 if
7 if 8 if 9 if
alpha=alpha’ and beta=beta’ then STOP
alpha’=eta and beta’=eta and flag=0 then
alpha’=0, flag:=1, go to 5 fi
alpha’=eta and beta’=eta and flag=1 then
eta:=eta+1, alpha’=eta, beta’=0, gamma:=gamma+1, go to 5 fi beta’<eta and flag=0 then
beta’:=beta’+1, gamma:=gamma+1, go to 5 fi alpha’<eta and flag=1 then alpha’:=alpha’+1, gamma:=gamma+1, go to 5 fi
The inverse functions G0 and G1 satisfying
∀γγ = G(G0(γ), G1(γ))
are ordinal computable as well. To compute G0(γ) compute G(α, β) for α, β < γ until you find α, β with G(α, β) = γ; then set G0(γ) = α. This is a special case of the following inverse function theorem.