Mathematical Structures in Computer Science · 2006 · 11 citations · 2 references
Natural SciencesComputer ScienceMathematicsLogicSet TheoryTheory Of ComputationAxiomatic Set TheoryCardinal NumbersComputability TheoryModel TheoryOrdinal NumbersTuring MachinesTuring Machine Computability
The notion of ordinal computability is defined by generalising standard Turing computability on tapes of length . In this paper we present a new proof of this theorem that makes use of a theory SO axiomatising the class of sets of ordinals in a model of set theory. The theory SO and the standard Zermelo–Fraenkel axiom system ZFC can be canonically interpreted in each other. The proof of the fundamental theorem is based on showing that the class of sets that are ordinal computable from ordinal parameters forms a model of SO.
2
Turing Computations On Ordinals
Peter Koepke · Bulletin of Symbolic Logic · 2005 · 98 citations