论文标题
无限计算的决策时间
Decision times of infinite computations
论文作者
论文摘要
无限时间算法的决策时间是其在所有实际输入中停止时间的至高无上。一组真实的决定时间是决定集合的算法的最小决策时间。半确定集的半确定时间是相似的。不难看到$ω_1$是一组真实的最大决策时间。我们的主要结果将可计数决策时间的至上确定为$σ$，而可计数的半决时间为$τ$，其中$σ$和$τ$分别表示$σ_1$ - 和$σ_2$ -DDEVINABLESILLS的额外，超过$ L_ {ω_1} $。我们进一步计算单身人士的类似性。
The decision time of an infinite time algorithm is the supremum of its halting times over all real inputs. The decision time of a set of reals is the least decision time of an algorithm that decides the set; semidecision times of semidecidable sets are defined similary. It is not hard to see that $ω_1$ is the maximal decision time of sets of reals. Our main results determine the supremum of countable decision times as $σ$ and that of countable semidecision times as $τ$, where $σ$ and $τ$ denote the suprema of $Σ_1$- and $Σ_2$-definable ordinals, respectively, over $L_{ω_1}$. We further compute analogous suprema for singletons.
