一句话：确定长纸带无限时间图灵机中最小不可达停机位置的序数 δ，并给出多个序数刻画。
本文研究纸带长度为 α 的无限时间图灵机 T_α，它推广了 Hamkins 与 Kidder 的纸带长度 ω 模型。新现象是：对某些可数序数 α，在平凡输入下有些单元不能成为 T_α 的停机位置。论文回答 Rin14 提出的核心问题，即最小这样的序数 δ 有多大，并给出多种刻画：δ 是最小满足以下任一性质的序数：(a) 存在 ξ<α，使某 ω 子集 T_ξ 可写但非 T_α 可写；(b) T_α 可写序数中存在间隙；(c) α 在 L_{λ_α} 中不可数，其中 λ_α 是 T_α 可写序数的上确界。作者进一步借助这些刻画以及 Welch 对 λ、ζ、Σ 的子模型刻画之类似结果，证明 δ 是函数 α↦Σ_α 的闭点，其中 Σ_α 是 T_α 偶然可写序数的上确界，从而说明 δ 很大。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{CarlRS20,
title = {Reachability for infinite time Turing machines with long tapes},
author = {Merlin Carl and Benjamin Rin and Philipp Schlicht},
journal = {Logical Methods in Computer Science},
volume = {Volume 16, Issue 2},
year = {2020},
doi = {10.23638/lmcs-16(2:2)2020}
}