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

input：0 0 1 1 1 1 0 0 . . .

scrαtch：1 1 0 1 0 0 1 0 . . .

output：0 0 1 0 1 0 1 1 . . .

根据到程序指令。计算被简单地扩展到限制有序阶段定义机器的极限配置。其想法是尽可能多地保留计算到那个阶段为止一直在创建的信息，将其保留在极限配置中，作为早期配置的一种极限。明确地在任何极限有序阶段ξ，机器进入我们所说的极限状态，其中一个区分状态以及开始状态和停止状态；磁头被重置为第一个单元在左边；并且磁带的每个单元都用先前值的limsup更新显示在该单元格中。已经指定了机器的完整配置在阶段ξ，计算现在可以继续到阶段ξ+1，以此类推只有当机器明确进入停止状态时才会给出输出，并且计算当这种情况发生时停止。

由于磁带自然地容纳了无限的二进制字符串——而且有很多头检查每个单元格的时间——输入和输出到的自然上下文机器是Cantor空间2ω，我们用R表示它，并称之为实数。因此机器提供了实数上可计算性的无限概念。一个程序p计算偏函数ξp。

.R→ R、 如果程序p在输入x上，则由ξp（x）=y定义产生输出y，其中计算的输出是输出磁带的内容，当机器进入停止状态。子集A⊆R是无限时间可判定的，如果A的特征函数是无限时间可以计算的。集合A是无限时间半可判定的，如果常偏函数1↾ A是可计算的。这相当于A是域的无限时间可计算函数（但不一定等同于A是这样的函数的范围）。[HL00]中的初步结果表明，算术集是正是那些在时间上可判定的一致小于ω2和超算术的集合是那些在时间上比某些递归序数更短的可判定集合。的力量。

然而，机器在描述集合论中达到了比这高得多的水平等级制度。

例如，每个π11.和∑11.集合是无限时间可判定的。要看到这一点，只需表明完整的π11.集合WO由编码ω上的良序关系的实数组成，是无限时间可计算的。这是通过[HL00，定理2.2]，我们想在这里画一下。给定一个实数x，我们将其视为编码ω上的关系式，其中n⊳m当且仅当x的h n，mi位为1。断言⊳是一个线性阶是x中的算术，因此很容易由机器确定。

之后，机器将通过计数来检查基础是否良好顺序，这取决于计算步骤本身是有序的。

具体来说，机器将当前最小元素的初始猜测放在关系⊳，在遇到它们时用更好的猜测进行更新。在每次修订时机器会闪烁某个主标志，这样在极限阶段，机器就可以知道猜测被无限频繁地更改，表明基础不健全（机器应该重置在极限级的极限处的主标志）。否则，真实的电流最小元素已经找到，因此机器可以从的字段中删除所有提及它的内容由x编码的关系。重复此操作，算法实际上系统地擦除由输入实数编码的关系的有根据的初始段，直到要么什么都没有发现了左或无根据的部分，这两者都可以确定。通过这种方式，WO的成员资格是无限时间可决定的。由此可知，每个π11.和∑11.集合是无限的。　

时间是决定性的，因此机器正确地爬升到∆1.2.。同时，的类无限时间可判定集很容易被观察到包含在∆中1.2.，实际上是∆类1.2.在无限时间跳跃运算下是封闭的，因此由一个显著的无限时间图灵度的一部分。

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