无限时间图灵机
摘要：我们描述了无限时间图灵机的基本理论和最近的一些发展，包括无限时间度理论，无限时间复杂性理论，以及无限时间可计算模型理论。我们特别关注的是无限时间图灵机上等价关系的层次分析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]。这一理论现在已经得到了扩展许多其他人，包括PhilipWelch、PeterKoepke、BenediktL¨owe、DanielSeabold，拉尔夫·辛德勒、维奈·德奥拉利卡、拉塞尔·米勒、史蒂夫·华纳、贾科莫·伦齐、埃里希·蒙特里昂、塞缪尔·科斯基等人。该理论的许多前身包括BlumShub-Smale机器（20世纪80年代）、Büuchi机器（60年代）及其伴随的发展，BarryBurd的极限“模糊”图灵机模型（1970年代），α-递归和E递归理论的广泛发展，高等递归理论的一部分（自20世纪70年代）、JackCopeland的加速图灵机（20世纪90年代）、RyanBissellSiders的序数机（90年代），以及最近的PeterKoepke的序数图灵机和序数寄存器机（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州。关于无限时间图灵机的新之处在于，它们的运算被扩展到超限有序时间。为了方便起见，这些机器采用三磁带模型，具有用于输入、暂存和输出的独立磁带。机器
input：00111100...
scrαtch：11010010...
output：00101011...
根据到程序指令。计算被简单地扩展到限制有序阶段定义机器的极限配置。其想法是尽可能多地保留计算到那个阶段为止一直在创建的信息，将其保留在极限配置中，作为早期配置的一种极限。明确地在任何极限有序阶段ξ，机器进入我们所说的极限状态，其中一个区分状态以及开始状态和停止状态；磁头被重置为第一个单元在左边；并且磁带的每个单元都用先前值的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的hn，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产生一个停止的计算，然后有另一个计算写出该计算的证书，整个计算历史的真实编码，包括有序关系，其顺序类型是计算的长度。这很重要事实远非显而易见，它依赖于对最终可写性的微妙处理，并构成这是该理论许多进一步发展的基础，包括我们的应用在本文中提及。
上述计数论证的反映方面包括观察到可能遇到的实数的任何可判定性质在计算过程中，必须持有一个可写的实数，因为我们可以开始计算搜索以找到这样的见证并在找到时输出它。这个想法极大地推广了PhilipWelch的λ-ζ-∑定理。具体而言，[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的概念及其伴随式无限时度关系Alect∞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]分析了一个磁带与多带无限时间图灵机和BenediktL¨owe[L¨01]观察了无限时间图灵机与真理修正理论之间的联系。
2.一些应用和扩展
让我们简要介绍一下最近的发展和无限时间的延伸图灵机，如无限时间复杂性理论的兴起和介绍无限时间可计算模型理论。在此之后，在以下部分中，我们将更详细地介绍无限时间图灵机在类似于Borel等价关系理论。
RalfSchindler[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++和PfBenediktL¨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，lecti的原子图，同时断言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具有可计算的商表示，但没有可计算的表示。
让我们也简要讨论一些有序计算的替代模型这是无限时间图灵机所产生的。PeterKoepke[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)xEx′⇐⇒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等价关系。此外，根据KechrisHarrington-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的枚举。最终类似地定义了可枚举等价关系。这是一个有价值的概括；例如，由xelechypy定义的关系，当x和y在一中是超对数的另一个是可枚举的，但不是Borel。
既然我们已经说过，E∞的最大性取决于可数Borel等价关系，并且由于我们已经定义了可数和最终，以类似的方式，E∞在Borel上下文中的最大性的证明在我们的上下文中产生了相同的可枚举等价关系。
定理12.E∞在可枚举关系中≤c-最大，在最终可列举的关系。
也许令人惊讶的是，我们也可以建立=的极小性。
定理13.=可通过连续的作用这一结果是一个直接的结果（最初是由于韦尔奇）存在一个完美的lecte∞-类集。（这里，lecte∞表示最终的度关系，它是定义类似于lect∞。）韦尔奇证明的思想是使用强迫理论L∑得到一个互一般Cohen实数的完美集，然后论证这个集做这项工作。为了看到定理13的成立，观察每个最终可枚举的关系E（作为一组对）包含在关系lectE∞中。因此存在一个完美的E类的集合，因此存在从=到E的连续约简。
最后，我们无法在等式上建立E0的极小性，我们将其作为一个问题。希望类似于证明的方法定理13将给出答案。
问题14。每一个可枚举等价关系E都是真的吗=否则E0可还原为E？
参考文献
[CFK+10]MerlinCarl、TimFischbach、PeterKoepke、RussellMiller、MiriamNasfi和GregorWeckbecker。
无限时间寄存器机的基本理论。拱数学逻辑，49（2）：249–2732010。
[CH11]SamCoskey和JoelDavidHamkins。无限时间可计算等价关系。圣母院
《形式逻辑杂志》，2011年。出现。
[DHS05]VinayDeolalikar、JoelDavidHamkins和RalfDieterSchindler。P≠无穷大的NPåco-NP计时机器。《逻辑与计算杂志》，15（5）：577-5922005年10月。
[FS89]哈维·弗里德曼和李·斯坦利。一类可数结构的Borel可约性理论。
J.符号逻辑，54（3）：894–9141989。
[Ham02]乔尔·大卫·哈姆金斯。无限时间的图灵机器。《心智与机器》，12（4）：521–5392002。（专门讨论超计算的特刊）。
[Ham04]乔尔·大卫·哈姆金斯。超级任务计算。在BorisPiwingerBenediktL¨owe和ThoralfR¨asch，编辑，《计算的经典和新范式及其复杂性层次》，《逻辑趋势》第23卷，第141-158页。Kluwer学术出版社，2004年。2001年9月21日至24日在维也纳举行的“形式科学基础III”会议的论文。
[Ham05]乔尔·大卫·哈姆金斯。具有无限时间图灵机的无限可计算性。在巴里S。
Cooper和BenediktL¨owe，编辑，《新计算范式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。CiE，SpringerVerlag。
[Ham07]乔尔·大卫·哈姆金斯。无限时间图灵机综述。在J´erõomeDurandLoseandMauriceMargenstern，编辑，《机器、计算和普遍性——2007年第五届MCU国际会议》，《计算机科学讲义》第4664卷，法国奥尔良，2007年。
[Hjo00]GregHjorth。分类和轨道等效关系，《数学调查》第75卷专著。美国数学学会，普罗维登斯，RI，2000年。
[HK96]GregHjorth和AlexanderS.Kechris。Borel等价关系和可数模型的分类。Ann.纯应用。逻辑学，82（3）：221-2721996。
[HL00]乔尔·大卫·哈姆金斯和安迪·刘易斯。无限时间图灵机。J.符号逻辑，65（2）：567–604，2000
[HL02]乔尔·大卫·哈姆金斯和安迪·刘易斯。Post的超级任务问题既有积极的解决方案，也有消极的解决方案。数理逻辑档案，41（6）：507–5232002。
[HLM07]乔尔·大卫·哈姆金斯、大卫·莱涅茨基和拉塞尔·米勒。快速决策的复杂性ORM可判定集。BarryCooper、BenediktL¨owe和AndreaSorbi，《计算》杂志编辑和现实世界中的逻辑-第三届欧洲可计算性会议CiE2007，第4497卷论文集，《计算机科学讲义》，意大利锡耶纳，2007年。
[HM07]乔尔·大卫·哈姆金斯和拉塞尔·米勒。有序寄存器机的Post问题。在巴里Cooper、BenediktL¨owe和AndreaSorbi，《真实世界中的计算与逻辑》的编辑-第三届欧洲可计算性会议CiE2007，论文集第4497卷，讲义计算机科学，意大利锡耶纳，2007年。
[HM09]乔尔·大卫·哈姆金斯和拉塞尔·米勒。有序寄存器机的Post问题：一个显式方法《纯粹与应用逻辑年鉴》，160（3）：302-3092009。
[HMW07]J.D.Hamkins、R.Miller、D.Seabold和S.Warner。无限时间可计算模型理论。在里面S.B.Cooper、BenediktL¨owe和AndreaSorbi，编辑，《新计算范式：变化》《什么是可计算的概念》，第521–557页。施普林格，2007年。
[HS01]乔尔·大卫·哈姆金斯和丹尼尔·西博尔德。只有一个磁带的无限时间图灵机。《数理逻辑季刊》，47（2）：271–2872001。
[HW03]乔尔·大卫·哈姆金斯和菲利普·韦尔奇。Pf≠NPf对于几乎所有的f。《数理逻辑季刊》，49(5):536–540，2003
[KK06]PeterKoepke和MartinKoervien。顺序计算。数学结构计算。Sci。，16(5):867–884，2006
[Koe05]彼得·科普克。序数上的图灵计算。符号逻辑公报，11（3）：377–3972005年9月。
[KS06]PeterKoepke和RyanSiders。在序数上注册计算。提交至：数学逻辑档案馆，2006年。
[KS09]PeterKoepke和BenjaminSeyfferth。序数机和容许递归理论。安。
纯应用程序。逻辑，160（3）：310–3182009。
[L¨01]BenediktL¨owe。修订顺序和计算机n无限长的时间。逻辑计算。，11(1):25–40，2001
[LM04]贾科莫·伦齐和埃里希·蒙特里昂。关于不动点算术和无限时间图灵机。
信息处理信函，91（3）：121-1282004。
[Sch03]拉尔夫·迪特尔·辛德勒。P≠无限时间图灵机的NP。马西马蒂克国王，139(4):335–340，2003
[ST11]ScottSchneider和SimonThomas。可数的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
无限时间图灵机卓有成效地扩展了普通图灵机的运算到超限有序时间，并通过这样做提供了关于的可计算性的鲁棒理论reals。集合论、描述性集合论和在可计算性理论中，该方法在实数上提供了无限的可计算性和可判定性概念，这些概念以非平凡的方式攀升到描述性集合论层次（∆1.2.)同时保持强计算性质。无限的时间图灵机，我们有无数经典概念的无限类似物，包括无限时间图灵度，无限时间复杂性理论，无限时间可计算模型理论，现在也是Borel等价理论的无限时间模拟Borel可约性下的关系。
在这篇文章中，我们将简要回顾机器及其基本理论，以及然后更详细地解释我们最近将无限时间可计算性应用于Borel等价关系理论的相似性，在[CH11]中给出了对其的完整描述。
这个应用程序的基本思想是通常取代Borel可约性的概念在该理论中使用了具有无限时间可计算可约性形式，并研究了伴随的等价关系层次。这种方法保留了大部分Borel分析和结果，同时也阐明了似乎超出Borel理论范围的等价关系层次的一部分，包括许多高度规范的等价关系无限时间可计算但不是Borel的等价关系，例如可数结构的不同类的同构关系。
本文的主要部分改编自调查[Ham07]和[Ham05]以及来自我们关于无限时间可计算等价关系的文章[CH11]。无限的时间Hamkins和Kidder于1989年首次研究了图灵机，Hamkins和Lewis提供了核心介绍[HL00]。这一理论现在已经得到了扩展许多其他人，包括PhilipWelch、PeterKoepke、BenediktL¨owe、DanielSeabold，拉尔夫·辛德勒、维奈·德奥拉利卡、拉塞尔·米勒、史蒂夫·华纳、贾科莫·伦齐、埃里希·蒙特里昂、塞缪尔·科斯基等人。该理论的许多前身包括BlumShub-Smale机器（20世纪80年代）、Büuchi机器（60年代）及其伴随的发展，BarryBurd的极限“模糊”图灵机模型（1970年代），α-递归和E递归理论的广泛发展，高等递归理论的一部分（自20世纪70年代）、JackCopeland的加速图灵机（20世纪90年代）、RyanBissellSiders的序数机（90年代），以及最近的PeterKoepke的序数图灵机和序数寄存器机（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州。关于无限时间图灵机的新之处在于，它们的运算被扩展到超限有序时间。为了方便起见，这些机器采用三磁带模型，具有用于输入、暂存和输出的独立磁带。机器
input：00111100...
scrαtch：11010010...
output：00101011...
根据到程序指令。计算被简单地扩展到限制有序阶段定义机器的极限配置。其想法是尽可能多地保留计算到那个阶段为止一直在创建的信息，将其保留在极限配置中，作为早期配置的一种极限。明确地在任何极限有序阶段ξ，机器进入我们所说的极限状态，其中一个区分状态以及开始状态和停止状态；磁头被重置为第一个单元在左边；并且磁带的每个单元都用先前值的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的hn，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产生一个停止的计算，然后有另一个计算写出该计算的证书，整个计算历史的真实编码，包括有序关系，其顺序类型是计算的长度。这很重要事实远非显而易见，它依赖于对最终可写性的微妙处理，并构成这是该理论许多进一步发展的基础，包括我们的应用在本文中提及。
上述计数论证的反映方面包括观察到可能遇到的实数的任何可判定性质在计算过程中，必须持有一个可写的实数，因为我们可以开始计算搜索以找到这样的见证并在找到时输出它。这个想法极大地推广了PhilipWelch的λ-ζ-∑定理。具体而言，[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的概念及其伴随式无限时度关系Alect∞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]分析了一个磁带与多带无限时间图灵机和BenediktL¨owe[L¨01]观察了无限时间图灵机与真理修正理论之间的联系。
2.一些应用和扩展
让我们简要介绍一下最近的发展和无限时间的延伸图灵机，如无限时间复杂性理论的兴起和介绍无限时间可计算模型理论。在此之后，在以下部分中，我们将更详细地介绍无限时间图灵机在类似于Borel等价关系理论。
RalfSchindler[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++和PfBenediktL¨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，lecti的原子图，同时断言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具有可计算的商表示，但没有可计算的表示。
让我们也简要讨论一些有序计算的替代模型这是无限时间图灵机所产生的。PeterKoepke[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)xEx′⇐⇒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等价关系。此外，根据KechrisHarrington-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的枚举。最终类似地定义了可枚举等价关系。这是一个有价值的概括；例如，由xelechypy定义的关系，当x和y在一中是超对数的另一个是可枚举的，但不是Borel。
既然我们已经说过，E∞的最大性取决于可数Borel等价关系，并且由于我们已经定义了可数和最终，以类似的方式，E∞在Borel上下文中的最大性的证明在我们的上下文中产生了相同的可枚举等价关系。
定理12.E∞在可枚举关系中≤c-最大，在最终可列举的关系。
也许令人惊讶的是，我们也可以建立=的极小性。
定理13.=可通过连续的作用这一结果是一个直接的结果（最初是由于韦尔奇）存在一个完美的lecte∞-类集。（这里，lecte∞表示最终的度关系，它是定义类似于lect∞。）韦尔奇证明的思想是使用强迫理论L∑得到一个互一般Cohen实数的完美集，然后论证这个集做这项工作。为了看到定理13的成立，观察每个最终可枚举的关系E（作为一组对）包含在关系lectE∞中。因此存在一个完美的E类的集合，因此存在从=到E的连续约简。
最后，我们无法在等式上建立E0的极小性，我们将其作为一个问题。希望类似于证明的方法定理13将给出答案。
问题14。每一个可枚举等价关系E都是真的吗=否则E0可还原为E？
参考文献
[CFK+10]MerlinCarl、TimFischbach、PeterKoepke、RussellMiller、MiriamNasfi和GregorWeckbecker。
无限时间寄存器机的基本理论。拱数学逻辑，49（2）：249–2732010。
[CH11]SamCoskey和JoelDavidHamkins。无限时间可计算等价关系。圣母院
《形式逻辑杂志》，2011年。出现。
[DHS05]VinayDeolalikar、JoelDavidHamkins和RalfDieterSchindler。P≠无穷大的NPåco-NP计时机器。《逻辑与计算杂志》，15（5）：577-5922005年10月。
[FS89]哈维·弗里德曼和李·斯坦利。一类可数结构的Borel可约性理论。
J.符号逻辑，54（3）：894–9141989。
[Ham02]乔尔·大卫·哈姆金斯。无限时间的图灵机器。《心智与机器》，12（4）：521–5392002。（专门讨论超计算的特刊）。
[Ham04]乔尔·大卫·哈姆金斯。超级任务计算。在BorisPiwingerBenediktL¨owe和ThoralfR¨asch，编辑，《计算的经典和新范式及其复杂性层次》，《逻辑趋势》第23卷，第141-158页。Kluwer学术出版社，2004年。2001年9月21日至24日在维也纳举行的“形式科学基础III”会议的论文。
[Ham05]乔尔·大卫·哈姆金斯。具有无限时间图灵机的无限可计算性。在巴里S。
Cooper和BenediktL¨owe，编辑，《新计算范式》，LNCS第3526卷，阿姆斯特丹，2005年6月8日至12日。CiE，SpringerVerlag。
[Ham07]乔尔·大卫·哈姆金斯。无限时间图灵机综述。在J´erõomeDurandLoseandMauriceMargenstern，编辑，《机器、计算和普遍性——2007年第五届MCU国际会议》，《计算机科学讲义》第4664卷，法国奥尔良，2007年。
[Hjo00]GregHjorth。分类和轨道等效关系，《数学调查》第75卷专著。美国数学学会，普罗维登斯，RI，2000年。
[HK96]GregHjorth和AlexanderS.Kechris。Borel等价关系和可数模型的分类。Ann.纯应用。逻辑学，82（3）：221-2721996。
[HL00]乔尔·大卫·哈姆金斯和安迪·刘易斯。无限时间图灵机。J.符号逻辑，65（2）：567–604，2000
[HL02]乔尔·大卫·哈姆金斯和安迪·刘易斯。Post的超级任务问题既有积极的解决方案，也有消极的解决方案。数理逻辑档案，41（6）：507–5232002。
[HLM07]乔尔·大卫·哈姆金斯、大卫·莱涅茨基和拉塞尔·米勒。快速决策的复杂性ORM可判定集。BarryCooper、BenediktL¨owe和AndreaSorbi，《计算》杂志编辑和现实世界中的逻辑-第三届欧洲可计算性会议CiE2007，第4497卷论文集，《计算机科学讲义》，意大利锡耶纳，2007年。
[HM07]乔尔·大卫·哈姆金斯和拉塞尔·米勒。有序寄存器机的Post问题。在巴里Cooper、BenediktL¨owe和AndreaSorbi，《真实世界中的计算与逻辑》的编辑-第三届欧洲可计算性会议CiE2007，论文集第4497卷，讲义计算机科学，意大利锡耶纳，2007年。
[HM09]乔尔·大卫·哈姆金斯和拉塞尔·米勒。有序寄存器机的Post问题：一个显式方法《纯粹与应用逻辑年鉴》，160（3）：302-3092009。
[HMW07]J.D.Hamkins、R.Miller、D.Seabold和S.Warner。无限时间可计算模型理论。在里面S.B.Cooper、BenediktL¨owe和AndreaSorbi，编辑，《新计算范式：变化》《什么是可计算的概念》，第521–557页。施普林格，2007年。
[HS01]乔尔·大卫·哈姆金斯和丹尼尔·西博尔德。只有一个磁带的无限时间图灵机。《数理逻辑季刊》，47（2）：271–2872001。
[HW03]乔尔·大卫·哈姆金斯和菲利普·韦尔奇。Pf≠NPf对于几乎所有的f。《数理逻辑季刊》，49(5):536–540，2003
[KK06]PeterKoepke和MartinKoervien。顺序计算。数学结构计算。Sci。，16(5):867–884，2006
[Koe05]彼得·科普克。序数上的图灵计算。符号逻辑公报，11（3）：377–3972005年9月。
[KS06]PeterKoepke和RyanSiders。在序数上注册计算。提交至：数学逻辑档案馆，2006年。
[KS09]PeterKoepke和BenjaminSeyfferth。序数机和容许递归理论。安。
纯应用程序。逻辑，160（3）：310–3182009。
[L¨01]BenediktL¨owe。修订顺序和计算机n无限长的时间。逻辑计算。，11(1):25–40，2001
[LM04]贾科莫·伦齐和埃里希·蒙特里昂。关于不动点算术和无限时间图灵机。
信息处理信函，91（3）：121-1282004。
[Sch03]拉尔夫·迪特尔·辛德勒。P≠无限时间图灵机的NP。马西马蒂克国王，139(4):335–340，2003
[ST11]ScottSchneider和SimonThomas。可数的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
温馨提示：按 回车[Enter]键 返回书目，按 ←键 返回上一页， 按 →键 进入下一页，加入书签方便您下次继续阅读。