TY - JOUR
T1 - Reachability for infinite time Turing machines with long tapes
AU - Carl, Merlin
AU - Rin, Benjamin
AU - Schlicht , Philipp
PY - 2020/4/24
Y1 - 2020/4/24
N2 - 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.
AB - 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.
U2 - 10.23638/LMCS-16(2:2)2020
DO - 10.23638/LMCS-16(2:2)2020
M3 - Article (Academic Journal)
VL - 16
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
IS - 2
ER -