Merlin Carl ; Benjamin Rin ; Philipp Schlicht - Reachability for infinite time Turing machines with long tapes

lmcs:4444 - Logical Methods in Computer Science, April 24, 2020, Volume 16, Issue 2 -
Reachability for infinite time Turing machines with long tapesArticle

Authors: Merlin Carl ; Benjamin Rin ; Philipp Schlicht

    Infinite time Turing machine models with tape length $\alpha$, denoted $T_\alpha$, 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_\alpha$ 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_\xi$-writable but not $T_\alpha$-writable subset of $\omega$. (b) There is a gap in the $T_\alpha$-writable ordinals. (c) $\alpha$ is uncountable in $L_{\lambda_\alpha}$. Here $\lambda_\alpha$ denotes the supremum of $T_\alpha$-writable ordinals, i.e. those with a $T_\alpha$-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 $\alpha \mapsto \Sigma_\alpha$, where $\Sigma_\alpha$ denotes the supremum of the $T_\alpha$-accidentally writable ordinals.

    Volume: Volume 16, Issue 2
    Published on: April 24, 2020
    Accepted on: March 8, 2020
    Submitted on: April 16, 2018
    Keywords: Mathematics - Logic,Computer Science - Logic in Computer Science
      Source : OpenAIRE Graph
    • Inner models and infinite computations; Funder: European Commission; Code: 794020

    Consultation statistics

    This page has been seen 1240 times.
    This article's PDF has been downloaded 273 times.