Three models of ordinal computability

Abstract

In this thesis we expand the scope of ordinal computability, i.e., the study of models of computation that are generalized to infinite domains. The discipline sets itself apart from classical work on generalized recursion theory by focusing strongly on the computational paradigm and an analysis in elementary computational steps. In the present work, two models of classical computability of which no previous generalizations to ordinals are known to the author are lifted to the ordinal domain, namely λ-calculus and Blum-Shub-Smale machines. One of the multiple generalizations of a third model relevant to this thesis, the Turing machine, is employed to further study classical descriptive set theory. The main results are: <br /> An ordinal λ-calculus is defined and confluency properties in the form of a weak Church-Rosser theorem are established. The calculus is proved to be strongly related to the constructible hierarchy of sets, a feature typical for an entire subfamily of models of ordinal computation. <br /> Ordinal Turing machines with input restricted to subsets of ω are shown to compute the Δ¹₂ sets of reals. Conversely, the machines can be employed to reprove the absoluteness of Σ¹₂ sets (Shoenfield absoluteness) and basic properties of Σ¹₂ sets. New tree representations and new pointclasses defined by the means of ordinal Turing computations are introduced and studied. <br /> The Blum-Shub-Smale model for computation on the real numbers is lifted to transfinite running times. The supremum of possible runtimes is determined and an upper bound on the computational strength is given. <br /> Summarizing, this thesis both expands the field of ordinal computability by enlarging its palette of computational models and also connects the field further by tying in the new models into the existing framework. Questions that have been raised in the community, e.g. on the possibility of generalizations of λ-calculus and Blum-Shub-Smale machines, are addressed and answered.