数学论文（无限时间图灵机）-拓崇最新章节-免费小说-全文免费阅读-拓崇作品-话本小说网

注：本章共划分（1/2）！

摘要：我们描述了无限时间图灵机的基本理论和最近的一些发展，包括无限时间度理论，无限时间复杂性理论，以及无限时间可计算模型理论。我们特别关注的是无限时间图灵机上等价关系的层次分析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州。关于无限时间图灵机的新之处在于，它们的运算被扩展到超限有序时间。为了方便起见，这些机器采用三磁带模型，具有用于输入、暂存和输出的独立磁带。机器

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上的结构，计算每个等价类的这种可区分元素并不总是可能的。