TY - JOUR

T1 - Reachability for infinite time Turing machines with long tapes

AU - Rin, Benjamin

AU - Carl, Merlin

AU - Schlicht, Philipp

PY - 2020/4/24

Y1 - 2020/4/24

N2 - 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.

AB - 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.

U2 - 10.23638/LMCS-16(2:2)2020

DO - 10.23638/LMCS-16(2:2)2020

M3 - Article

SN - 1860-5974

VL - 16

SP - 2:1–2:16

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 2

ER -