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

如果它的图{（x，n）|f（x）∈Bn}是绝对∆∼1.2.（此处，Bn贯穿R的基本开子集）。据我们所知，很少有自然发生的病例

绝对存在∆∼1.2.两个等价关系而非无穷大之间的归约时间可计算缩减。并且当存在无限时间可计算缩减时，人们可以通过简单地“编码”实现见证约简函数的算法来证明这一点。这种计算方法可能更满足而不是抽象地定义一个归约函数并验证它是∆∼1.2.总共强制扩展。另一方面，我们没有任何通用工具来建立超越已建立的无限时间可计算函数的不可约性上述工具，所有这些工具都通过绝对∆建立了不可还原性∼1.2.功能已经Hjorth和Kanovei建立绝对∆的不可还原性的结果的简要总结∼1.2.函数可以在[CH11]的第5节中找到。一些更深的关于这个可约性概念的结果可以在[Hjo00]的第9章中找到。

对于“编码”一个新的（非Borel）归约函数的例子，考虑Eck如果x和y计算（在普通意义上）相同的序数，则x和y定义的关系。

我们将其与关系进行比较=WO，这只是限于井阶的代码集的同构关系。Borel无法比较这两种关系削减；然而，它们是密切相关的，这一点可以通过以下内容来明确后果

定理8. Eck和≌WO是无限时间的可计算双可教育性。

例如，有一个直观的减少从Eck到≌WO——即将x映射到代码对于从x可计算（在普通意义上）的序数的上确界。事实上，这种直觉很容易转化为无限时间图灵的程序机器简单地说，该程序只是模拟所有普通的图灵计算考察每一个列举的真实性。每当这些real中的一个被视为好的顺序，这个代码被添加到一个列表中。最后，程序计算并输出一个代码为其列表中的序数的上确界。

使用无限时间可计算并最终可计算的另一个明显好处减少是为了处理在研究无限时间复杂度类。作为一个非常简单的例子，考虑其中的两个这类等价关系中最重要的一类：无穷时度关系lect∞在第1节中介绍了，并且由定义的（光面）跳跃等价关系xJy当且仅当x▽ ≡∞ y▽. 我们有以下关系（有些琐碎）两者之间。

定理9. J最终可通过计算无限时间的函数降为lect∞一个真实的跳跃。

见证这一过程的程序只是在输入时模拟所有无限时间的程序x、 并且每当其中一个暂停时，将其索引添加到其输出磁带上的列表中。由于所有将在阶段λ停止的程序，输出磁带最终将显示x▽.

同时，下一个结果给出了不可约性结果的采样，可以是使用上述Hjorth和Kanovei的方法获得。这里=当然表示R上的相等关系，E0是由x定义的几乎相等关系当且仅当几乎所有n的x（n）=y（n）。接下来，≌HC表示同构关系限于可遗传可数集的代码集。最后，Eset表示由x-Esety定义的关系，如果x和y被认为是实数的可数序列的码，枚举同一集合。

定理10.

（1） E0不是无限时间可计算地减少到＝。

（2） Eset不是无限时间可计算地减少到E0。

(3) ≌HC和Eset不是无限时间可计算地减少到≌两个。

如果没有强的集合论假设，就不能得到这样的结果来进行约简比绝对∆更通用的函数∼1.2.功能。例如

无限时间半可计算归约函数仍然在∆类中∼1.2.，但如果我们允许这个类中的约简函数，那么中的所有等价关系定理10可归结为等式关系。

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