Page 51 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY
PETER KOEPKE
Abstract. Ordinary computations can be characterized by register machines working with natural numbers. We study ordinal register machines where the registers can hold arbitrary ordinal numbers. The class of sets of ordinals which are computable by such machines has strong closure properties and satisfies the set theoretic axiom system SO. This implies that ordinal computability is equivalent to Go¨del’s model L of constructible sets. In this tutorial we shall give a proof of this theorem, starting with brief reviews of ordinal theory and standard register machines.
1 Introduction
There are many equivalent machine models for defining the class of in- tuitively computable sets. We define computations on ordinals in analogy to the unlimited register machines (URM ) presented in [2]. An URM has registers R0, R1, . . . which can hold natural numbers, i.e., elements of the set ω = {0, 1, . . .}. A register program consists of commands to increase or to reset a register. The program may loop on condition of equality between two registers. A natural generalisation from the perspective of transfinite ordinal theory is to extend such calculations to the class Ord = {0,1,...,ω,ω + 1,...} of all ordi- nal numbers so that registers may 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 (liminf).
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.
Using the pairing function one can view each ordinal α as a first-order sentence with constant symbols for ordinals < α. One can then define a recursive truth predicate T ⊆ Ord by:
α∈T iff(α,<,G∩α3,T∩α)α.
This recursion can be carried out on an ordinal register machine, using stacks which contain finite decreasing sequences of ordinals. For ordinals μ and ν the predicate T codes the set
T(μ,α) = {β < μ|T(G(α,β)) = 1}. 43