希尔伯特纲领

第一章　希尔伯特纲领

1900年8月8日，巴黎。第二届国际数学家大会在索邦大学召开，一个梳着络腮胡子、戴着圆框眼镜的德国人站上讲台。他叫大卫·希尔伯特，柯尼斯堡大学教授，刚被哥廷根请去四年，三十八岁，正处在一生中最有干劲的时候。他宣读了一份清单，十来个问题，后来扩充成二十三个。他在开场里说了一句被引用了一百多年的话，大意是：谁人不为揭开数学的未来而心潮澎湃，谁人不为我们所处的创造时代而自豪。这份清单后来成了二十世纪数学的藏宝图，代数、几何、数论、物理，几乎每个领域都被它犁过一遍。但本书关心的是其中两个看似不起眼的问题，第二个问题问的是算术公理的无矛盾性，第十个问题问的是丢番图方程有没有统一的解法判据。就是这两个问题，一个引出了哥德尔，一个引出了丘奇和图灵，合起来把希尔伯特毕生最看重的宏大计划送上了一条谁都没想到的路。

这本书要讲的故事，本质上是一群人如何试图把数学整体装进机器，又如何精确地发现哪些部分永远装不进去。故事的主线人物有三位半：希尔伯特出了题，哥德尔划出了证明的边界，图灵和丘奇给出了计算的边界，还有半个是冯·诺伊曼，他站在每一幕的侧幕，随时准备把理论变成工程。先把镜头对准出题的人。

全书路线在此交底，免得读者在后半程迷路。前两章讲纲领的提出与哥德尔的爆破，中间五章讲计算概念的定型，从λ演算、图灵机、停机问题到可计算函数与递归函数，第八章讲不可解性内部的分层，第九、十章转入复杂度与NP完备，十一、十二、十三章讲三种对经典范式的扩张，随机化、量子化、交互化，第十四章把整个框架押上物理法庭，第十五章收账。这条路线本身有个说法：它顺着历史的骨生长，但每一处关节都按概念的逻辑缝合。读者若只对某一段好奇，各章开头都有承上启下的路标，跳读不至于迷路，只是会错过一些埋了两百页的伏笔，比如本书第九章要讲的对角线法，在第一章就埋下了它的第一颗种子，第十五章的终章审判也要回到本章的未竟公案。写作者的立场也在此声明：本书对纲领抱有历史的同情，对它的失败抱有分析的兴趣，对它的遗产抱有毫不掩饰的敬意。

柯尼斯堡走出的数学家

先说说这座城，因为本书开头和本章结尾都落在它身上，让它提前露脸是值得的。柯尼斯堡坐落在普雷格尔河口，汉萨同盟的商埠，大学创立于1544年，康德一生未曾远离，七桥问题由欧拉1736年顺手解决，开出了拓扑学。这座城的学术气质是商埠式的，务实，开放，不好玄谈。希尔伯特后来全部的工作风格，偏爱构造、偏爱算法式的明确、对哲学玄虚保持体面的距离，都带着这座城的胎记。1944年英国空军的两夜空袭把老城烧成白地，1946年更名加里宁格勒，德意志的学术记忆整城蒸发。本书第一章和最后一章之间的地理悲剧，此处按下不表。

1862年1月23日，希尔伯特生在东普鲁士的柯尼斯堡，就是今天俄罗斯的加里宁格勒。这座波罗的海边的小城在数学史上颇有来历，康德一辈子没离开过它，欧拉就是在它的七桥问题上开创了图论。希尔伯特的父亲是城市法官，家教严格，据说常叮嘱儿子行事得体，别把话说满。老希尔伯特大概没想到，他儿子日后会把话说得极满，而且还都说到点子上。希尔伯特后来常说自己小时候并不算聪颖，理解东西慢，全靠一步一步抠。这话半是谦虚半是实话，他一生的工作方式就是不做天才状，把一个问题反复嚼到只剩骨架。

1880年他进入柯尼斯堡大学，比同岁的天才少年闵可夫斯基晚显露头角。闵可夫斯基十八岁就拿了大奖，希尔伯特则按部就班，1885年在林德曼指导下以不变量理论的论文拿到博士学位。这位林德曼就是那位证明了圆周率超越性的林德曼。1886年起，希尔伯特与闵可夫斯基、年长两岁的赫维茨结成小圈子，每天下午在苹果树下散步谈数学，这段散步持续了八年，希尔伯特后来说自己的数学教养大半是在那条路上得来的。1895年，克莱因把二十八岁的他请到哥廷根。此后三十多年，哥廷根成了世界数学的麦加，闵可夫斯基也于1902年跟来，加上后来的朗道、柯朗、诺特、外尔、伯奈斯，群星密度至今没有哪所大学重现过。

希尔伯特的数学口味极广，不变量、代数数论、几何基础、变分法、积分方程、数学物理，几乎在每个领域都留下了以他命名的概念。但对本书而言，关键作品是1899年的《几何基础》。这本书干了一件此前没人干干净净干成的事：把欧几里得几何从头公理化，公理不再是自明的真理，而是一堆任意的符号约定，二十来条，分五组，然后逐一研究它们的独立性和相容性。相容性怎么证？用模型。把点、线、面解释成实数域上的有序组和线性方程，几何公理就变成了实数算术的真命题。这一招漂亮，却也埋下了本书全部故事的引信：几何的无矛盾性被归约到了算术的无矛盾性。那算术自身的无矛盾性呢？这个问题悬在半空，二十年后成了希尔伯特第二问题复活的原形。1930年希尔伯特退休，哥廷根的黄金年代也差不多到头了，但那是本章结尾的事。

1900年：一份清单

回到巴黎。二十三个问题里，第二个直截了当：算术公理的相容性证明。希尔伯特特意点名说，这题是数理分析里数一数二的难题。第十个问题则换了一副面孔：给定一个整系数多项式方程，能不能用有限步运算判定它有没有整数解。请注意这个问题的措辞，它问的不是某个方程有没有解，而是一类问题有没有统一的、机械的解法。换句话说，它问的是算法的存在性。第十问题等了七十年，1970年被一位二十四岁的苏联数学家马季亚谢维奇用否定答案收割，那条线的伏笔要埋到本书第八章才收。

还有一段花絮值得讲。1900年的清单一向号称二十三问，2000年前后，数学史家蒂勒在希尔伯特的手稿里翻出了被他自己划掉的第二十四个问题：为证明的简洁性找标准，也就是问什么样的证明算更好的证明。一个被作者亲手删掉的问题，一百年后重见天日，居然还成了今天自动定理证明领域的理论源头之一。这桩小事颇能说明希尔伯特式思维的特点，他关心的从来不只是解决某个问题，而是给一类活动找到裁判规则。

巴黎演讲的精神内核是一句信念：每一个表述明确的数学问题都有明确的答案，能解出来或者能证明它等价于某个公认难题，总之不存在永远的谜。希尔伯特说，数学里没有不可知，这杆旗他扛了一辈子。这面旗本来是竖给哲学家看的，因为此前1872年，生理学家出身的杜波依斯-雷蒙在莱比锡做过一场轰动一时的演讲，题为《论自然认识的界限》，造了一个拉丁词ignorabimus，意思是“我们将永远不知道”，宣称科学再发达，也有一批问题注定无解。希尔伯特用一生跟这个词较劲。他不知道的是，三十年后，这个词会以精确的数学形式在他的祖国、他的故乡、他退休的那个星期还魂。

这份清单的后续命运也值得一笔，因为它能校准我们对预言的期待。二十三问里有的当年就被解决，比如第三问题的体积割补，德恩在1900年就给出了否定答案；有的拖了整一个世纪，第八问题里黎曼猜想到今天还悬着；有的在解决路上开出了意外的大产业，第一问题即连续统假设，哥德尔1938年证明它相对协调，科恩1963年发明力迫法证明它独立，一个问题养出了集合论半壁江山。还有的以否定形式收获，本书关心的第二与第十问题都属于这一类。回头看，清单上问题与答案之间的错位，几乎每一条都有戏剧性，而最大的戏剧性是：希尔伯特用来兜底的那条总信念，每个问题必有答案，会被他自己的第二问题引爆的连锁反应修剪掉一半。答案存在，与答案可被机械找到，是两回事，这条裂缝就是本书全部故事的发源地。

巴黎的听众里还有庞加莱，当时世界数学的另一极。他对希尔伯特的公理化路线持保留态度，认为数学的灵魂在直觉不在逻辑。此后三十年，两人各自的方向都有传人，但推动计算概念诞生的那条路，基本是希尔伯特这边的工程。历史选择哪条路，常常要看哪条路上愿意收留更多天才学徒，二十世纪初的德国大学体制恰好把最聪明的一批人送进了基础研究这条胡同，从学理到机缘，缺一样都出不了1936年。

三大流派争锋

要理解希尔伯特纲领，得先看清它是在跟谁打架。十九世纪末，数学基础战场上有三面旗。第一面是逻辑主义，旗主弗雷格。1879年弗雷格出版《概念文字》，发明了量词，把逻辑变成了一种可以机械推演的演算，梦想把整个数学还原为逻辑。他的工程浩大而孤独，《算术基本定律》第一卷1893年出版，第二卷付印前夕，1902年6月16日，他收到罗素一封信。罗素在研究他的书时发现了一个麻烦：按照弗雷格的规则，可以构造出一个由所有不包含自身的集合组成的集合，问它是否包含自身，无论怎么答都矛盾。这就是罗素悖论。弗雷格在第二卷附录里写下了科学史上最沉痛的认输之一，大意是：一位科学家最不愿遇到的，莫过于整座大厦落成时地基塌了。逻辑主义没有死，罗素和怀特海的《数学原理》三卷在1910到1913年间出版，用类型论给集合论打补丁，硬是把算术盖在了逻辑的地基上。代价是出了名的笨重，证明一加一等于二要走到第一卷五百多页的地方，命题编号是星号五十四点四十三，旁边还配了一句干巴巴的旁注：本命题偶尔有用。

第二面旗是直觉主义，旗主布劳威尔。这位荷兰人1907年的博士论文就亮出了立场：数学不是符号游戏，数学是心智的构造，一个命题说某物存在，就必须给出构造它的方法，否则这句话没说完。由此，排中律在无穷集合上不可全信，因为对无穷多个对象，你没法一个个检查完毕再谈“要么有要么没有”。布劳威尔后来真的按这套原则重建了分析学的一部分，考究、别致，也极其难用。在他看来，经典数学大量使用排中律和实无限，等于在没铺好的桥上跑火车。希尔伯特的回应火药味十足，他说禁止数学家用排中律，好比禁止拳师用拳头。两人在1920年代正面开战，私人关系彻底破裂，1928年博洛尼亚国际数学家大会，布劳威尔抵制出席，因为组织方站在希尔伯特一边。这段公案的是非此处不论，值得记住的是它逼出了一个后果：希尔伯特意识到，光骂不行，得拿出证明，证明经典数学是无矛盾的。

第三面旗就是希尔伯特自己的形式主义。准确地说，形式主义不是宣称数学只是符号游戏那么简单，它是一套两层结构：底下是带真实有限内容的初等部分，直白可靠；上面是理想部分，实无限、超限数、纯存在性证明，像几何里的无穷远点、代数里的虚数，是为方便和统一而引入的工具。理想工具凭什么可信？希尔伯特的方案是证明论：把证明本身变成研究对象，用有穷的、组合的方法证明，理想部分的推演永远不会产生一个有限的矛盾。只要这一步成立，整个经典数学就安全了。你看，这实际上是把整座大厦的安保外包给了一台设想中的审查机器。

三派之争有一个常被忽视的技术交集，值得点出来，因为它直接通向本书主角。逻辑主义需要一套无矛盾的逻辑演算，直觉主义需要一个精确的能行性概念，什么叫构造出来，什么叫一步步给出，形式主义需要一个机械的推演概念，什么叫按规则变形。三条路在最深处要的是同一样东西：把机械的、有效的、有穷的过程，从哲学形容词升级为数学名词。二十世纪的头三十年，这个共同需求像地下水一样在三大阵营底下流动，最终在1936年从三口不同的井里同时冒出地面。评价这场争论时，流行的教科书叙事偏爱宣布胜负，说形式主义败给了哥德尔，直觉主义输给了工程。这种记分牌太粗糙。更准确的说法是，三派联合挖出了计算概念这口井，然后各自的水桶都在打水。今天编程语言里的构造主义倾向、证明助手里的直觉主义逻辑、形式验证里的经典逻辑，三家的血脉都在延续。

还有个背景变量必须在此登记，因为它解释了为什么纲领的高潮和谢幕挤在1928到1936这八年里。第一次世界大战抽干了德国大学的青年一代，1920年代重建期，数学基础成了少数几个不怕缺经费的方向，一张纸一支笔就能开工，于是聪明人扎堆。同时期的魏玛文化对科学与精确性有近乎信仰般的热忱，逻辑与元数学恰好长在这个温床上。等到1933年政治地动来临，这个学派的人事被连根拔起，研究重心整体迁移到普林斯顿和剑桥，本书的后半程故事，地理坐标也跟着换了。科学史的剧本常被思想内在逻辑解释掉，但 timezone 和地址有时同样重要。

无限天堂与有限方法

1925年6月，希尔伯特在明斯特做了一场演讲，题为《论无限》，1926年刊于《数学年鉴》，是他基础研究纲领的总纲。演讲里那句最著名的话是：没有人能把我们逐出康托尔为我们创造的乐园。乐园指的是康托尔的集合论，超限数、不同等级的无穷。乐园里出过强盗，罗素悖论就是明目张胆的一桩，于是需要警察。警察就是证明论，巡逻范围是形式化的数学文本，武器是有穷方法。

什么叫有穷方法，值得多说两句，因为它是整个纲领的命门。希尔伯特要求元数学，也就是研究数学的那个数学，只谈论具体的符号、具体的公式、具体的证明这个有限对象，只承认逐个构造而不承认把无穷总体当作完成了的东西。比如“存在一个素数大于任意给定数”，直觉主义者要求给出找一个的办法，形式主义者接受反证法，但两者都承认逐条检查的有限过程。有穷方法就是这种检查精神的理论化，只许数得过来的东西登场。伯奈斯后来给出了更技术性的刻画，但精神就是这么朴素。妙处在于，如果连这么弱、这么保守的方法都能证明经典数学无矛盾，那这个结论就稳如泰山，谁也挑不出循环论证的毛病，因为审查工具比被审查对象弱得多。

这场演讲里希尔伯特还旧事重提，把ignorabimus拎出来痛批，说数学里没有这个字，我们必胜。他当时不会想到，五年之后，“永远不知道”将以一个构造精巧的句子形式，在他的体系内部被证明存在。不过那是下一章的戏码，本章先让冲锋继续。

有限方法这个概念在后世引起的讨论，比它看起来应有的多，值得加一段辨析。有一种批评说，希尔伯特的有限立场从来没能严格定义，什么算具体的、什么算可感知的，这些词本身就有心理主义残余，用它们当元数学的地基，等于用一摊含混去担保一座精确。这个批评有道理，但历史的回应更有意思：后来证明，有限立场的精确对应物恰恰是原始递归推理，第七章的主角。哥德尔1931年论文里那一排原始递归函数，就是希尔伯特设想的有限操作的形式替身，而一旦替身站住，不完备定理就能证明，替身够不着的地方永远够不着。换句话说，希尔伯特凭直觉圈定的那块保守领地，后来被精确圈定为原始递归的领地，然后定理宣告，这块领地证不了自己的清白。直觉先于形式，形式反过来给直觉判刑，这个结构在本书后面还会反复出现，第九章的多项式时间、第十四章的物理可计算性，都是同一出戏的重演。

证明论的冲锋与隐忧

1920年代的哥廷根，是纲领的施工队。希尔伯特本人年过六十，具体工程由年轻人干。阿克曼从1924年起构造算术无矛盾性的证明，冯·诺伊曼1927年也独立给出一个方案，用的主材都是希尔伯特发明的ε算子代入法。冲到1928年，气氛相当乐观，希尔伯特在博洛尼亚大会的演讲里，口气已经像是胜利前夜。他宣布无矛盾性的证明已经有了眉目，只差技术性收尾。数学史上这种时刻很常见，大部队觉得离山顶五百米，实际上离山顶还隔着一整个理论物理学的距离。

裂缝在随后几年逐步显形。阿克曼和冯·诺伊曼的证明，各自用到了超出严格有穷立场的归纳强度，需要在超限序数上做归纳，这恰恰是他们本该证明其安全性的那种理想手段。发现自己家里用了要审查的工具，工程只能回撤。希尔伯特和伯奈斯把这些工作谨慎地整理成两大卷《数学基础》，1934年和1939年先后出版，成了证明论的经典教材，但作为纲领的胜利宣言，它迟到了，而且变了味。冲锋还留下一个副产品，跟本书第七章大有关系：阿克曼1928年在《论实数的希尔伯特构造》里，为了展示递归定义的层级，造出了一个比一切原始递归函数增长都快、然而仍然可以算出来的函数，后人叫它阿克曼函数。这个怪物第一次提醒人们，“可以计算”这个概念的水比想象的深。

这里还该给伯奈斯几句公道。这位希尔伯特最亲密的合作者从1917年起就在哥廷根效力，纲领的大量技术细节出自他手，两卷《数学基础》名义上是合著，实际执笔主要是他。1933年希特勒上台，因为犹太血统，他被剥夺教职，先流亡瑞士，哥廷根随之人去楼空。希尔伯特有一次在宴会上被纳粹教育部长问到，如今哥廷根的数学怎么样，没有犹太人的数学怎么样，据说他答：哥廷堡的数学？已经没有了。宏伟建筑在逻辑上尚未完工，在物理上先塌了一半。

判定问题与机械化之梦

在正式介绍判定问题前，先把1920年代工程进度表拉齐，免得低估这个纲领当时的胜算。到1928年为止，账面成绩相当好看。逻辑演算方面，罗素的类型论证明可用，希尔伯特学派的谓词逻辑被整理成清晰的公理系统，一阶与高阶的区分在1917年到1928年间被逐步澄清，这套澄清工作的总结正是那本教科书。证明论方面，阿克曼和冯诺伊曼的相容性证明眼看收尾，根岑式的相继演算还没登场，但表方法已经成熟。算术方面，斯柯伦等人证明大块数论可以形式化。站在1928年往回看，似乎只差推土机再轰几个月，地基就能验收。这个乐观账目最要命的未清项是：没有人问过，这些形式系统彼此之间、以及它们与真之间，到底是什么关系。完备性、可判定性这类问题此前不是没人想过，而是被默认为正面答案，就像十九世纪物理学家默认以太存在。历史在数学里也爱玩这种把戏，把最深的裂缝用日常语言的乐观糊住。

纲领的第四块基石，也是与本书书名关系最紧的一块，叫判定问题，德文Entscheidungsproblem。1928年，希尔伯特和阿克曼出版了教科书《理论逻辑基础》，末尾明确写下两个悬案。头一个是完备性：一阶逻辑的有效式是否恰好等于可证式。第二个就是判定问题：有没有一个通用程序，对任何一阶公式，都能在有限步内判定它是否普遍有效。这两个问题一个比一个致命。完备性在1929年就被维也纳一个二十五岁的博士生解决，答案是肯定的，此人叫哥德尔，下一章的主角。判定问题则悬而未决，一悬八年，直到1936年才由丘奇和图灵先后宣判死刑，而且死得极其彻底，那种死刑是数学里最硬的一种。

判定问题不是凭空冒出来的，它是西方思想史上一桩古老梦的收官。1651年霍布斯在《利维坦》里说，推理无非是计算。莱布尼茨1679年前后构想普遍文字和推理演算，梦想有一天人们争论问题时只需坐下来，把话摆到纸面上说：我们来算吧。他的机械计算器只做出了四则运算的样机，逻辑的机械化停留在他那漂亮得像教堂穹顶的手稿里。此后两百年，布尔1854年的《思维规律研究》把逻辑代数化，杰文斯1869年造出能做三段论推理的“逻辑钢琴”，弗雷格把逻辑变成了今天程序员的日常工具。到希尔伯特这里，两千年哲学口号终于被压成一个可以证明或反驳的数学命题：这样的通用判定程序存在吗？

这里有一个极微妙、也极易被忽略的关节。希尔伯特问“有没有通用程序”的时候，世界上还不存在“程序”的数学定义。问题先于概念。这就好比问“有没有永动机”之前还没建立能量守恒，问的人其实是在逼后人先发明一套语言，再回答他。要给判定问题一个答案，必须先说清楚什么是算法、什么是机械过程、什么是有效可计算。二十世纪前三十多年，好几个人各自独立地补上了这个定义，丘奇的λ演算、哥德尔的一般递归、图灵的机器、波斯特的规范系统，而且殊途同归。这种不约而同本身就是本章纲领留给后世最深的馈赠之一，它把一个哲学直觉钉成了数学定理，这是第六章的主题。

最后看一眼纲领的全图。第一块，形式化：把数学内容翻译成无意义的符号串和推演规则。第二块，无矛盾性：用有穷方法证明这套符号游戏推不出矛盾。第三块，完备性：证明每个真命题都在游戏里可证。第四块，可判定性：证明有一个机械程序判定任一命题是否可证。四块基石齐了，数学就成了一个原则上可以全自动处理的系统：机器负责推演和判定，人只负责提出问题。希尔伯特1927年在汉堡的演讲里说过一句常被拿出