超小小中大超大

数学论文（无限时间图灵机）

好书推荐：数学联邦政治世界观、万人迷她又被强取豪夺了、惊世狂妃：皇叔一宠到底、冷宫九公主要翻身、恋与伤、多重宇宙：离婚后，为她一夜白头、穿书后恶毒女配只想修仙、喜美：朦胧梦境、粼深时见古、我在泰娱哦！、

注：本章（2/2）！

问题5. 每一个具有无限时间可计算商表示的结构都有一个无限时间可计算表示？

在有限时间理论中，或者对于N上的结构，答案当然是肯定的。但在R上结构的完全无限时间上下文，答案取决于集合论背景

定理6. 问题5的答案与ZFC无关。明确地

（1）与ZFC相对一致的是，具有无限时间的每个结构都是可计算的商表示具有无限时间的可计算表示。

（2）与ZFC相对一致的是，有一个结构具有无限时间可计算的商表示，但没有无限时间可可计算的表示。

让我们简要概述一下证据中出现的一些想法。为了建造结构的无限时间可计算表示，给定可计算商表示，我们想以某种方式从每个等价类中选择一个代表，在计算有效的方式，并在这些代表的基础上构建一个结构。在下面集合论假设V=L，我们可以附加到每个等价的L-东成员真正的A级护卫，其力量足以表明它是其L东部成员类，并用这些被护送的实数对构建一个可计算的表示。（特别是，新的演示文稿不仅仅是由原始类别的代表构建的，因为这些real可能太弱；他们需要护送人员的帮助。）因此，如果V＝L，那么每个具有可计算商表示的结构都具有可计算表示。

在独立性的另一方面，我们用强迫的方法证明了陈述2。

结构hω1，＜i总是有一个由实数编码的良好阶建立的可计算商表示，但存在没有无限时间可计算集的强迫扩展在描述性集合论的基础上，大小为ω1。因此，在这些扩展中，hω1，＜i具有可计算的商表示，但没有可计算的表示。

让我们也简要讨论一些有序计算的替代模型这是无限时间图灵机所产生的。Peter Koepke[Koe05]介绍了序图灵机，它通过扩展来推广无限时间图灵机胶带超限序数长度。相应地调整了限额规则，以便这台机器可以利用这个额外的空间。具体来说，而不是使用特殊的极限状态，序数图灵机在它们的（有限多个）上有一个固定的阶状态，并且在任何极限阶段，该状态被定义为先前状态的lim-inf。这个然后将磁头位置定义为机器运行时磁头位置的lim-inf之前处于所产生的极限状态。为了一致性，Koepke定义磁带的单元使用先前单元值的lim-inf（而不是使用无限时间图灵机）。如果头部在极限位置从单元格向左移动，则它一直出现在第一个单元格的左侧。

因此，这些机器为序数上的函数提供了计算模型，以及序数类的可判定性概念。主要定理是的幂这些机器本质上与G模型的可构建宇宙的机器相同。

定理7（Koepke）. 序数图灵机可判定的序数集，具有有限许多序数参数正是G模型的可构造宇宙L中的序数集。

其他几种序数计算的无限模型都是基于序数寄存器的概念，并产生了丰富的理论。参见[Koe05]、[KS06]、[KK06]、[CS09]，[CFK+10]、[HM07]、[HM09]和[HLM07]。

3.无限时间可计算等价关系理论

最近，我们介绍了Borel等价关系理论的自然相似性。其中将无限时间可判定关系与无限时间可计算归约函数进行比较。这在一定程度上是由于研究中的偶尔需要Borel等价关系超越了Borel。事实上，一个更强大的可约性概念可能能够准确地比较更复杂的关系。特别是，我们将能够考虑由于无限的时间复杂性而产生的新关系类。

我们首先简要介绍博雷尔等价关系的研究。这个这门学科的名称有点用词不当--实际上是研究的主要对象是标准Borel空间上的任意等价关系，即配备有完全可分度量空间的Borel结构。在应用程序中，我们想到等价关系表示来自的某个其他领域的分类问题数学例如，由于域为N的任何群都是由其乘法函数决定的，因此研究可数群的分类问题相当于×N的一个子空间上的同构等价关系。对于更多示例，请参见[ST11]的第1.2节。

Borel等价关系理论围绕以下关键概念展开复杂性如果E，F是标准Borel空间X，Y上的等价关系，则如下〔FS89〕和〔HK96〕我们说E是Borel可约为F，写成E≤BF，当存在Borel函数f:X→ Y使得

(1)x E x′⇐⇒ f（x）Ff（x′）。

Borel可约性度量等价关系的复杂性，而不是作为对的集合，而是分类问题。也就是说，如果E是Borel可约为F，那么的分类X到E的元素并不比Y到F的元素的分类难。

现在，Borel等价关系的经典且非常成功的研究包括两大努力。首先，人们希望绘制出众多之间的关系充分理解和自然发生的等价关系。其次，给一个现实生活分类问题应该通过将其与制定基准关系。

关于归约函数（在这种情况下，它们是Borel）的一些可定义条件是必需的事实上，如果没有任何这样的限制，还原性总是可以确定的仅凭基数。然而，也有通过不变量进行自然分类的情况其不能通过Borel归约函数来计算。例如，它是∆∼1.2.，而不是Borel计算可数扭阿贝尔群的经典Ulm不变量。一可能会倾向于形成∆的理论∼1.2.可还原性，但事实证明这个概念也是慷慨的事实上，正如我们将在下面的定理11中看到的，它可能包含大多数等价性关系合并为一个琐碎的复杂性类。

我们将在这里考虑可在无限时间内计算的约化函数图灵机（参见[CH11]以获得更完整的阐述）。因此，对于R上的任何两个等价关系E，F，我们说E是无限时间可计算可约为F，写E≤cF，如果存在无限时间可计算函数F（自由允许实参数）满足等式（1）。类似地，我们说E最终可约为F，写成E≤eF，如果存在满足等式（1）的最终可计算函数f。请注意由于所有不可数的标准Borel空间都是Borel同构的，我们不失去一般性通过限制我们与域R的等价关系。

当然，通过第1节中的评论（并再次强调我们允许参数），无限时间可计算的约简包括所有的Borel约简。

因此，我们的理论将扩展经典理论。相反，许多不可约性E6≤BF的经典证明依赖于测度、范畴或强迫等方法。因此，他们经常“过冲”，并表明不存在从E到F的减少，即Lebesgue可测量，Baire可测量，或绝对∆∼1.2.（下面讨论）。

由于无限时间可计算的和最终可计算的函数享有这三个函数在这些性质中，在每种情况下，都可以得出E≰cF，甚至E≰eF，以及因此，当我们从≤B层次转移到≤c和≤e层次时，不会有太多的“塌陷”层次结构。

可约性的无限时间概念与绝对∆的概念密切相关∼1.2.可还原性，Hjorth等人在文献中对此进行了讨论。回想一下子集A⊆R被认为是绝对∆∼1.2.

如果它由等价∑定义∼1.2.和π∼1.2.公式其在每个强制延伸中保持相等。函数f:R→ 据说R是绝对∆∼1.2.　

如果它的图{（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可归结为等式关系。

定理11. 如果V=L，则R上的每个无限时间可计算等价关系都是可约的通过一个无限时间半可计算函数将等式转化为等式关系。

定理11的证明使用了与定理6的证明相同的思想，并且参数，归约函数不是关系的选择器。另一方面在适当的确定性假设下，每个无限时间半可计算函数是勒贝格可衡量。在这种情况下，无限时间半可计算可约性再次出现类似于更具体的可约性概念。

我们已经看到，通过扩展可用的一类约简函数，我们有时能够考虑更广泛的一类等价关系。一个校正这方面的例子是以下可数Borel等价类的推广关系这里，Borel等价关系被认为是可数的，当每个等价类是可数的。可数关系已经成为古典理论中研究的最重要的集合之一，因为许多自然关系都处于这个层次在≤B条件下揭示其结构已取得基本进展。例如，通过Silver的一个经典结果，等式=是≤B-最小可数Borel等价关系。此外，根据Kechris Harrington-Louveau的一个深入结果，E0是不可约为=的≤Bleast-Borel等价关系。第三，我们已经做到了是一个≤B-最大可数Borel等价关系，表示为E∞。剩余的可数Borel等价关系位于区间（E0，E∞）中，并且是Adams-Kechris的一个结果这意味着在Borel的双重教育性之前存在着连续的许多不同的关系。

最后一个结果也适用于≤c和≤e可约性的情况，因为Adams和Kechris用来建立不可约性是测度论的。

我们现在定义了一类无限时间可计算关系，我们提出它是校正可数Borel等价关系的类似，并研究剩余结果的相应推广。这个想法来自于经典的证明关于E∞的最大性，这取决于可数的以下特征Borel等价关系。也就是说，E是一个可数的Borel等价关系，如果和只有当它允许Borel枚举，也就是说，Borel函数f使得f（x）编码一个所有x的[x]E的枚举。（此特性是描述集合论中的Lusin-Novikov定理。）概括起来，我们说等价关系E是（无限时间）可枚举的，如果存在无限时间可计算函数f，使得f（x）对所有x编码[x]E的枚举。最终类似地定义了可枚举等价关系。这是一个有价值的概括；例如，由x elec hyp y定义的关系，当x和y在一中是超对数的另一个是可枚举的，但不是Borel。

既然我们已经说过，E∞的最大性取决于可数Borel等价关系，并且由于我们已经定义了可数和最终，以类似的方式，E∞在Borel上下文中的最大性的证明在我们的上下文中产生了相同的可枚举等价关系。

定理12. E∞在可枚举关系中≤c-最大，在最终可列举的关系。

也许令人惊讶的是，我们也可以建立=的极小性。

定理13.=可通过连续的作用这一结果是一个直接的结果（最初是由于韦尔奇）存在一个完美的lect e∞-类集。（这里，lect e∞表示最终的度关系，它是定义类似于lect∞。）韦尔奇证明的思想是使用强迫理论L∑得到一个互一般Cohen实数的完美集，然后论证这个集做这项工作。为了看到定理13的成立，观察每个最终可枚举的关系E（作为一组对）包含在关系lect E∞中。因此存在一个完美的E类的集合，因此存在从=到E的连续约简。

最后，我们无法在等式上建立E0的极小性，我们将其作为一个问题。希望类似于证明的方法定理13将给出答案。

问题14。每一个可枚举等价关系E都是真的吗=否则E0可还原为E？

参考文献

[CFK+10]Merlin Carl、Tim Fischbach、Peter Koepke、Russell Miller、Miriam Nasfi和Gregor Weckbecker。

无限时间寄存器机的基本理论。拱数学逻辑，49（2）：249–2732010。

[CH11]Sam Coskey和Joel David Hamkins。无限时间可计算等价关系。圣母院

《形式逻辑杂志》，2011年。出现。

[DHS05]Vinay Deolalikar、Joel David Hamkins和Ralf Dieter Schindler。P≠无穷大的NPåco-NP计时机器。《逻辑与计算杂志》，15（5）：577-5922005年10月。

[FS89]哈维·弗里德曼和李·斯坦利。一类可数结构的Borel可约性理论。

J.符号逻辑，54（3）：894–9141989。

[Ham02]乔尔·大卫·哈姆金斯。无限时间的图灵机器。《心智与机器》，12（4）：521–5392002。（专门讨论超计算的特刊）。

[Ham04]乔尔·大卫·哈姆金斯。超级任务计算。在Boris Piwinger Benedikt L¨owe和Thoralf R¨asch，编辑，《计算的经典和新范式及其复杂性层次》，《逻辑趋势》第23卷，第141-158页。Kluwer学术出版社，2004年。2001年9月21日至24日在维也纳举行的“形式科学基础III”会议的论文。

[Ham05]乔尔·大卫·哈姆金斯。具有无限时间图灵机的无限可计算性。在巴里S。

Cooper和Benedikt L¨owe，编辑，《新计算范式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。CiE，Springer Verlag。

[Ham07]乔尔·大卫·哈姆金斯。无限时间图灵机综述。在J´erõome Durand Lose and Maurice Margenstern，编辑，《机器、计算和普遍性——2007年第五届MCU国际会议》，《计算机科学讲义》第4664卷，法国奥尔良，2007年。

[Hjo00]Greg Hjorth。分类和轨道等效关系，《数学调查》第75卷专著。美国数学学会，普罗维登斯，RI，2000年。

[HK96]Greg Hjorth和Alexander S.Kechris。Borel等价关系和可数模型的分类。Ann.纯应用。逻辑学，82（3）：221-2721996。

[HL00]乔尔·大卫·哈姆金斯和安迪·刘易斯。无限时间图灵机。J.符号逻辑，65（2）：567–604, 2000.

[HL02]乔尔·大卫·哈姆金斯和安迪·刘易斯。Post的超级任务问题既有积极的解决方案，也有消极的解决方案。数理逻辑档案，41（6）：507–5232002。

[HLM07]乔尔·大卫·哈姆金斯、大卫·莱涅茨基和拉塞尔·米勒。快速决策的复杂性ORM可判定集。Barry Cooper、Benedikt L¨owe和Andrea Sorbi，《计算》杂志编辑和现实世界中的逻辑-第三届欧洲可计算性会议CiE 2007，第4497卷论文集，《计算机科学讲义》，意大利锡耶纳，2007年。

[HM07]乔尔·大卫·哈姆金斯和拉塞尔·米勒。有序寄存器机的Post问题。在巴里Cooper、Benedikt L¨owe和Andrea Sorbi，《真实世界中的计算与逻辑》的编辑-第三届欧洲可计算性会议CiE 2007，论文集第4497卷，讲义计算机科学，意大利锡耶纳，2007年。

[HM09]乔尔·大卫·哈姆金斯和拉塞尔·米勒。有序寄存器机的Post问题：一个显式方法《纯粹与应用逻辑年鉴》，160（3）：302-3092009。

[HMW07]J.D.Hamkins、R.Miller、D.Seabold和S.Warner。无限时间可计算模型理论。在里面S.B.Cooper、Benedikt L¨owe和Andrea Sorbi，编辑，《新计算范式：变化》《什么是可计算的概念》，第521–557页。施普林格，2007年。

[HS01]乔尔·大卫·哈姆金斯和丹尼尔·西博尔德。只有一个磁带的无限时间图灵机。《数理逻辑季刊》，47（2）：271–2872001。

[HW03]乔尔·大卫·哈姆金斯和菲利普·韦尔奇。Pf≠NPf对于几乎所有的f。《数理逻辑季刊》，49(5):536–540, 2003.

[KK06]Peter Koepke和Martin Koervien。顺序计算。数学结构计算。Sci。，16(5):867–884, 2006.

[Koe05]彼得·科普克。序数上的图灵计算。符号逻辑公报，11（3）：377–3972005年9月。

[KS06]Peter Koepke和Ryan Siders。在序数上注册计算。提交至：数学逻辑档案馆，2006年。

[KS09]Peter Koepke和Benjamin Seyfferth。序数机和容许递归理论。安。

纯应用程序。逻辑，160（3）：310–3182009。

[L¨01]Benedikt L¨owe。修订顺序和计算机n无限长的时间。逻辑计算。，11(1):25–40, 2001.

[LM04]贾科莫·伦齐和埃里希·蒙特里昂。关于不动点算术和无限时间图灵机。