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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:685421 |
| Date | January 2010 |
| Creators | Dawson, Barnaby |
| Publisher | University of Bristol |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.002 seconds