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 -