Turing Computations On Ordinals
Peter Koepke · Bulletin of Symbolic Logic · 2005
Abstract We define the notion ofordinal computabilityby generalizing standard Turingcomputability on tapes of length ω to computations on tapes of arbitrary ordinal length. We show that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Gödel'sconstructible universeL. This characterization can be used to prove the generalized continuum hypothesis inL.