Reachability for infinite time Turing machines with long tapes

MaRDI QIDQ6297821arXivFDO

Authors Merlin Carl, Benjamin G. Rin, Philipp Schlicht

Publication date 15 February 2018

Published in arXiv

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

arXiv classification

cs.LOmath.LO

Abstract: Infinite time Turing machine models with tape length $alpha$, denoted $T_{a}lpha$, strengthen the machines of Hamkins and Kidder [HL00] with tape length $omega$. A new phenomenon is that for some countable ordinals $alpha$, some cells cannot be halting positions of $T_{a}lpha$ given trivial input. The main open question in [Rin14] asks about the size of the least such ordinal $delta$. We answer this by providing various characterizations. For instance, $delta$ is the least ordinal with any of the following properties: (a) For some $xi<alpha$, there is a $T_{x}i$-writable but not $T_{a}lpha$-writable subset of $omega$. (b) There is a gap in the $T_{a}lpha$-writable ordinals. (c) $alpha$ is uncountable in $L_{lambd{a}_{a}lpha}$. Here $lambd{a}_{a}lpha$ denotes the supremum of $T_{a}lpha$-writable ordinals, i.e. those with a $T_{a}lpha$-writable code of length $alpha$. We further use the above characterizations, and an analogue to Welch's submodel characterization of the ordinals $lambda$, $zeta$ and $Sigma$, to show that $delta$ is large in the sense that it is a closure point of the function $alphamapstoSigm{a}_{a}lpha$, where $Sigm{a}_{a}lpha$ denotes the supremum of the $T_{a}lpha$-accidentally writable ordinals.

This page was built for publication: Reachability for infinite time Turing machines with long tapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6297821)