无限绵延的层级

在图灵诞生103周年之际，我把它献给这位伟大的先驱。

计算无处不在。

进入计算机房，听着服务器排成一排的墙之间风扇的噪音，你似乎可以闻到0和1在*处理器和内存之间的连续流动。从计数和计数到今天的计算机，我们用来计算的工具终于开始有质的飞跃。电脑可以做越来越多的事情，甚至超过它们的制造商。上世纪末，深蓝凭借其前所未有的搜索和判断国际象棋的能力，成为第一台击败国际象棋世界冠军的计算机，但它的胜利仍然依赖于人类大师丰富的国际象棋知识。然而，仅仅过了10年，沃森已经能够用自己的算法“理解”这个问题，然后有针对性地在大量数据库中找到相关答案。从长远来看，这种工具将在更多方面超越它的制造者。所有这些都来自越来越复杂的计算。

计算似乎无所不能，就像一个新的上帝。但即使是这个“上帝”也无法逃脱逻辑设定的界限。

图灵是第一个发现这个的人。

“计算的极限”系列

交错存在所有邮报在他的演讲中谈到了自然数集之间的减少，而克林也在研究一个类似的问题:由不同的逻辑公式定义的自然数集不同吗？它们有什么不同？如果在自然数的逻辑公式P(x)中只有一个*变量x，那么使该公式有效的所有值的集合就是由P(x)定义的自然数集合。每个自然数集对应另一个判断问题:这个自然数集中有一个自然数N吗？

这样定义的自然数集的性质是什么？

我们知道，在逻辑公式中，除了我们熟悉的变量，加法、减法、乘法和除法，还有一个叫做“量词”的符号。有两种类型的量词，量词。>和完整的量词'。>，每个量词都带有一个参数。不要把它们视为*，它们只是象征。量词的存在意味着，只要应变元素的某个值能够满足命题的其余部分，整个命题就是真的。例如，“有一道菜，我可以在桌子上吃三碗米饭”，那么就举一个例子(当然，有很多例子，包括鸡片和清蒸鱼，举几个例子)来说明这个命题的真实性。完整的量词有相反的意思。它需要为应变元素的每个值满足命题的其余部分，那么整个命题就是真的。只要有反例，这个命题就被拒绝。例如，“对于所有的菜，我可以吃三碗米饭”可以通过举一个例子来否定整个命题(例如仰望星空派)。如果我们否认一个以量词开始的命题，结果命题就以一个通用量词开始，反之亦然。富兰克林想研究的是这些量词将如何影响命题定义的自然数集。

我们知道一阶逻辑的所有命题都可以把所有量词放在命题的开头，这对于现在的数学学生来说只是一个小练习。因此，我们可以假设所有命题都有这种形式。根据初始量词的具体形式，克莱因将所有关于自然数的命题分成无限多个类别。没有量词的命题被称为零阶命题。带有量词的命题必须从存在量词和通用量词的交错组合开始。分段的交错数是命题的顺序。对于一个n阶命题，如果它以一个存在量词开始，我们称它为n阶存在命题，否则它就是一个n阶泛命题。根据这个定义，我们可以很容易地看到一个性质:n+1阶存在命题实际上是通过在n阶泛命题的开头加上一些存在量词而得到的。在这种性质下，两个词“存在”和“全名”是颠倒的，它仍然成立。

(注:在关于自然数的逻辑命题中，还有一个特殊的量词叫做“有界存在量词”。在n阶命题的定义中，我们忽略了这些有界的存在量词。)

来自维基媒体

让我们看一个实际的例子。著名的哥德巴赫猜想说，每个大于或等于4的自然数都可以写成两个质数的和。对于特定的偶数2n+4，我们可以把“2n+4可以写成两个素数之和”写成下面的逻辑命题:“a”。“b”。c’。“d”。p’。q(n+n = p+q)。(& # x00AC(p+2 = a’。b)。(a = 1)-。(b=1))>∀a∀b∀c∀d∃p∃q.(n+n=p+q)∧((p+2=a∗b)∨(a=1)∨(b=1))∀a∀b∀c∀d∃p∃q.(n+n=p+q)∧((p+2 = a∫b)∞(a = 1)∞(b = 1))；(& # x00AC(q+2 = c’。d)。(c = 1)-。(d = 1))> ∪( q+2 = CD)∪( c = 1)∪( d = 1))∪( q+2 = CD)∪( c = 1)∪( d = 1))这个命题是一个二阶泛命题，因为它的量词被分成两部分，并且开头是一个泛量词。

富兰克林考虑了所有这些可以定义自然数集的命题。他把命题0定义的自然数集称为集合& # 0394；0 >δ0δ0，由n阶存在命题和n阶泛命题定义的自然数集的集合称为& # x03A3N > σ n σ n和& # x03A0n >πnπn .克莱因证明了这些集合形成了一个无限向上延伸的水平。每一级都是由自然数集合组成的集合。阶数越高，命题能够定义的自然数集越多，表达能力越强。对于每一层，总有这样一个集合，它只能由这一层和上面的命题来定义，而不能由下面较弱的层来定义。换句话说，层次之间的包含关系是严格的。

也许不是每个人都预料到的，克莱恩证明这一切的方法仍然是康托的对角线法。他今天定义的层次叫做算术层次，这是数学逻辑中的一个重要概念。

算术层次

富兰克林的工作极大地启发了波斯特。这是为什么？

让我们先看看& # 0394。什么是0 >δ0δ0？假设集合s是& # x03940 >δ0δ0，则有一个命题P(x)只有一个*变量但没有量词，一个自然数x属于s当且仅当P(x)为真。然后，对于一个特殊的自然数，如42，要判断它是否属于S，只有42需要代入命题P(x)来检验。既然P(x)没有量词，只要很难计算，就一定会得到答案。换句话说，我们有一个绝对会停止的算法，当它停止时，我们可以得到答案。记忆力好的读者可以观察到这种算法就是所谓的递归函数。

然后，& # x03A3什么是1 > σ 1 σ 1？它所涉及的命题有。A.P(x，a) > a.p (x，a) a.p (x，a)，其中P(x，a)为& # x0394如果a被视为符号，则0 >δ0δ0。然后，要判断这个命题对于一个特定的X值是对还是错，最直接的方法是先把这个X值代入这个命题，然后把量词中的变量A从0开始一一列举出来，然后把这个值代入P(x，A)，这样这个命题中就没有*变量了，而且可以直接很难计算它是对还是错。一旦找到A的某个值，使P(x，A)为真，那么根据存在量词的定义，我们就可以判断整个命题为真。但是如果这个命题对我们的x值不成立，那么这样的值就不存在，我们必须继续枚举。这是一个不一定停止的算法，但它仍然是一个算法，它定义的集合是可计算的。

那么，什么是不可计算的问题，如停机？可以证明，与关机问题相关的命题可以在更高的& # x03A32 > σ 2 σ 2水平。由于等级是无止境的，我们自然会问这样一个问题:在更高的等级中有什么问题？换句话说，由于一些问题的等级高于Σ，这包括关机问题；2 > σ 2 σ 2更高，那么这是否意味着有些问题比关断问题更困难？

波斯特以前的工作集中在困难在于可计算问题和关机问题之间的问题上，但是克莱因的工作促使他转向另一个方向:比关机问题更困难的计算问题，以及在图灵简化下它们有什么结构？

在不可触及的世界里，让我们回顾一下图灵归约的概念:考虑一个预言机m，假设它有问题a的预言，如果它能解决某个问题b，那么我们说问题b可以通过图灵归约为a，并记录为B&。TA>B≤TAB≤TA .这与开卷考试非常相似。如果一个学生参加了问题B的开卷考试，但是带错了问题A的参考书，如果这个学生仍然可以用这本参考书完美地完成考试，那么我们可以说问题B并不比问题A难。如果问题B可以通过转到问题A来简化(B&；TA>B≤TAB≤TA)，而a也可以通过图灵化(a’化为B。那么我们说A和B是图灵等价的，记录为B=TA>B=TAB=TA。

图灵等价是一种等价关系:如果一个图灵等价于b，b图灵等价于c，那么一个图灵等价于c。我们可以将这些图灵等价问题归入同一个类(数学术语是等价类)。这些被称为“图灵度”的类别，可以通过图灵惯例进行难度比较。可以说，在相同的图灵度下的判定问题在图灵约定的意义上是相同的，而具有其中任何一个的神谕给甲骨文机器带来了相同的能力，并且可以被彼此替换。

那么，这些旅游是什么样子的呢？

显然，所有可计算决策问题都是图灵等价的，因为“可计算”的定义是“有图灵机可以解决”。因为通用图灵机足以解决问题，所以任何oracle机器当然也可以使用。因为这些判断问题对图灵机来说太简单了，没有甲骨文也能完成，所以甲骨文的内容就变得不重要了，有了可计算的甲骨文和没有甲骨文，对图灵机来说是一样的。同样，任何可计算的决策问题都可以归结为任何决策问题。可以说，在图灵约定的框架下，可计算判断问题是最“简单”的问题，它形成了最“容易”的图灵度，并被记录为0>00。

那么，停机时间呢？图灵证明了任何图灵机都不能解决停机问题。类似地，一台带有可计算甲骨文的甲骨文机器当然不能解决这个问题，因为这种甲骨文机器的计算能力与一般图灵机相同。换句话说，停机问题不能简化为任何可计算的判断问题，也就是说，停机问题比那些可计算的问题更严格地困难，或者停机问题和可计算的问题不在同一图灵度。因此，我们至少有两个图灵度，一个是可计算的0>00，另一个是关机问题所在的图灵度，记录为0。> 0 ' 0 '.

那么，如何构造更难的问题呢？

图灵在他的博士论文中发现，所有的“图灵机”都被“带“数论问题”的甲骨文机器”所取代，证明了关机问题是不可计算的，其他部分也不容易用一个词来形容，而且所获得的证明仍然是正确的。因此，他证明了所谓的“数论问题”并不包括所有的计算问题。在这里，图灵选择了“数论问题”的预言，但事实上，无论选择哪种计算问题，将其代入原始证明，得到的证明仍然有效。也就是说，对于任何判断问题A，带有问题A的甲骨文的甲骨文机器是否会停止，这个判断问题不能由带有问题A的甲骨文的甲骨文机器来解决。如果问题A是在某一图灵度a>aa中的判定问题之一，则公正判定问题必须属于更高的图灵度，并且我们将它记录为‘1’2；> a ' a '.

(注:顺便提一下，“图灵机”可以被“甲骨文机”取代的证明称为相对性证明。这个概念的变体在P和n P问题中起着重要的作用。更确切地说，在所谓的“多项式约简”概念下，解P和NP问题的证明不能是相对的。这个结论也被称为“相对论障碍”。)

这就是波斯特如何构建日益艰难的旅行。对于图灵度a>aa，考虑一个有一个问题的oracle，关闭问题是另一个更高的图灵度a。这个图灵跳跃被称为原始图灵跳跃。从可计算问题0>00开始，通过图灵跳转，post可以一步一步地构建类似于klin的算术等级的图灵等级。除了最低的0>00，每个级别对应于那些不可计算的问题，级别越高，问题就越难。

事实上，波士顿的图灵层次和富兰克林的算术层次之间的联系比我们想象的更深。我们将0(n)>0(n)0(n)定义为从最低层的0>00开始通过n次图灵跳跃获得的图灵度。波斯特证明，如果判断问题等于自然数集，那么0(n)>0(n)0(n) 0 (n)恰好是& # x03A3N+1 > σ n+1 σ n+1和& # x03A0在n+1 > π n+1 π n+1的交点。也就是说，图灵水平实际上与算术水平紧密地交织在一起，并且图灵水平中的每个水平正好在算术水平的两个水平之间。

但是图灵水平实际上比算术水平延伸得更远。在算术层次的定义中，第n层由含有n个不同量词的命题组成。因为命题的长度是有限的，所以n只能是自然数。这里，n表示数量，它是基数。然而，在图灵层次结构中，定义方法是跳过图灵，这是一种顺序关系。在0(n)>0(n)0(n)的层中，数字n实际上是一个序数。事实上，类似于康托的导出集和图灵的序数逻辑，图灵的层次结构实际上可以延伸到无穷远处。只有极差的序数才能表达所有这些层次。

换句话说，尽管只有人力资源能够解决的可计算问题，但通过逻辑推理，我们可以认识到，这些问题中仍有一个我们无法解决的微妙结构。是波斯特第一次向我们展示了这个不可触摸的世界。

《无限级连续性邮报》很快在1948年美国数学学会公报上发表了他的一些发现作为摘要。当科林阅读这篇摘要时，他自然对波斯特的新发现感到兴奋，但他并不反对这篇摘要。

数学家做数学，但他们做事情的方式多种多样。在写作方面，一些数学家勤奋写作，一有新的成果就会写论文，并通过期刊或私下传阅的预印本让同事们尽快知道他的成果。一些数学家珍惜像金子一样的单词。即使他们有一组新的结果，他们也记录了相关的定理和证明，但是他们不愿意把它们写下来，也许希望能更好地完善这些结果。著名数学家鄂尔多斯和欧拉是前者的典型代表。他们是第一个和第二个分别发表数学史论文的数学家。同样著名的高斯和怀尔斯是后者的典型代表。高斯是一个完美主义者，他希望他的作品是完美的，“移除所有的脚手架”，所以他发现的结果经常被搁置多年，直到高斯最终对他的作品满意或者其他数学家再次发现结果。然而，怀尔斯在八年的时间里独自完成了费马大定理的主要证明，这一直是个好故事，被认为是怀尔斯坚强性格的证明。这些不同的风格在不同的环境中可能有不同的适应性，但是对与错之间没有绝对的区别。

帖子属于珍惜文字的范畴，但与高斯和怀尔斯不同，他喜欢在发表的论文中提及自己已经取得的成果，并承诺撰写相关论文，但这一承诺并未兑现。在他发表的这篇摘要中，他提到了上述极度贫困的等级结构，并提出了更多的结果。也许波斯特想吸引其他数学家，但这对那些也在这个领域工作的人不公平。如果你也是一个研究这个方向的学者，在阅读了波斯特的文章之后，你可能希望在这些结论上发展更深入的定理。然而，由于这些结论的证据还没有正式公布，你不知道波斯特的结论是基于证据还是仅仅是虚张声势，因此陷入了使用它们而不使用它们的两难境地。更糟糕的是，如果你发现了相同的结论并希望发表它，将会有一个优先权争议，这是每个人都不想看到的。无论如何，仅仅是提示结果和长时间推迟正式论文的发表对学术研究的整体发展是非常有害的。

富兰克林对邮报摘要的评论也在这里。他给邮报写了一封信，除了赞扬他的成果和一些讨论，他还提到了不发表的问题。富兰克林的信可能扰乱了波斯特的良心。他很快给富兰克林送去了一份手稿，里面有他的新发现。手稿延续了波斯特长期以来依赖直觉的风格，不严谨，结构混乱。因为这是一份手稿，混乱更糟。波斯特自己可能知道这一点，他对克莱因的建议是:找一个研究生，让他整理一下内容，然后作为合作者一起发表文章。克莱因按照计划行事，但手稿太难理解。他发现的研究生都无能为力。最后克莱因不得不卷起袖子自己动手。

克莱恩是丘奇的学生，也继承了丘奇严谨的研究风格。丘奇对严谨的要求给更多依赖直觉的图灵带来了很多痛苦。这一次轮到克林被《邮报》手稿中各种直观的描述所困扰。但最终，克林整理了手稿的内容，填补了缺失的证据，并做了一些扩展研究。最后，他写了一篇论文:

递归不可解性的上半格。

所谓的“递归不溶性”实际上是那些无法计算的符号。“上半晶格”是一种有序结构。波斯特和克莱因证明了所有的图灵度实际上都形成了一个非常复杂但有序的结构。我们以前已经看到，通过图灵跳跃获得的图灵水平与算术水平有非常密切的关系，但是不同于算术水平，在每个图灵水平之间有更多令人惊讶的结构，也就是说，在*和*之间没有任何东西，并且有更多的结构包含在其中。这也是显而易见的，因为自然数有无数的子集，但是每个图灵度最多包含几个子集。因此，图灵度数是不可数的，比我们想象的无限多了。图灵层次结构不一定能概括所有的图灵结构，所以层次结构之间必须有更多的结构。

假设a>aa是一个图灵度，a是一个。a是它的图灵跳跃。让我们来看看这两个步骤之间的区别。波斯特和克林证明了这一点。在> a'a之间，有可数的无限图灵度，它们不能相互比较，但是在两个步骤之间(在数学术语中，在两个图灵度之间至少有一个可数的无限逆链)。此外，在这两个步骤之间，至少有一个由图灵度组成的链。每个图灵度可以相互比较。更有趣的是，对于任何两个不同的图灵度，例如c>cc和d>dd，假设c>cc比d>dd更硬，那么在这个链中一定有另一个图灵度。它的难度介于两者之间，比c>cc简单，但比d>dd难。用数学术语来说，这条链是密集的。也就是说，在图灵层次结构中的每两个层次之间，不仅有无数种方法可以从一个层次爬到另一个层次，而且旅程的一部分不是普通的一步一步，而是一个连续不断的斜坡。所有图灵度的结构比我们想象的要复杂得多。

这篇论文最终发表在著名的《数学年鉴》上。可以说，它开辟了图灵研究的新领域。迄今为止，图灵理论已经成为数理逻辑中一个非常活跃的分支，而主要的研究方法——所谓的“优先方法”——也起源于本文。

这就是波斯特，一位数学家，他的数学研究的顶峰。