摘要：我们描述了无限时间图灵机的基本理论和最近的一些生长，包罗无限时间度理论，无限时间庞大性理论，以及无限时间可盘算模型理论。我们特别关注的是无限时间图灵机上等价关系的条理分析reals，类似于由Borel可约性发生的理论。我们界说了一个看法具有无限的时间可约性，这将Borel理论的大部门提升到?类～1.2.在一个令人满意的方式。
无限时间图灵机卓有成效地扩展了普通图灵机的运算到超限有序时间，并通过这样做提供了关于的可盘算性的鲁棒理论reals。荟萃论、描述性荟萃论和在可盘算性理论中，该要领在实数上提供了无限的可盘算性和可判定性看法，这些看法以非平凡的方式攀升到描述性荟萃论条理（?1.2.)同时保持强盘算性质。无限的时间图灵机，我们有无数经典看法的无限类似物，包罗无限时间图灵度，无限时间庞大性理论，无限时间可盘算模型理论，现在也是Borel等价理论的无限时间模拟Borel可约性下的关系。
在这篇文章中，我们将简要回首机械及其基本理论，以及然后更详细地解释我们最近将无限时间可盘算性应用于Borel等价关系理论的相似性，在[CH11]中给出了对其的完整描述。
这个应用法式的基本思想是通常取代Borel可约性的看法在该理论中使用了具有无限时间可盘算可约性形式，并研究了陪同的等价关系条理。这种要领保留了大部门Borel分析和结果，同时也分析了似乎超出Borel理论规模的等价关系条理的一部门，包罗许多高度规范的等价关系无限时间可盘算但不是Borel的等价关系，例如可数结构的差异类的同构关系。
本文的主要部门改编自视察[Ham07]和[Ham05]以及来自我们关于无限时间可盘算等价关系的文章[CH11]。无限的时间Hamkins和Kidder于1989年首次研究了图灵机，Hamkins和Lewis提供了焦点介绍[HL00]。这一理论现在已经获得了扩展许多其他人，包罗Philip Welch、Peter Koepke、Benedikt L¨owe、Daniel Seabold，拉尔夫·辛德勒、维奈·德奥拉利卡、拉塞尔·米勒、史蒂夫·华纳、贾科莫·伦齐、埃里希·蒙特里昂、塞缪尔·科斯基等人。该理论的许多前身包罗BlumShub-Smale机械（20世纪80年代）、Büuchi机械（60年代）及其陪同的生长，Barry Burd的极限“模糊”图灵机模型（1970年代），α-递归和E递归理论的广泛生长，高等递归理论的一部门（自20世纪70年代）、Jack Copeland的加速图灵机（20世纪90年代）、Ryan Bissell Siders的序数机（90年代），以及最近的Peter Koepke的序数图灵机和序数寄存器机（2000年代）。涉及无限时间图灵的扩展文学机械包罗[HL00]、[Wel99]、[Wel00a]、[Wel00b]、[L¨01]、[HS01]、[HL02]、[Sch03]，[HW03]、[Ham02]、[Ham04]、[LM04]、[DHS05]、[HMSW07]、[Ham05]、[Wel]、[Wel05]、[Coe05]，[Ham07]、[HM09]、[HM07]和其他。
1.无限时间图灵机综述
无限时间图灵机的硬件与它们的经典有限时间机完全相同时间对应物，头在半无限长的纸带上来回移动，凭据有限多个有限法式的严格指令写0和1州。关于无限时间图灵机的新之处在于，它们的运算被扩展到超限有序时间。为了方便起见，这些机械接纳三磁带模型，具有用于输入、暂存和输出的独立磁带。机械
q
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.在无限时间跳跃运算下是关闭的，因此由一个显著的无限时间图灵度的一部门。
尽管超限，但盘算本质上是可数的，因为共最终性论证证明，每一次盘算要么暂停，要么重复一些可数序数阶段。如果存在盘算，则序数α被认为是可计时的恰好停在α上第th步。如果实数x是盘算的输出ξp（0），则实数x是可写的，而序数是可写的，如果它是由这样的实数编码的。因为只有可计数的在许多法式中，因此只有可计数的多个可计时和可写的序数。可计时和可写的序数扩展到所有递归序数和远远超出；它们的上确界是递归不行会见的等等。可写的序数形成序数的初始段，因为每当一个序数是可写的，那么编写它的算法就可以很容易地修改为任何较小的序数编写代码。但是对于可计时的序数来说，情况并非如此；在可计时的序数中，有无（无参数）无限时间图灵的越来越庞大的禁区机械可能会停下来。
让我们快速勾勒出这样一个论点，即可计时序数中存在这样的差距，因为这是有序反射中一个有趣的练习，它组成了许多要领的基本要领厥后的理论建构。考虑模拟上所有法式的算法同时输入0，通过一些保留和治理sufi的记账要领-每个法式都有足够的独立空间，模拟ω每个法式的许多盘算步骤在每个ω实际盘算的许多步骤中。我们的算法可能会仔细跟踪哪些法式已经停止，并注意找到没有法式停止的阶段。由于这样一个阶段存在于所有可计时序数的上确界之上，我们最终一定会找到这样的舞台。由于我们的算法可以识别第一个在这样的阶段，我们可以部署它在这一发现后立即停止。因此，我们描述了一种盘算历程，它将在比没有盘算停止的阶段，因此在可计时的序数中存在间隙，如渴望的对该算法的仔细分析讲明，任何可计时序数之后的第一个间隙都具有阶型ω，本质上是因为ω需要许多特别的步骤才气实现已经到达了一个缺口。革新的算法搜索更长的间隙，并讲明必须是在越来越庞大的可容许极限阶段越来越庞大任何可计时或可写的序数α，都存在巨细至少为α的间隙。这些的结构gap体现出与无限时间停顿问题相同的庞大性。
尽管在[HL00]中已经确定了可计时和可写的序数同样的订单类型，也许该论文中留下的主要问题是这些序数的上确界是相同的。这件事获得了菲利普的肯定Welch在[Wel00b]。另一种描述结果的方式是，每当法式打开输入x发生一个停止的盘算，然后有另一个盘算写出该盘算的证书，整个盘算历史的真实编码，包罗有序关系，其顺序类型是盘算的长度。这很重要事实远非显而易见，它依赖于对最终可写性的微妙处置惩罚，并组成这是该理论许多进一步生长的基础，包罗我们的应用在本文中提及。
上述计数论证的反映方面包罗视察到可能遇到的实数的任何可判定性质在盘算历程中，必须持有一个可写的实数，因为我们可以开始盘算搜索以找到这样的见证并在找到时输出它。这个想法极大地推广了Philip Welch的λ-ζ-∑定理。具体而言，[HL00]界说如果存在x泛起在从上的某个点输出磁带（纵然盘算没有停止），而且如果x在盘算期间的任何阶段泛起在任何磁带上，则它是意外可写的。通过用实数编码序数，我们获得了最终可写和意外可写的看法序数。如果λ是可计时或可写序数的上确界，则ζ是最终可写序数，∑是意外可写序数的上确界，则[HL00]建设λ＜ζ＜∑。Welch[Wel00a]断言的λ-ζ-∑定理。
此外，Lλ?∑1Lζ图案这个结果准确地表达了算法可能会下降的意义见证人从意外可写领域进入最终可写或可写领域王国。证明和结果的焦点是每一次盘算都是重复的∑阶段的ζ配置。
经典有限时间可盘算性理论的许多基本结构延续到无限的时间语境。例如，我们可以证明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]视察了无限时间图灵机与真理修正理论之间的联系。
2.一些应用和扩展
让我们简要介绍一下最近的生长和无限时间的延伸图灵机，如无限时间庞大性理论的兴起和介绍无限时间可盘算模型理论。在此之后，在以下部门中，我们将更详细地介绍无限时间图灵机在类似于Borel等价关系理论。
Ralf Schindler[Sch03]通过求解P与NP问题的无限时间图灵机模拟。界说多项式类P在无限时间的上下文中，Schindler简朴地视察到所有实数具有长度ω，且ω的多项式函数受形式为ωn的多项式函数的约束。
因此，他界说了一个荟萃a?R在P中，如果有一个法式P和一个自然数n使得p决定A，并在ωn之前的时间内停止所有输入.荟萃A在NP中，如果存在是法式p和自然数n使得x∈a当且仅当存在y使得p接受（x，y），而且p在小于ωn的时间内停止所有输入Schindler证明了P≠NP
对于[Sch03]中的无限时间图灵机，使用从描述集理论到分析类P和NP的庞大性。这已经在联合中推广对[DHS05]进行如下运算，其中类co-NP由荟萃的补集组成在NP中。
定理3.
P≠关于无限时间图灵机的NP?co-NP。
此证明泛起在[DHS05]中。由此可见，P≠无限时间图灵机的NP。（这个结果与有限经典P无关≠NP问题。）
P背后的一些结构性原因≠NP?co-NP是通过放置类来揭示的使用盘算的庞大性类Pα和NPα的较大条理中的P和NP巨细限制在α以下。[DHS05]中的结果讲明，例如，类NPα对于ω+2≤α≤ω1是相同的CK，但无论如何，Pα+1（任何可计时极限的Pα+2序数α。如下所示，由于Pα在类NPα≠co-NPα的同时稳步增加保持稳定，对于ω+2≤α＜ω1的任何序数α，Pα
因此，P≠NP?co-NP。然而，我们在上确界ω1处获得相等CK与Pω1CK=NPω1CK?co-NPω1CK。
事实上，这是等式?1的一个例子
1 =Σ11∩Π11.，从而可以开始看看无限时间图灵机理论是如何自然地生长成描述集的学说
这种相同的不等式模式Pα（NPα，
当α严格位于可计时序数的连续块内时，对于在可计时序数中开始间隙的任何β，对应的Pβ=NPβ≠co-NPβ。在里面
此外，对于其他庞大度类P+、P++和PfBenedikt L¨owe已经引入了PSPACE的类似物。
在[HMSW07]中介绍了无限时间可盘算模型理论的主题。
可盘算模型理论是着眼于结构和理论的可盘算性的模型理论。无限时间可盘算模型理论利用无限时间图灵机提供的无限时间可算性看法来执行该法式。经典理论始于几十年前，其主题包罗可盘算完备性（每个可判定理论都有可判定模型吗？）和可盘算分类性（每个同构的可盘算模型对都有可盘算同构吗？），该领域现在已经成熟为庞大度谱的庞大分析可数模型和理论。
更广泛配景的动机是，虽然经典的可盘算模型理论一定局限于可数模型和理论，无限可盘算性上下文允许建设在现实基础上的无数模型和理论。可盘算模型理论中的许多盘算结构都是从建设在N，使用有限时间可盘算性，到建设在R上的结构，使用无限时间可盘算。不行计数的上下文打开了新的问题，例如无限可盘算L¨owenheim-Skolem定理，它没有有限时间的相似性。几个最自然问题被证明是独立于ZFC的。
在联合事情[HMW07]中，我们界说了一个模型a=hA。i是无限时间可盘算的，如果A?R是可判定的，而且所有函数、关系和常数都是一致的无限时间，可凭据其G模型代码和输入进行盘算。结构A是可判定的，如果可以盘算出A|=[?一]给定pΓq和?一理论T是无限时间可判定的，如果关系T?Γ在pΓq中是可盘算的。因为我们想处置惩罚不行计数的语言，G模型代码的自然上下文是R而不是N。
虽然，最初的问题是完全性定理的无限时间可盘算模拟：每个一致的可判定理论都有一个可判定模型吗？这个这个答案和ZFC无关。
定理4（[HMSW07]）。完全性定理的无限时间可盘算模拟独立于ZFC。明确地：
（1）如果V=L，那么每个一致的无限时间可判定理论都有一个无限时间可决定模型，在语言的可盘算翻译中。
（2）与ZFC相对一致的是，在可盘算泛起的语言，在中没有无限时间的可盘算或可判定模型该语言的任何翻译。
（1）的证明使用了体现良好的语言L的看法，对于该语言存在符号hsα|α＜δi的枚举使得从任何psαq可以一致盘算先验符号hpsβq|β≤αi的代码。可以证明每一个一致的在一个体现良好的语言中的可判定理论有一个可判定模型，如果V=L，那么每一种可盘算语言都有一个体现良好的可盘算翻译。对于（2），一使用理论T扩展了hWO，lect i的原子图，同时断言f是select类上的选择函数。这是一个可判定的理论，但对于任何可盘算的模型A=hA，lect，fi的T，集{f（cu）|u∈WO}为∑1.2.而且具有基数ω1。众所周知与ZFC一致，即没有∑1.2.荟萃的巨细为ω1。
对于L¨owenheim-Skolem定理的无限时间类似物，我们证明了每一个充实泛起的无限时间可判定模型都有一个适当的向上版本具有可判定体现的初等扩展，对于向下的版本，每个充实体现的不行数可判定模型都有一个可数可判初等下部结构。的完全直接推广有很强的反例。
然而，L¨owenheim-Skolem定理，因为[HMW07]在整个实数集上提供了一个可盘算结构hR，Ui，它没有合适的可盘算初等子结构。
一些最有趣的事情涉及可盘算商。结构具有无限时间可盘算体现，如果它同构于可盘算结构，以及具有可盘算商体现，如果它同构于可盘算的商结构通过可盘算的等价关系（同余）。对于N上的结构，在无论是在有限的照旧无限的时间配景下，这些看法都是等价的，因为人们可以可盘算地找到任何等价类的最小元素。然而对于R上的结构，盘算每个等价类的这种可区分元素并不总是可能的。
问题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.
如果它由等价∑界说～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]贾科莫·伦齐和埃里希·蒙特里昂。关于不动点算术和无限时间图灵机。
信息处置惩罚信函，91（3）：121-1282004。
[Sch03]拉尔夫·迪特尔·辛德勒。P≠无限时间图灵机的NP。马西马蒂克国王，139(4):335–340， 2003.
[ST11]Scott Schneider和Simon Thomas。可数的Borel等价关系。在阿巴拉契亚地域理论2006–2010、2011。
菲利普·韦尔奇。关于Deolalikar、Hamkins和Schindler的问题。
菲利普·韦尔奇。弗里德曼的诀窍：无穷时间图灵度中的极小性论点。在“荟萃《美国手语逻辑学术讨论会论文集》，258:425-4361999年。
菲利普·韦尔奇。最终无限时间图灵机度：无限时间可判定实数。符号逻辑杂志，65（3）：1193–12032000。
菲利普·韦尔奇。无限时间图灵机盘算的长度。伦敦公报数学学会，32（2）：129-1362000。
菲利普·韦尔奇。1个磁带图灵机的超限行动。巴里·S·库珀和贝内迪克特L¨owe，编辑，《新盘算范式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。
施普林格Verlag多伦多大学街222号菲尔德学院m5t3j1&约克大学
安简陋省多伦多市基勒街4700号罗斯N520数学与统计系
纽约都市大学研究生中心，数学项目，365第五名
纽约大道，邮编：10016&州立大学库尼岛分校，数学，2800胜
纽约州斯塔滕岛林荫大道10314