Return to search

Ordinal time Turing computation

This thesis develops the theory of Ordinal Time Turing Machines (OTTMs) and explores connections between this theory, inner model theory, α-recursion and Turing computation. We first provide a rigorous definition of an OTTM. We define how such machines may be taken to operate on sets, we prove that the class of OTTMs has a universal machine, we prove that the class 0 of OTTM computable sets is equal to L, we prove an analogue of the condensation lemma and we prove that the Generalized Continuum hypothesis & ◊ωl hold in L using lemmas concerning OTTMs. We also define several variants of computer limited to α time. We expose weaknesses in all bar one of the variants (uniform-α-computation) and then we use this remaining variant to develop a degree theory. Vie show this theory is isomorphic to the theory of α-recursion, we show that α-recursion is not equivalent to α-computation and we give a proof of a form of the SACKS SIMPSON theorem stated for the uniform-α-computer. We then prove results about halting computations, universal and metaversal programs ('metaversal program' is defined in this thesis) for the uniform-α-computer. We define a (B,α)-computer which is closely related to inner model theory. We prove an analogue of the Density theorem for the (B,α)-computer and find a metaversal program for the (B,α)-computer. Finally we compare the α-computers and OTTMs with Turing machines. The introduction consists entirely of pre-existing results and definitions which provide a necessary background for the rest of the thesis. The proof of SACKS-SIMPSON for uniform-a-computers is adapted from Benjamin Seyfferth's proof for non-uniform-a-computers. The Density theorem for α-recursion of Sacks is modified and adapted for uniform-(B,α)-computers. All other results are entirely my own work unless otherwise stated.
Date January 2010
CreatorsDawson, Barnaby
PublisherUniversity of Bristol
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation

Page generated in 0.0016 seconds