首页 >> 数学 >> 计算机科学 >> 文章

计算无处不在。

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

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

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

计算的极限》系列

难料的世事

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

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

范氏大楼

(普利斯顿大学当年数学系所在的范氏大楼,图片来自http://web.math.princeton.edu/conference/frggeometry2011/)

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

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

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

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

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

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

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

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

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

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

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

一致的扩充

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

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

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

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

你可能会有这样的疑问:如果把 Cons(T) 当作一条公理加进