Reachability for infinite time Turing machines with long tapes

Merlin Carl, Benjamin Rin, Philipp Schlicht

Research output: Contribution to journalArticle (Academic Journal)peer-review

5 Downloads (Pure)

Abstract

Infinite time Turing machine models with tape length α, denoted T_α, strengthen the machines of Hamkins and Kidder with tape length ω. A new phenomenon is that for some countable ordinals α, some cells cannot be halting positions of Tα given trivial input. The main open question in a paper of Rin from 2014 asks about the size of the least such ordinal δ. We answer this by providing various characterizations. For instance, δ is the least ordinal with any of the following properties: • For some ξ < α, there is a T_ξ-writable but not T_α-writable subset of ω. • There is a gap in the T_α-writable ordinals. • α is uncountable in L_(λ^α). Here λ^α denotes the supremum of Tα-writable ordinals, i.e. those with a T_α-writable code of length α. We further use the above characterizations, and an analogue to Welch’s submodel characterization of the ordinals λ, ζ and Σ, to show that δ is large in the sense that it is a closure point of the function α ﰁ→ Σ_α, where Σ_α denotes the supremum of the Tα-accidentally writable ordinals.
Original languageEnglish
Number of pages16
JournalLogical Methods in Computer Science
Volume16
Issue number2
DOIs
Publication statusPublished - 24 Apr 2020

Fingerprint Dive into the research topics of 'Reachability for infinite time Turing machines with long tapes'. Together they form a unique fingerprint.

Cite this