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.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:685421
Date January 2010
CreatorsDawson, Barnaby
PublisherUniversity of Bristol
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation

Page generated in 0.0016 seconds