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

经典有限时间可计算性理论的许多基本构造延续到无限的时间语境。例如，我们可以证明smn定理的无限时间相似性、递归定理和无穷大的不可判定性时间停滞问题，本质上是经典论点。其他一些经典事实，但是，不要直接一概而论。例如，在无限时间的情况下，这是不正确的。如果函数f的图是半可判定的，那么该函数是可计算的。这是以下情况的结果：

定理1（损失旋律定理）。存在一个实c，使得{c}是无限时间可判定的，但是c是不可写的。

真正的c，一首丢失的旋律，你不能自己唱，尽管你能认出。当有人唱给你听时，它是或否，表现出足够的内部结构，{c}是可决定，但本身太复杂，无法写入。也就是说，我们可以识别给定实数y是否为c，但我们不能从无到有产生c。函数f（x）=c

因此，常数值c是不可计算的，因为c不可写，但图是可判定的，因为我们可以识别一对是否具有形式（x，c）。

停顿问题的无限时间模拟分为黑体和黑体版本，h={p|ξp（p）↓ } 并且H＝{（p，x）|ξp（x）↓ }, 分别地这都是半可判定和不可判定，但在无限上下文中，它们不是可计算的相等的预言计算的概念上升到无限的上下文中，并产生了一个理论相对可计算性和丰富的学位结构。与经典理论相反。

然而，在N上，在无限时间的上下文中，我们有两种自然的神谕可供使用在oracle计算中，对应着二阶性的理论。第一个人可以使用一个真正的个人作为神谕，完全按照经典的方式，通过连接一个oracle磁带，上面写着real的值。这相当于修复一个补充输入参数，可以被视为产生了黑体理论无限可计算性，就像在描述性中允许任意实参数一样黑体∆的集论处理∼1.1.和π∼1.1.（我们将明确采用这样的黑体透视我们在无限时间下等价关系理论中的应用还原性。）然而，第二，人们自然希望以某种方式使用一组real作为甲骨文，尽管我们一般不能指望在磁带上写下这样的一套（也许它甚至是不可计数的）。相反，oracle磁带在计算开始时是空的，并且在计算期间，机器可以在该磁带上自由地写入；每当算法调用它时，机器可能会进行成员身份查询，询问是否真实当前写在oracle磁带上的是否是oracle的成员。因此，该机器能够知道它能产生的任何真实，无论真实是否在预言集中。

这样的预言计算产生了相对可计算性的概念p（x）和

因此，一个无穷时可变约简a≤∞B的概念及其伴随式无限时度关系A lect∞B。对于任意一个集合A，我们都有光面跳跃A▽。而黑体跳跃AH，对应于两个停顿问题，与A相对应。

黑体跳跃比浅色跳跃高得多，因为[HL00]确定了A＜∞A▽ ＜∞ 啊，还有A▽H≠∞AH和许多其它有趣的相互作用。波斯特问题的无限时间相似性，即是否存在介于0和跳跃0之间的中间半可判定度▽, 由[HL02]于解决一个双向切入的答案：

定理2。波斯特问题的无限时间模拟既有肯定的解决方案，也有否定的解决方案。

（1） 不存在0＜∞z＜∞0的实数z▽.

（2） 存在实数A的集合，其中0＜∞A＜∞0▽. 事实上，实A的半可判定集是不可比的。

意外可写实数的度数是线性排序的，实际上形成了有序类型ζ+1的有序层次，这也对应于它们在任何计算中最早出现的顺序。在其他作品中，Welch[Wel99]在无限时间的图灵度。Hamkins和Seabold[HS01]分析了一个磁带与多带无限时间图灵机和Benedikt L¨owe[L¨01]观察了无限时间图灵机与真理修正理论之间的联系。

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