必威体育-必威app下载-必威亚洲官网

热门关键词: 必威体育,必威app下载,必威亚洲官网

数理科学

当前位置:必威体育 > 数理科学 > 计算的极限

计算的极限

来源:http://www.jyjkw.net 作者:必威体育 时间:2019-08-29 23:32

在图灵诞辰103周年之际,献给这位伟大的开拓者。

计算无处不在。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

第一位发现这一点的,便是图灵。

《计算的极限》系列

《计算的极限》系列

时代逝去的叹息

波斯特断言,存在一些形式系统,我们无法在有限的时间内知道其中某个命题能不能被证明或否证。可以说,他的断言与10年后哥德尔的不完备性定理非常相似。那么,为什么在数学史中,“不完备性定理”前面的名字不是波斯特,而是哥德尔呢?因为波斯特虽然在1921年得到这个结果,但要等到1943年,在哥德尔、图灵、丘奇的黄金时代过去之后,才得以在极省略的篇幅下发表。

他没有跟上时代的节拍。

当时的美国数学界普遍对数理逻辑没有太大的兴趣,波斯特与他的导师凯泽在当时算是异类。要等到第二次世界大战前夕欧洲数学家大幅迁移到美国,这种状况才开始改变。波斯特曾经将他的想法写成上下两篇论文,并且将上篇提交到《数学年刊》(Annals of Mathematics)。但他得到的回复十分令人失望,同行评议的报告对是否应该发表各执一词,而编辑部也没有给出具体的决定。如果没有上篇的理论奠基,那么下篇就仅仅是空谈。

但无人问津还不是最致命的问题。实际上,波斯特根本没有一个实打实的证明。也就是说,他并没有实际证明他的结论,那只是一种推测再加上关于证明的一些想法而已。虽然以我们的后见之明来看,他的结论与想法都是正确的,但他毕竟没有一个能让别人详细检验的证明。

在数学界,证明就是一切。没有证明,即使看上去再确定无误的结论,哪怕拥有再多的间接证据,哪怕是最优秀的数学家的想法,都只能是猜想,而不是定理。要确立一个定理,就必须有一个滴水不漏的证明。这就是数学界的规则。而很不巧,波斯特的研究风格比图灵更依赖直觉,换种说法就是更不严谨。波斯特的直觉足以预见超越时代的结论,但他却没有对应的能力来将他的直觉在当下整理为严谨而有条理的证明。他的雄心壮志超越了哥德尔,甚至超越了图灵与丘奇,但他当时没有足够的工具,也没有足够的能力来完成这样远大的目标。

但也许波斯特多花些时间整理他的思路,就能写出完整的证明来说服数学界。可惜命运没有给他这样的机会。

就在波斯特取得突破之后不久,也许是由于这个结果的冲击性太大,他的心理失去了平衡。而论文未能成功发表更是为这种失常雪上加霜。他患上的是双相情感障碍,患者会在无端愉悦与无故抑郁中震荡。此后十多年,他一直受双相情感障碍的困扰,在数学上毫无产出,申请到的大学教职也因为发作而不得不放弃。这段时期,他只能当一名中学教师聊以糊口。直到1935年,他才算是回到了学术界。

从1921到1935,波斯特错过了哥德尔,错过了图灵和丘奇。在他迷惘之时,时代巨轮已经呼啸而过,他错过了数理逻辑的黄金年代。在1941年,他写了一篇文章,详细叙述了他此前在逻辑的不完备性方面的工作,投往了《美国数学期刊》。时任编辑赫尔曼·外尔(Hermann Weyl)拒绝了这篇文章:

我毫不怀疑在二十年前你的工作,部分由于它的革命性,没有得到应有的尊重。但我们无法将时针往回拨;在这段时间,哥德尔、丘奇与其他人完成了他们的工作,而美国数学期刊并不是发表历史回顾的地方。

作为编辑,外尔的决定是正确的。探索的前线并不是向迷失者施予救济的地方,历史才是。历史不会忘记这些被忽视的探索者,他们所有的功绩、辛劳与忧伤。波斯特厚厚的研究笔记,就是历史的见证。当时发生的一切将化为铅字,被人们一遍一遍以不同的形式复述,成为集体记忆的一部分。

为传说撰写诗篇,并一直传颂下去,这就是我们能做的一切。

图片 1衡量难度的归约

对波斯特来说,错过时代节拍还不算是最大的打击。

当时人们对精神疾病的认识尚浅,没有确实有效的药物,没有确实有效的疗法,一切只能靠摸索。波斯特的双相情感障碍,同样没有标准疗法。当时的想法是,既然发作时出现的是狂喜和抑郁的极端情绪,那么就应该尽量避免这种极端情绪的发生,最好的方法就是限制会导致极端情绪的活动,对于波斯特来说就是数学。他的医生开出的疗法,就是限制波斯特做数学的时间:从下午四点到下午五点,用餐,然后从晚上七点到晚上九点,每天共计三小时。对热爱数学的数学家来说,这简直是能与精神疾病媲美的折磨,就像让美食家用牙签吃最爱的肉酱意粉,我不知道波斯特是如何忍受这种焦灼感的。

幸而波斯特并没有止步不前。他在症状缓解后很快重新投入到数理逻辑的研究中。在图灵刚发表他论述图灵机的论文后,波斯特在对图灵的研究毫不知情的情况下,发表了另一个与图灵机非常相似的模型,现在被称为波斯特机,它与我们常用的计算机更相似,驱动计算的与其说是状态的转移,不如说是语句的执行。他猜想波斯特机的计算能力与λ演算相同,这是个正确的猜测,但他当时无法证明这一点。图灵的桂冠并未因此旁落。而波斯特在看到图灵的构造与证明后也心服口服,他的探索再次失去了意义。他后来也考虑过图灵机在多维上的扩展,与后来的“元胞自动机”颇有相似之处。著名的“生命游戏”就是元胞自动机的一个例子。可惜他并没有发表这个想法。

之后,波斯特转到了布尔函数的研究,也就是那些变量与值都是“真”或者“假”的函数。在1941年,他发表了一个非常重要的结果:对于函数复合封闭的布尔函数类的分类定理。这些类别构成了一个被称为“格”的数学结构,现在被称为波斯特格。对于当时的研究者来说,波斯特的这个结果虽然很有意义,但研究的对象有些偏门,再加上波斯特典型的那种含混晦涩的行文风格,波斯特格这项成果在当时并没有得到太多的重视。要等到几十年后,人们研究约束满足问题时,波斯特格才重新回到人们的视线中。

图片 2Recursive enumerable sets of positive integers and their decision problems),它希望回答的问题非常简洁:停机问题有多难?有比停机问题容易的不可计算问题吗?

有时候错过时代节拍可能也是一件好事,起码对于波斯特而言,与主流的疏离给他带来了一种与众不同的视角。对他而言,判定问题的计算就是形式系统的推演证明,而形式系统的相互包含是一个非常自然的问题。比如说定义自然数的皮亚诺公理体系,就是一种形式系统,而这个系统中的所有命题都能翻译到集合论的策梅洛-弗兰克公理体系中,能用皮亚诺公理证明的数学命题,在翻译后都能在ZF中证明。可以说,ZF体系包含了皮亚诺公理体系。那么,给定两个不同的公理体系A和B,我们自然希望考察它们的包含关系,比如说B是否包含A。也就是说,我们希望知道,是否存在一种方法,能将A中的命题翻译到B中,并且希望翻译后,在A中能证明的命题在B中仍然能证明。

图片 3归约。从一般的形式系统到正则形式A,再到正则形式B,再到一种非常特殊的推演规则,这些都是归约。在关于形式系统不完备性的研究中,波斯特早已自己构造过许多这样的归约。从特殊的归约到一般的“归约”这个概念,对于数学家来说,仅仅是一步之遥。

为了简洁起见,波斯特并没有使用他的正则形式的概念,而是将计算问题表达为一个个由自然数组成的集合。对于数理逻辑学家来说,无论是形式系统、判定问题还是自然数组成的集合,本质上并没有什么不同。形式系统的命题可以用字符串表达,所以可以化为自然数,判断某个命题是否能从公理推演出来,也就相当于判断对应的自然数是否属于可推演命题对应的集合。而一个集合对应的判定问题,就是某个输入作为自然数是否处于这个集合中,所以,指定一个由自然数组成的集合,与指定一个判定问题是等价的。在这个框架下,归约的定义更方便更直观。

归约也有很多不同的种类,它们有强有弱。波斯特在研究形式系统是用到的归约,也就是上面所说的“公理体系之间的翻译”,是其中能力比较弱的一种,又叫“多一归约”(many-one reduction)。而最强的图灵归约在判断A中命题的正误时,可以在可计算的范围内任意生成B中的命题并得到解答,再从这些任意多的解答中提取结论。能获取的解答数目多了,自然也能解决更多问题,也就是说能力越强。

图灵归约是波斯特研究的最终目标,但它的能力太强,很难研究。所以在1944年的这篇论文中,波斯特主要研究的是更简单的多一归约和另一种稍微更强大的“真值表归约”。他证明了,在这两种归约方法定义的难度概念下,存在这样的计算问题,它们是不可计算的,但却比停机问题更容易。也就是说,如果按照这些归约定义的难度来排序,在可计算问题与停机问题之间,存在无数的“中间层级”。从可计算问题到停机问题迈出的这一步,实际上跨过了无数的层级。

波斯特在论文的结尾猜想,对于更强大的图灵归约,这样的“中间层级”也存在,不仅如此,其中有无数个中间层级是计算可枚举的。这并不显然,因为越强大的归约,越能填补不同问题之间难度的差距。比如说,多一归约认为问题A比问题B要难,但这可能是因为它本身太弱,如果换用图灵归约,也许就能通过多问几个问题得出答案。波斯特关于计算可枚举的“中间层级”是否存在的这个问题,又被称为波斯特问题。

波斯特的这篇论文的新观点和新结果最终引起了美国逻辑学家的注意,他终于获得了作为一个数理逻辑学家应有的赞赏。也许,他并不需要什么救济。

在那场演讲之后,在美国数学协会的聚会上,有个人叫住了波斯特。这个人叫克林,也是一位数理逻辑学家(一些读者可能还记得提出λ演算的丘奇就是他的博士导师)。他对波斯特说,有些东西想让他看看,并将波斯特邀请到了他的家中。

这就是波斯特与克林伟大合作的开端。

图片 4

交错的存在所有

波斯特在演讲中谈到了关于自然数集之间归约的问题,而克林当时也正在研究类似的问题:用不同的逻辑公式定义的自然数集,它们是否不同,又有什么不同?如果在一个关于自然数的逻辑公式P中,只有一个自由变元x,那么,使这个公式成立的所有值组成的集合就是P定义的自然数集。每个自然数集又对应一个判定问题:某个自然数n在这个自然数集中吗?

用这种方法定义的自然数集,它们有着什么样的性质呢?

我们知道,在逻辑公式中,除了我们熟悉的变量和加减乘除,还有一种符号叫“量词”。量词分两种,存在量词∃>∃∃和全称量词∀>∀∀,每个量词都带着一个变元。不要将它们视为洪水猛兽,它们不过是又一些符号而已。存在量词的意思是,只要对应变元的某一个取值能满足命题余下的部分,那么整个命题就为真。比如说,“存在一道菜肴,我可以就着吃三碗饭”,那么只要举出一个例子(当然例子很多,白切鸡、清蒸鱼,不一而足),就能说明这个命题为真。而全称量词的意思恰好相反,它需要对应变元的每个取值都能满足命题余下的部分,那么整个命题才是真的。只要有一个反例,命题就被否定了。比如说,“对于所有的菜肴,我可以就着吃三碗饭”,只要举出一个例子,就能否定整个命题。如果我们否定一个开头是存在量词的命题,得到的命题开头就是全称量词,反之亦然。而克林要研究的,就是这些量词会如何影响命题定义的自然数集。

我们知道,所有一阶逻辑的命题都可以将所有量词整理到命题的开头,对于现在的数学系学生来说,这只不过是一道小小的练习题。所以,我们可以假定所有命题都有着这样的形式。按照开头量词的具体形式,克林将所有有关自然数的命题分成了无穷个类别。没有量词的命题被称为零阶命题,而有量词的命题,它们开头必定由存在量词和全称量词交错组成,这样交错的段数,就是命题的阶数。对于一个n阶命题,如果它的开头是存在量词,我们就称它为n阶存在命题,反之则是n阶全称命题。根据这个定义,我们能轻易看出一个性质:n+1阶存在命题,其实就是n阶全称命题开头加上一些存在量词得到的。而在这个性质中,将“存在”和“全称”两个词反过来,它仍然成立。

(注:在关于自然数的逻辑命题中,还有一种特殊的量词,被称为“有界存在量词”。在n阶命题的定义中,我们忽略这些有界存在量词。)

图片 5∀a∀b∀c∀d∃p∃q.(n+n=p+q)∧(¬(p+2=a∗b)∨(a=1)∨(b=1))>∀a∀b∀c∀d∃p∃q.∧(¬(p+2=a∗b)∨∨∀abcdpq.(n + n = p + q) ∧ (¬(p + 2 = a * b) ∨ (a = 1) ∨ (b = 1))∧(¬(q+2=c∗d)∨(c=1)∨(d=1))>∧(¬(q+2=c∗d)∨∨ ∧ (¬(q + 2 = c * d) ∨ (c = 1) ∨ (d = 1))这个命题是一个2阶全称命题,因为它的量词分两截,而开头是一个全称量词。

克林考虑了所有这些类别的命题能定义的自然数集。他将0阶命题定义的自然数集组成的集合称为Δ0>Δ0Δ0,而将n阶存在命题和n阶全称命题定义的自然数集组成的集合分别称为Σn>ΣnΣ*n*和Πn>ΠnΠ*n*。克林证明了,这些集合组成了一个向上无限绵延的层级,每一层都是自然数集组成的集合,阶数越高,命题能定义的自然数集也越多,表达能力也越强。对于每一层,总有存在这样的集合,它只能被这一层及以上的命题定义,而不能被下方更弱的层定义。也就是说,层级之间的包含关系是严格的。

也许不出大家的意料,克林证明这一切的方法,仍然是康托尔的对角线法。他定义的这个层级,今天被称为算术层级(Arithmetic Hierarchy),是数理逻辑中的一个重要概念。

图片 6Δ0>Δ0Δ0到底是什么。假设集合S是Δ0>Δ0Δ0中的元素,那么存在一个只有单个自由变元的但没有量词的命题P,某个自然数x属于S当且仅当P为真。那么,对于某个特殊的自然数,比如说42,要判断它是否属于S,只需要将42代入命题P中检查即可。既然P没有量词,那么只要硬算,就必然能得到答案。也就是说,我们有一个算法,它一定会停止,而当它停止时,就能得到答案。记忆力好的读者能观察到,这种算法就是所谓的递归函数。

那么,Σ1>Σ1Σ1是什么呢?它涉及的命题拥有∃a.P(x,a)>∃a.P∃a.P(x, a)的形式,其中P是一个Δ0>Δ0Δ0中的命题,如果将a看成一个符号的话。那么,要判断这个命题对于某个特殊的x值是对是错,最直接的方法就是先将x值代入命题中,然后对于存在量词中的变量a,从0开始枚举每一个值,然后将这个值代入P中,命题中就再也没有自由变量,可以直接硬算它是对是错。一旦找到了某个a的值,使得P为真,那么根据存在量词的定义,我们就能判定整个命题为真;但如果命题对于我们的x值来说不为真,那么这样的a值不存在,我们就得一直枚举下去。这是一个不一定会停止的算法,但它仍然是一个算法,而它定义的集合也就是可计算的。

那么,不可计算的问题,比如说停机问题,它又在哪个层级呢?可以证明,停机问题相关的命题可以在更高的Σ2>Σ2Σ2层级中表达出来。既然层级无限绵延,那么我们自然会提出这样的问题:更高的层级中的问题到底是什么?换句话说,既然有些问题的层级比包含停机问题的Σ2>Σ2Σ2更高,那么,这是否说明有些问题比停机问题更难?

波斯特之前的工作聚焦于难度处于可计算问题与停机问题之间的问题,但克林的工作促使他将目光投向另一个方向:难度比停机问题更高的计算问题,在图灵归约之下,它们有着怎样的结构?

无法触及的世界

我们先复习一下图灵归约的概念:考虑一台谕示机M,假设它带有问题A的谕示,如果它能解决某个问题B,那么我们说问题B能被图灵归约到A,记作B≤TA>B≤TAB*T*A。这跟开卷考试很类似,一位学生如果参加关于问题B的开卷考试,却带错了关于问题A的参考书,如果这位学生仍然能借助这本参考书完美地完成考试,那么我们可以说问题B不比问题A难。如果问题B能被图灵归约到A(B≤TA>B≤TAB*T*A),同时A也能被图灵归约到B(A≤TB>A≤TBA*T*B),那么我们说A和B是图灵等价的,记作B=TA>B=TAB=*T*A

图灵等价是一种等价关系:如果A图灵等价于B,而B图灵等价于C,那么A也图灵等价于C。我们可以将那些相互之间图灵等价的问题归为同一类。这些类别,被称为“图灵度”,它们之间可以通过图灵规约来比较难度,可以说,在同一个图灵度中的判定问题,在图灵规约的意义下,难度都是相同的,而带有其中任意一个问题的谕示,给谕示机带来的能力都是相同的,可以互相置换。

那么,这些图灵度到底看起来是什么样子的呢?

显然所有的可计算的判定问题都是图灵等价的,因为“可计算”的定义就是“存在图灵机可以解答”,既然一般的图灵机足以解答,那么任意的谕示机当然也可以。因为这些判定问题对于图灵机来说过于简单,不需要谕示就能完成,所以谕示的内容反而变得不重要,带有一个可计算谕示与没有谕示,对于图灵机来说是一样的。同样,任意的可计算判定问题都能图灵规约到任意的判定问题。可以说,在图灵规约的框架下,可计算判定问题就是那些最“简单”的问题,它们组成了最“容易”的图灵度,被记作0>00。

那么,停机问题又如何呢?图灵证明了任意的图灵机都不能解决停机问题,同样,带有一个可计算谕示的谕示机当然也不能解决,因为这样的谕示机与一般的图灵机的计算能力是相同的。也就是说,停机问题不能规约到任何一个可计算的判定问题,也就是说,停机问题比那些可计算的问题要严格地难,或者说,停机问题与可计算问题不在同一个图灵度。所以,我们至少有两个图灵度,一个是可计算的0>00,另一个是停机问题所在的图灵度,记作0′>0′0

那么,如何构筑更难的问题呢?

图灵在他的博士论文中发现,在停机问题不可计算的证明中,将所有的“图灵机”全部换成“带有‘数论问题’的谕示机”,其他部分不易一字,得到的证明仍然正确。从而他证明了所谓的“数论问题”并不包含所有的计算问题。在这里,图灵选取了“数论问题”这个谕示,但实际上,无论选取什么计算问题的谕示,将它代入原来的证明,得到的证明仍然成立。也就是说,对于任意的判定问题A,带有问题A谕示的谕示机是否会停机,这个判定问题是不能用带有问题A谕示的谕示机解决的。如果问题A是某个图灵度a>aa中的判定问题之一,刚刚的判定问题必定属于某个更高的图灵度,我们将它记作a′>a′a

(注:顺带一提,类似这样可以将“图灵机”换成“谕示机”的证明被称为可相对化的证明(relativizable proof)。这个概念的变体在P与NP问题中占据着重要的地位。更精确地说,在所谓的“多项式归约”的概念下,解决P与NP问题的证明不可能是可相对化的。这个结论又被称为“可相对化障碍”。)

这就是波斯特构筑越来越难的图灵度的方法。对于某个图灵度a>aa,考虑带有其中问题之一的谕示的谕示机,有关的停机问题处于另一个更高的图灵度a′>a′a,这个图灵度被称为原来图灵度的图灵跳跃(Turing jump)。从可计算问题0>00开始,通过图灵跳跃,波斯特能够一步步构建与克林的算术层级相似的图灵度层级,除了最底层的0>00以外,每一个层级都对应着那些不可计算的问题,而且层级越高,问题越难。

实际上,波斯特的图灵度层级与克林的算术层级之间的联系,比我们想象中的更深刻。我们定义0(n)>00(*n*)为从最底层的0>00出发,经过n次图灵跳跃得到的图灵度。波斯特证明了,如果将判定问题与自然数集等同起来,那么可以说0(n)>00(*n*)恰好处于Σn+1>Σn+1Σ*n* + 1和Πn+1>Πn+1Π*n* + 1的交集之中。也就是说,图灵度层级实际上与算术层级紧密地缠结着,图灵度层级中的每一层恰好处于算术层级的两层之间。

但图灵度层级实际上比算术层级延伸得更远。在算术层级的定义中,第n层是由那些拥有n段不同量词的命题构成的,因为命题的长度有限,所以n只能是自然数。在这里,n表达的是数量,也就是基数。但在图灵度层级中,定义的方法则是通过图灵跳跃,是一种顺序关系。在0(n)>00(*n*)这一层中,编号n实际上是一个序数。实际上,与康托尔的导集以及图灵的序数逻辑相似,图灵度层级实际上可以延伸到“无穷之外”,只有用超穷的序数才能表达所有这些层级。

也就是说,尽管人力能及的只有可计算的问题,但通过逻辑推演,我们能认识到,在那些我们无法解答的问题中,竟然还存在着一个精巧的结构。而正是波斯特,向我们首次展示了这个无法触及的世界。

图片 7无限绵延的层级

波斯特很快就将他的部分发现以摘要的形式发表在1948年的《美国数学学会通报》上。克林读到了这篇摘要,自然为波斯特的新发现而兴奋,但他对这份摘要并非毫无意见。

数学家尽管做的都是数学,但他们的处事方式却是各式各样。在提笔写作方面,有的数学家勤于下笔,每获得了新的结果,就会很快写出论文,并通过期刊或者私下流通预印本的形式让同行尽快知道他的结果;有的数学家却惜字如金,即使有了一整套新结果,也记录了相关的定理和证明,但却迟迟不肯下笔,也许是希望更好地打磨这些结果。著名数学家埃尔德什和欧拉是前者的典型代表,两者分别是数学史上发表论文第一和第二多的数学家。而同样著名的高斯和怀尔斯则是后者的典型代表。高斯是个完美主义者,他希望他的著作中毫无瑕疵,“将所有的脚手架去掉”,于是他发现的结果往往在抽屉里一躺就是几年,直到高斯终于满意他的写作,或者别的数学家再次发现这个结果为止。而怀尔斯独自一人在八年时间内钻研,完成费马大定理的证明主体,这早已传为佳话,被认为是怀尔斯坚韧性格的证明。这些不同的风格,也许在不同的环境下有着不同的适应性,但却没有绝对的对与错之分。

波斯特属于惜字如金的那个类别,但与高斯和怀尔斯不同,他喜欢在发表的论文中提及他已经得到的结果,承诺会写出相关的论文,但这个承诺却迟迟不见兑现的踪影。在他发表的这篇摘要里,他除了提到上述超穷的层级结构之外,还提示了更多的结果。也许波斯特是想吊一下别的数学家的胃口,但对于同样在这个领域工作的人,这很不公平。如果你也是研究这个方向的学者,你读了波斯特的这篇文章,可能希望在这些结论上生发出更深入的定理。但因为这些结论的证明并没有正式发表,你并不知道波斯特的这些结论到底是有凭有据,还是仅仅是虚张声势,从而陷入想用但没法用的两难境地。更糟糕的是,如果你发现了相同的结论,希望发表的话,又会出现优先权之争,而这是大家都不希望看到的。无论如何,仅仅提示结果而长久拖延正式论文的发表,对学术整体的发展相当不利。

克林对波斯特这篇摘要的意见也正在于此。他给波斯特写了一封信,除了赞扬他的结果以及一些讨论之外,还提及了不发表的这个问题。克林的信也许使波斯特的良心有些不安,他很快给克林寄去了一份包含他的新结果的手稿。这份手稿延续着波斯特一直以来的风格:依赖直觉,不太严谨,结构也很凌乱。因为这是一份手稿,混乱程度更甚。波斯特自己可能也知道这一点,他给克林的建议是:找个研究生,让他把内容整理出来,然后以合作者的身份一起发表这篇文章。克林依计行事,但这份手稿实在是太难理解,克林找来的研究生实在无能为力,最后克林只好捋起袖子自己动手。

克林是丘奇的学生,也继承了丘奇的那种追求严谨的研究风格。当年丘奇对严谨性的要求曾经让更依赖直觉的图灵吃了不少苦头,这次轮到克林被波斯特的手稿中的各种直觉描述所困扰了。但最终,克林还是将手稿中的内容整理出来,将缺少的证明补齐,并且做了一些延伸的研究,最后写成了一篇论文:

《递归不可解度的上半格》(The upper semi-lattice of degrees of recursive unsolvability)。

所谓的“递归不可解度”,其实就是不可计算的那些图灵度。而“上半格”是一种序结构。波斯特与克林证明了,所有图灵度其实组成了一个非常复杂但有序的结构。我们此前看到,通过图灵跳跃得到的图灵度层级与算术层级关系非常密切,但与算术层级不同的是,在每个图灵度层级之间,还有更加令人惊讶的结构存在,也就是说,阶梯与阶梯之间并不是空无一物,还有更多的结构蕴含其中。这也是显然的,因为自然数的子集有不可数无穷个,但每个图灵度中最多包含可数个子集。所以,图灵度的个数是不可数的,比我们想象中的无穷还要多得多。图灵度层级必然不能概括所有图灵度的结构,那么,必然有更多的结构存在于层级之间。

假设a>aa是一个图灵度,而a′>a′a是它的图灵跳跃,我们来看看这两层阶梯之间到底有些什么。波斯特与克林证明了,a>aa和a′>a′a之间,存在可数无穷个图灵度,它们之间互相不能比较,但都处于两层阶梯之间(用数学术语来说,就是两个图灵度之间至少存在一条可数无穷的反链)。同样在这两层阶梯之间,存在至少一条由图灵度构成的链,其中每个图灵度都可以相互比较,而更有趣的是,对于其中任意两个不同的图灵度,比如说c>cc和d>dd,假设c>cc比d>dd要难,那么这条链之中必定存在另一个图灵度,它的难度处于两者之间,比c>cc要简单,但比d>dd要难。用数学的术语来说,就是这条链是稠密的。也就是说,在图灵度层级之中的每两层之间,不仅存在着无数种方法从一层逐级攀登到另一层,而且在某些路径上,有一部分的路程不是常见的一级一级分立的阶梯,而是连续的无可割裂的斜坡。所有图灵度组成的结构,比我们能想像的还要复杂得多。

图片 8Annals of Mathematics)上。可以说,它开创了图灵度研究这个新领域。到现在,图灵度理论已经成为了数理逻辑中非常活跃的一门分支,而其中主要的研究方法——被称为“优先方法”——同样起源于这篇文章。

这就是作为数学家的波斯特,他的数学研究的顶峰。

图片 9

本文由必威体育发布于数理科学,转载请注明出处:计算的极限

关键词:

上一篇:计算的极限,岩头之斧

下一篇:没有了