计算的极限(五):有限的障壁

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/85861

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

计算无处不在。

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

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

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

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬

难料的世事

美国普林斯顿大学,1936年9月底。

离乡别井,总是一种冒险。即使是一衣带水的英国与美国,文化与传统上的微妙差异,不知制造了多少惶惑。而图灵这时来到普林斯顿,可以说是双重冒险。他刚申请了普林斯顿的奖学金,但却受不了漫长的等待:精英荟萃的普林斯顿实在太诱人了。虽然图灵当时已是剑桥国王学院的研究员,每年有一笔比上不足比下有余的薪金,但人在他乡,经济上需要更多余裕。多申请一笔普林斯顿的奖学金,自然也合乎常理。

但图灵没有拿到这笔奖学金。

在现在看来,这是件不可思议的事:即使是可计算性理论的奠基人,在这笔奖学金上竟然都得不到普林斯顿的青睐。但从当时的情况来看,图灵的遭遇又很合情合理。当时他只是一名小研究员,在学术上名气不大,论文也不多。即使关于图灵机的论文是可计算性理论的奠基石,但脱胎于逻辑的这个领域仍需时间洗练。没有人能参透未来,所以普林斯顿只能从现实角度考虑,而这个考虑的结果,就是拒绝图灵的申请。

但即使没有奖学金,普林斯顿对图灵来说,依然有着相当的吸引力。当时普林斯顿大学数学系与高等研究院共用一幢大楼,可谓人才济济。单在数理逻辑,丘奇自不用提,丘奇的学生克林(Kleene)和罗瑟(Rosser)也是一等一的好手,就连前文反复提到的哥德尔,在一年前访问过普林斯顿,而且计划再次访问。当时在普林斯顿的学者常常开这样的玩笑:如果希望瞻仰数学界的某位领头羊,只要呆在普林斯顿就好,他们总会过来的。人才与人才是相互吸引的,图灵选择冒险,自然有他的理由。

可惜人算不如天算。克林与罗瑟刚刚拿到博士学位,在外校取得了一席教职,已经离开了普林斯顿。哥德尔下一次访问要等到1939年。当时普林斯顿在可计算性理论上能拿得出手的,大概就只有丘奇。丘奇的λ演算在日后同样枝繁叶茂,但那将是本系列的另一个故事。

然而,丘奇的研究方式与图灵格格不入,他追求一切概念的严谨与形式化,甚至到达了难以容忍任何模糊描述的地步。从丘奇和图灵各自提出的可计算性的模型,也能看出二人研究风格的差异。丘奇的λ演算从模型本身的描述开始就充满了一种严谨精确、不可更改的气度,如同数学王国中又一块晶莹璀璨的宝石,可望而不可即;而图灵的图灵机则更为灵动直观,似乎在机械工房中就能找到它的身影,每个人都能明白它的原理。

可以想象这两种迥异的研究风格相遇时必然产生的矛盾。当年二人如何合作研究,在今天剩下的文件中只能窥见一鳞半爪,细节已然遗失于历史的尘埃之中。但从图灵的信件可以推测,他们一开始的合作并不顺利。尽管丘奇为人友善,尽管图灵勤勤恳恳,尽管二人都可以说是数理逻辑领域中的佼佼者,但他们首次合作并没有产生什么成果。当然,数学研究就是这样,失败才是正常情况,甚至可以说,数学研究就是在不断的失败上前进的。

幸而,图灵在数学上的兴趣不仅限于数理逻辑。从冯·诺依曼听来的一个有关群论的问题引起了图灵的兴趣,他很快就解决了这个问题,令冯·诺依曼对他大加青眼。也幸亏有了这个群论问题,图灵在普林斯顿的第一年不算颗粒无收。

但图灵最希望做的,还是有关数理逻辑的问题,他希望继续留在普林斯顿,跟随丘奇继续研究,虽然剑桥也有着强烈的吸引力。在再三的劝说后,他又申请了第二年的奖学金。这次,因为有冯·诺依曼的保荐,结果毫无悬念。

值得玩味的是,冯·诺依曼的信中只字未提图灵在数理逻辑方面的成就。但以后见之明看来,图灵在可计算性理论上的工作,远远比他在群论上的工作意义重大而深远。此中对比,意味深长。然而我们不能说奖学金的管理者做错了什么,只能说他们错失了一段佳话。

图灵在普林斯顿的生活踏入第二年。作为博士导师的丘奇,向图灵提出了一个新的题目:探求超越哥德尔不完备性定理的方法。

图灵再次抓住了这个机遇。

一致的扩充

哥德尔的不完备性定理(参见希尔伯特之梦,以及梦的破灭以及计算的极限(零)),其实描述的就是数学本身的界限。在此之前,数学家认为真理必可达到,而希尔伯特的那句“我们必须知道,我们必将知道”,正是这项信念奏出的最强音。但哥德尔打破了这种幻想,他证明了,对于强得足以包含算术而又不自相矛盾的数学系统而言,“真”与“可证明”是两个彻底不同的概念。在这些系统中,存在着无法证明的真理。

哥德尔的不完备性定理有两条。

第一,一个“合适的”包含了算术系统的数学系统不可能同时是一致和完备的,也就是说,如果它没有自相矛盾,那么必定存在这样的命题,它们是真的,但无法证明。

第二,在这样的系统中,我们可以将“系统本身没有自相矛盾”表述为系统中的一个命题,而这个命题正是一个无法被证明的真命题。假设我们有一个包含算术系统,但又没有自相矛盾的数学系统T,我们将表达“T没有自相矛盾”的命题记作Cons(T),那么,哥德尔的第二不完备性定理说的就是Cons(T)在T中无法被证明。

你可能会有这样的疑问:如果把Cons(T)当作一条公理加进T中,那么得到的新系统不就能证明T没有自相矛盾了吗?这是否与哥德尔的定理矛盾?

但如果将Cons(T)作为新的公理,我们研究的公理系统就不再是T,而是另一个系统T_1 = T \cup \{Cons(T)\} 。虽然在新的系统T_1中的确能证明Cons(T),但它只表达了原有系统T没有自相矛盾,而对于新系统T_1,它不能表达这一点。结合了新的公理之后,表达系统本身没有自相矛盾的命题同样会产生变化。这就像一场猫捉老鼠的游戏,我们自以为封死了一切退路,把猎物逼进了墙角,但事实却是按下葫芦浮起瓢,在我们不知道的地方又出现了新的漏洞,狡猾的猎物得以全身而退。

值得一提的是,这种对公理系统的扩充方法有其独特之处:虽然新的系统比原来多了一条公理,阐述了原有体系的一致性,的确使公理系统变得更强大,但在某种意义上,这又是最保守的扩充方法。它仅仅假定了原有系统的一致性,看似没有引入什么新的知识,而得出的新系统的一致性也与原来的系统相同:如果原有系统是一致无矛盾的,阐述这一点的新公理自然不会引发矛盾;而如果原有系统本身就存在矛盾,那么它能证明一切命题,无论是真是假,那么加入新的公理也不会改变这一点。

这可能不是最有趣的扩充方法,但却是最稳妥的。如果随便添加公理,我们得到的更有可能得到的是一个自相矛盾的无用系统。与其矛盾,不如稳健。

但要用这种方法在系统内部证明自身的一致性,实际上并不可行。的确,我们可以多次重复添加公理的过程,得到从T_1T_2开始的一系列理论系统,但它们的一致性是相同的,都依赖于起始的数学系统T,而且这一点是可以证明的。既然在起始的系统中不能证明自身的一致性,那么之后的一系列系统,无论重复多少次,都不可能证明自身的一致性。

那么,如果我们重复无限次,添加无限条公理呢?这样的话,无论使用了多少条公理,总有比它们更大的一条公理将会断言前面公理的一致性,一环扣一环,直至无穷,整个系统岂不是无懈可击?

系统的证明

从某个理论T_0 = T 开始,逐次添加关于新理论一致性的公理Cons(T_i) ,不断得到T_1 = T_0 + Cons(T_0), T_2 = T_1 + Cons(T_1), T_3, \ldots ,一直到最后包含无穷条公理的T_\infty ,其中每一条公理都有更大的公理来断言它的一致性。似乎我们就得到了一个超越哥德尔不完备性定理的数学系统。

但事情当然不会那么顺利。

首先,在包含无穷条公理的数学系统中,如何在系统内部谈论它的一致性,这并非顺理成章。的确,从理论上来说,包含任意的无穷条公理的数学系统是存在的。但如果要在这种系统内思考,很快就会遇到困境。先不说在系统中进行推理,就算是阅读一个证明,也并非显然。要理解这一点,需要对“形式证明”有更具体的理解。

一个数学系统内的形式证明,实际上是一串有限的命题组合,其中的命题要么是系统内的公理,要么是此前命题明白无误的简单逻辑推论,而最后出现的命题就是这个形式证明要得出的结论,也就是要证明的定理。这种一环套一环的组合方式,恰好保证了最后结论的正确性。而我们在阅读一个形式证明时,也只需要顺次检查这些命题,看看每一个命题是否本身就是公理或者此前命题的推论,就能验证这个证明的正确性。

而如果要在系统内部用命题表达系统本身的一致性,就要用到哥德尔在证明他的不完备性定理时用到的技术。简单来说,我们需要“阅读证明”的这个过程能够完全机械化,即使将人脑换成图灵机,也可以完成类似的验证。但如果数学系统本身包含无穷条公理的话,这个机械的阅读过程可能甚至连第一步都无法开始:如果有无穷条公理,那么面对一个命题,又如何知道它是否一个公理呢?

打个比方,数学系统好比是座仓库,里边装的都是公理。现在有人给我们一件东西,比如说一本书,我们的任务则是查看仓库里是否有一模一样的存货。如果仓库里只有有限样东西,一个个清点总能完成任务;但如果仓库容纳了无数物件,即使仓库的确有相应的存货,如果清点的次序不当,也有可能永远也碰不上我们的目标。

同样,要判断某个命题是否给定的数学系统中的公理,如果公理只有有限条,那么一个一个比较,总能在有限时间内判断出来。但对于无穷条公理的情况,这种方法有着严重的缺陷。如果检查的命题的确是公理,那么有朝一日总会停止;但反过来,如果我们检查了很久,仍然没有找到它是公理的证据的话,因为我们没有清点公理的一般方法,所以同样无法断言是否有遗漏。

所以一般而言,在一个包含无穷条公理的数学系统中,我们甚至无法在有限时间内机械地判断一个证明是否正确。尽管形式上仍然可以对形式证明进行定义,但我们几乎无法有效地考察这样的定义。同样,在这类系统中,有关形式证明的概念,尤其是系统本身的一致性,也如同处于矛盾中的说谎者,根本无法被表达。在这些系统中,难以谈及有关证明论的问题。

然而,在数学家们平常使用的数学系统中,不乏包含无穷条公理的例子。其中包括策梅洛-弗兰克公理系统,它被认为是现代数学的公认基础;还有皮亚诺算术的一阶逻辑版本,这个版本在数理逻辑的研究中经常出现。虽然这些系统同样包含无穷条公理,但数学家们在使用这些系统进行证明时没有一丝的踌躇,似乎其中形式证明的意义理所当然,与我们之前的结论背道而驰,这又是为什么呢?

答案很简单:这些数学系统拥有特殊的性质,虽然包括无穷条公理,却能在有限的时间内判断某个命题是否其中的公理。在数理逻辑中,这些系统被称为可有效生成的公理系统。

“可有效生成的公理系统”,顾名思义,这种系统里的公理都是可以“有效生成”的,也就是说,存在一台图灵机,可以“生成”所有的公理,将它们一一打印到纸带上,而打印出来的命题则必定是系统中的公理。可以说,这样的公理系统可以约化为一台图灵机。

回到仓库的比喻的话,一个可有效生成的数学系统同样是公理的仓库,但其中有着某种规律。比如一个包揽全世界所有书的仓库(它的别名叫图书馆),要判断某样物品是否有存货就太简单了:只要是书,那就有存货;如果不是书,那就没有。无需费力找到具体的对应,但同样可以确定仓库中是否存在相同的存货。

如果一个数学系统是可有效生成的,那么可以构造一个图灵机来判断某个证明是否正确。它能仅仅承认那些系统内正确的证明,对于错误的证明则一律拒绝。那么,即使有无穷条公理,我们仍然能通过这台图灵机考察关于形式证明的性质,从而可以谈论所有有关证明论的问题,包括我们关心的系统一致性。

而我们希望讨论的扩充系统,也就是通过无穷次扩充得到的数学系统,的确是一个可有效生成的系统。所以,我们对它一致性的讨论是有意义的。

对于读者来说,可能会感觉这些围绕着无穷条公理的讨论仅仅是一种吹毛求疵。但对于数学,特别是数理逻辑而言,精确性无比重要。在日常生活中,我们使用的语言太模糊太杂乱,人们的本意常常迷失在语言当中,有时连人本身都不理解口中的言说。但在数理逻辑中,一切含糊都被符号明晰,没有歧义,没有矛盾,对就是对,错就是错。这种确定性,正是数学真理性的所在。

有限的障壁

无限扩充得到的公理系统T_\infty ,虽然能在其中表达系统本身的一致性,但它的一致性却不像我们想象中的那么显然。虽然对于其中的每一条新公理Cons(T_k) ,都有比它更强大的另一条公理Cons(T_{k+1}) 保证它的一致性,但这真的能证明包含无数条新公理的系统是一致无矛盾的吗?

我们重温一下一致性的定义:一个公理系统是一致无矛盾的,当且仅当系统中不存在对于假命题的证明。也就是说,无论系统有多大有多复杂,只要系统本身不能证明任意一个假命题,比如说“1=2”,那么这个系统就是一致的。

我们现在尝试考虑无限扩充得到的公理系统T_\infty 。要超越哥德尔不完备性定理,就需要在系统内部证明有关系统本身一致性的命题Cons(T_\infty) 。假设系统中存在一个这样的形式证明P ,这意味着什么呢?

我们知道,形式证明的长度是有限的,毕竟无论是人类还是计算机,都无法完整阅读无限长的证明。所以,证明P 用到的公理也只有有限条。既然有限,那么其中形如Cons(T_k) 的公理也有限,对应的k 必然有一个最大值,不妨设为N 。那么,证明P 中的所有公理,在更小的系统T_{N+1} 中早已存在,所以证明P T_{N+1} 中同样有效。也就是说,仅仅在T_{N+1} 中就可以证明T_{\infty} 的一致性,它也蕴含了更小的系统T_{N+1} 的一致性。

也就是说,因为形式证明的长度是有限的,如果无限扩充后的系统T_\infty 能超越不完备性定理,证明它自身的一致性,那么在之前有限次扩充中,必然已经存在一个系统,它能证明自身的一致性。根据之前的论述,这也表示一开始的出发点——也就是系统T ——也能证明自身的一致性,而这是不可能的。

尽管我们尝试用无限来突破不完备性定理,但名为“有限”的障壁挡住了我们的去路。

在某种意义上,我们能够处理的,只有“有限”,而无法处理真正的“无限”。那些我们看似能抓住的“无限”,实际上也只是通过某种“有限”的手段确立的。而在“无限”的海洋中,我们无法辨别的,远多于我们能认识到的。

我们无法认识一切,相对地,我们永远有着等待探索的世界。

既然从一致性的方向无法突破,那么从另一个方向呢?哥德尔不完备性定理断言,对于合适的数学系统而言,一致性与完备性是两立的,那么,是否可以不停地扩充系统,在保证一致性的前提下,使它能证明越来越多的命题呢?最后又是否能得到一个完备的系统,在其中可以证明所有真命题呢?

为了回答这个问题,图灵将眼光投向了无穷的彼岸。

Advertisements

One thought on “计算的极限(五):有限的障壁

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s