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

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的。

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