Page 78 - Textos de Matemática Vol. 38

70
PETER KOEPKE
We show uniqueness. Assume that also
α=δα′0 ·ζ′ +δα′1 ·ζ′ +···+δα′r−1 ·ζ′
0 1 r−1
Thenα∈[δα0 ·ζ0,δα0 ·(ζ0+1))andα∈[δα′0 ·ζ0′,δα′0 ·(ζ0′ +1)).Bythepairwise
disjointness of intervals of this type, α0 = α′0 and ζ0 = ζ0′ . Furthermore
δα1 ·ζ +···+δαn−1 ·ζ =δα′1 ·ζ′ +···+δα′r−1 ·ζ′ <δα0 ·ζ α.
1 n−1 1 r−1 0
inductive assumption, (α1, . . . , αn−1) = (α′1, . . . , α′r−1) and ✷
By the
(ζ1, . . . , ζn−1) = (ζ1′ , . . . , ζn′ −1). Hence the two δ-adic representation of α agree.
By the proposition, a decreasing stack α0 > α1 > · · · > αn−2 αn−1 of ordinals can be coded by one ordinal
α=⟨α0,α1,...,αn−2,αn−1⟩=3α0 +3α1 +···+3αn−2 +3αn−1.
We call the natural number n the length of the stack α . The final elements
αn−1, αn−2, . . . of this stack can be defined from α as follows: αn−1 = thelargestξsuchthatthereisζwithα=3ξ·ζ
αn−2 = thelargestξsuchthatthereisζwithα−3αn−1 =3ξ·ζ .
The ordinals
programs last, llast resp., we agree that these functions return a special value UNDEFINED if the stack is too short.
αn−1 , αn−2 are obviously ordinal register computable by some If the stack α is kept in a register stack then the lim inf behaviour of
registers implies the following crucial limit behaviour of stacks.
Proposition 8.2. Let t ∈ Ord be a limit time and t0 < t. For time τ ∈ [t0,t) let thecontentsoftheregisterstackbeoftheform ατ =⟨α0,...,αk−1 ,ρ(τ),...⟩ for fixed α0,...,αk−1 and variable ρ(τ) αk−1. Assume that the sequence (ρ(τ )|τ ∈ [t0 , t)) is weakly monotonously increasing and that the length of stack is equal to k+1 cofinally often below t. Then at limit time t the content of stack is of the form αt = ⟨α0,...,αk−1 ,ρ⟩ with ρ = τ∈[t0,t) ρ(τ).
8.2 Stack recursion
Given an algorithm for the recursion function H we compute F with a stack as considered above and a variable value which can hold a single value of the function F : we let value = 2 stand for “undefined’. The intention of the following program P is to accept an input ordinal α on the singleton stack α and stop with the output stack α and value= F (α). During the recursion