数学论文（无限时间图灵机） (6-3)

尽管超限，但计算本质上是可数的，因为共最终性论证证明，每一次计算要么暂停，要么重复一些可数序数阶段。如果存在计算，则序数α被认为是可计时的恰好停在α上第th步。如果实数x是计算的输出ξp（0），则实数x是可写的，而序数是可写的，如果它是由这样的实数编码的。因为只有可计数的在许多程序中，因此只有可计数的多个可计时和可写的序数。可计时和可写的序数扩展到所有递归序数和远远超出；它们的上确界是递归不可访问的等等。可写的序数形成序数的初始段，因为每当一个序数是可写的，那么编写它的算法就可以很容易地修改为任何较小的序数编写代码。但是对于可计时的序数来说，情况并非如此；在可计时的序数中，有无（无参数）无限时间图灵的越来越复杂的禁区机器可能会停下来。

让我们快速勾勒出这样一个论点，即可计时序数中存在这样的差距，因为这是有序反射中一个有趣的练习，它构成了许多方法的基本方法后来的理论建构。考虑模拟上所有程序的算法同时输入0，通过一些保留和管理sufi的记账方法-每个程序都有足够的独立空间，模拟ω每个程序的许多计算步骤在每个ω实际计算的许多步骤中。我们的算法可能会仔细跟踪哪些程序已经停止，并注意找到没有程序停止的阶段。由于这样一个阶段存在于所有可计时序数的上确界之上，我们最终一定会找到这样的舞台。由于我们的算法可以识别第一个在这样的阶段，我们可以安排它在这一发现后立即停止。因此，我们描述了一种计算过程，它将在比没有计算停止的阶段，因此在可计时的序数中存在间隙，如渴望的对该算法的仔细分析表明，任何可计时序数之后的第一个间隙都具有阶型ω，本质上是因为ω需要许多额外的步骤才能实现已经达到了一个缺口。改进的算法搜索更长的间隙，并表明必须是在越来越复杂的可容许极限阶段越来越复杂任何可计时或可写的序数α，都存在大小至少为α的间隙。这些的结构gap表现出与无限时间停顿问题相同的复杂性。

尽管在[HL00]中已经确定了可计时和可写的序数同样的订单类型，也许该论文中留下的主要问题是这些序数的上确界是相同的。这件事得到了菲利普的肯定Welch在[Wel00b]。另一种描述结果的方式是，每当程序打开输入x产生一个停止的计算，然后有另一个计算写出该计算的证书，整个计算历史的真实编码，包括有序关系，其顺序类型是计算的长度。这很重要事实远非显而易见，它依赖于对最终可写性的微妙处理，并构成这是该理论许多进一步发展的基础，包括我们的应用在本文中提及。

上述计数论证的反映方面包括观察到可能遇到的实数的任何可判定性质在计算过程中，必须持有一个可写的实数，因为我们可以开始计算搜索以找到这样的见证并在找到时输出它。这个想法极大地推广了Philip Welch的λ-ζ-∑定理。具体而言，[HL00]定义如果存在x出现在从上的某个点输出磁带（即使计算没有停止），并且如果x在计算期间的任何阶段出现在任何磁带上，则它是意外可写的。通过用实数编码序数，我们得到了最终可写和意外可写的概念序数。如果λ是可计时或可写序数的上确界，则ζ是最终可写序数，∑是意外可写序数的上确界，则[HL00]建立λ＜ζ＜∑。Welch[Wel00a]断言的λ-ζ-∑定理。

此外，Lλ≺∑1Lζ图案这个结果准确地表达了算法可能会下降的意义见证人从意外可写领域进入最终可写或可写领域王国。证明和结果的核心是每一次计算都是重复的∑阶段的ζ配置。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。