------------------------------------------------------————-------------------------------------------------------
作者：方弦
这个系列开始发表于2012年，然而到今年这个专题还在继续 表示支持鼓励
来源

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

【一台通用图灵机，数据具体格式请参见来源：http://rendell-attic.org/gol/utm/utmprog.htm】
通用图灵机的想法，在如今这个计算机泛滥的时代，似乎并不新鲜。但在图灵的1935年，电子计算机甚至仍未问世，机械计算机还只能执行内设的一套指令。即使是Charles Babbage和Ada Lovelace的超越时代的设想，其中执行外部程序的概念也相当含混不清。在这种历史背景下，要归纳出通用图灵机这个概念，本身就需要极为丰富的想象力，而且这种图灵机是否存在，这是个远非显然的问题。而图灵不仅设想到了这个概念，而且正确地判断出它的存在性，这需要何等非凡的直觉！
但单纯的直觉终究不能令人信服，数学家讲究的是逻辑和证明。而要证明通用图灵机的存在，最直接的方法莫过于直接给出一个通用图灵机的实例。这并不简单，如果读者想尝试一下的话，我建议先尝试构造一个能做二进制加法的图灵机。为了降低难度，可以假设纸带上有第三种符号，表示空白，但即使如此，要构造一个能做加法的图灵机，远比想象中的困难。可想而知，通用图灵机的构造肯定更为复杂繁琐。即使是图灵，他在一开始给出的构造也是有问题的，而这些问题甚至在后来的勘误中也没有成功修正。比构造更麻烦的是证明给出的图灵机的确是一台通用图灵机，在图灵解决希尔伯特可判定性问题的论文中，有关通用图灵机的构造和证明占了相当大的篇幅。这部分非常繁复琐碎，而且其中还有错误，如果细细研读的话，绝对有诱发剧烈偏头痛的危险。
幸运的是，无论细节多么复杂，图灵的想法还是被逻辑学家们接受了。一旦领会到图灵机的能力，接受了通用图灵机的构想，再检查几个能完成基本任务的图灵机之后，大部分数学家都会认为通用图灵机的确存在，尽管他们并不一定会细看图灵的详细构造。而现代电子计算机的发展，更是验证了通用图灵机的存在：每一台电脑都相当于一台通用图灵机。
通用图灵机的存在，从侧面说明了图灵机这个计算模型的强大之处：图灵机作为一类机器，其中一个特例就可以模拟整个类别中的任意一台机器，宛如能折射大千世界的一滴水珠。但在这种强大的背后，隐隐也暗藏着不安定的因素。哥德尔不完备性定理告诉我们，有时候越强大的数学理论，因为能表达的概念太多，甚至连理论的命题和证明都能表达，反而会导致不能被证明的真命题的存在。如果一个系统足以描述它自己，那魔法般的自指将是不可避免的。图灵机如此强大，它的其中一台就可以模拟所有图灵机，会不会导致不能用计算来回答的问题存在呢？
很不凑巧，答案是会。

计算的极限（四）：机械计算的圭臬
殊途同归
大洋彼岸寄来的论文，对于图灵来说，并不是什么好消息。在看到丘奇的论文后，图灵有过何等反应，至今恐怕已不可考。面对着一位在数理逻辑方面已然小有名气的职业数学家，与自己一起独立发现了相同的突破性结果。往好处想，这说明图灵自己的水平已经达到了当时数理逻辑研究的前沿；往坏处想，重复了别人的结果，哪怕是独立发现的，似乎都有些不对味儿。
然而，在下定论之前，图灵还有一件事情要搞清楚。他和丘奇对“可计算性”的定义，分别建筑在图灵机与λ演算之上。那么，在不同的基础上定义的两种“可计算性”，是貌合神离还是本为一体？
图灵机与λ演算，两者似乎都在平平无奇中暗藏玄机。作为计算模型，它们有很多相似之处，比如自我指涉的能力。但它们看起来又是如此不同，图灵机是一台在工程上能建造的机器，而λ演算则是一个彻头彻尾的数学模型。看起来，要回答这个问题，并非易事。


图灵知道，丘奇也知道，他们已经踏入了一个新领域。昔日希尔伯特在他的二十三个问题中，一语带过的那个“机械化的运算”，即将被赋予精确的数学含义。但正因如此，踏出的第一步必须慎之又慎，尤其对于“可计算性”这个最基础的定义，必须做到毫不含糊。为此，为了消除模棱两可之处，图灵机与λ演算是否能力相当，这是个必须回答的问题。
知己知彼，百战不殆。为了解答这个问题，图灵开始钻研λ演算，试图弄清到底λ演算能计算什么。终于，他证明了，所有λ演算能计算的函数，他的图灵机也能计算，反之亦然。也就是说，λ演算与图灵机的计算能力是等价的，两种模型定义的“可计算性”实际上殊途同归。他将这个结果作为附录补充到了他的论文。
对于图灵来说，这既是个坏消息，也是个好消息。坏消息是，他的结果与丘奇的重复了，对于发表文章来说，这不是什么好事情。好消息是，他的结果与丘奇的重复了，但他对可计算性的定义与丘奇的截然不同，而且两种看似毫无关系的定义，在实质上是相同的，这说明，他们对可计算性的定义，这最初的一步踏出的方向是正确的。一个人提出的定义很可能忽视某个方面，但现在两个截然不同的定义引向相同的结果，在交叉印证下，几无出错之虞。
可以说，图灵的工作面世之日，正是可计算性理论呱呱坠地之时。
也难怪纽曼教授一开始不相信图灵的工作。仅仅二十出头，刚刚踏入科学界的年轻人，就解决了如此重要的问题，而且为一个全新的领域立下了奠基石，这种人，即使在剑桥这个英国顶尖学府，也可谓难得一见。倒不如说，一开始不相信，这才是正常的反应。
但即便不相信，数学证明就是证明。即使纽曼教授并不专精于数理逻辑，还是能看出图灵论文的过人之处。他决定为图灵争取发表的机会。
这并非易事。因为从结论上说，图灵重复了丘奇的结果，所以最初联系的几个期刊的编辑都婉拒了纽曼的要求：他们只看到了论文的结论，没看到论文的精髓。最后，纽曼找到了当时伦敦皇家学会学报的编辑，经过三催四劝，终于说服编辑发表图灵的文章。
《论可计算数，及其在可判定性问题上的应用》，图灵的这篇文章，后来被认为是伦敦皇家学会学报发表过的最重要的文章之一。

万变之宗
乘着远洋货轮，图灵的论文很快传到了大洋彼岸，在普林斯顿掀起了一阵旋风。
在普林斯顿高等研究院的哥德尔，与丘奇有过不少碰面的机会。他读过丘奇的论文，大概也听过丘奇本人介绍他的λ演算。但哥德尔对λ演算一直颇有微词。实际上，作为一种计算模型，λ演算从未得到他的认可。它与人们日常接触到的“计算”毫无相似之处，更像是符号的堆砌和推演。虽然其中的计算的确可以机械性地完成，但要证明这一点绝非易事。事实上，这是一个远非显然的定理，证明也相当复杂。总而言之，λ演算并不像机械的计算，更像智慧的推理。
实际上，哥德尔自己也有一套“机械计算”的模型，那正是他在证明哥德尔不完备性定理时发展出来的递归函数体系。这套体系将“机械计算”定义为递归函数能计算的内容，而递归函数，顾名思义，就是可以用某些递归方式定义的整数函数。但哥德尔对他自己的模型同样不满意，原因同样是他的模型似乎需要太多的聪明才智，不像一台机器。
但图灵的论文瞬间就令哥德尔为之折服。
任何人，只要看一眼图灵机的定义，都会认同图灵机的计算完全是机械演算，完全可以造出一台可以运作的实际的图灵机。而更重要的是，图灵机抓住了“机械计算”的神韵。
机械计算是什么？是机器可以做出的计算。但机器可以千奇百怪，要用三言两语抓住本质，似乎不太可能。那么，何不反其道而行之？与其想像这些机器共有的特性，不如寻找它们共有的限制。
这正是图灵在论文中的做法。他总结了以下几个机器计算的限制：
第一：一台机器只有有限个可以分辨的状态；一台机器能分辨的表示数据的符号只有有限种。
开关或开或合，电路或通或断，中间的变化是跳跃式的。即使是连续的电信号，由于不可避免的热噪声影响，通过测量能分辨出的状态同样只有有限个。虽然现代的计算机看似有无限可能，但这只是幻觉。CPU和内存中的电路，数量虽然庞大无比，但总归是有限的，它们的通断形成的不同状态亦是如此。同理，虽然符号、信号在细节上可以有无数种变化，但由于精度等问题，即使是人，也无法事无巨细将所有细节一一分辨出来，更何况机器。

第二：机器的每一步操作需要的时间有一个下限，而每次操作最多只能读入与改写外部有限个符号。在某次操作读写某处的符号后，下一步机器读写的符号与之前符号的距离应该是有界的。
由于物理的限制，不存在速度无限的物体。无论任何机器，都不能在有限的时间内作出无限次操作，当然也不可能有无限次读入与改写。同样，读写头移动的速度是有限的，所以两次操作读写符号的距离当然也有限制。
第三：在某步操作中，机器的行动完全取决于它当时的内部状态以及读取到的符号。
机器就是机器，它应该做的，就是按照预先规划的图纸一步一步执行。没有异想天开，没有灵光一现，只有照章办事，只有步步为营。

这几个限制看起来相当合理，甚至显得理所当然。但就从如此平平无奇的限制出发，图灵用缜密的逻辑说明了，一台服从这些限制的机器能计算的问题，必定可以用一台特定的图灵机解决。也就是说，任何一台服从这些限制的机器，无论设计如何精巧，构成如何复杂，它的计算能力都不可能超越图灵机，无一例外。
我们甚至可以说，图灵机的设计本身，正是这些限制的一种体现。图灵很可能一开始就意识到了这些限制，再由此出发，去定义他的图灵机。哥德尔之所以对图灵机击节叹赏，大概也正因蕴含在它定义中的，图灵对“机械计算”的深刻洞察。相比之下，虽然与之等价的λ演算也尚算精致，但对于“机械计算”只得其形未得其神，显然逊色不少。
现在，希尔伯特在他的问题中那模糊的“机械计算”，终于有了一个精确的定义：机械计算，就是图灵机能做的计算。这又被称为图灵-丘奇论题，正是可计算性理论的奠基石。
除了λ演算与递归函数以外，还有许多计算系统与图灵机等价。波斯特对应问题，计数器机，马尔可夫算法，甚至元胞自动机，这些计算模型都与图灵机等价。但以我们的后见之明来看，图灵机仍然是机械计算最自然最有用的模型之一。

也正因这篇论文，图灵得到了到普林斯顿读博深造的机会，在丘奇的指导下，得以继续探索可计算性的无限可能。在大洋彼岸等待图灵的，又是可计算性理论的一篇新章。

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

（普利斯顿大学当年数学系所在的范氏大楼，图片来自http://web.math.princeton.edu/conference/frggeometry2011/）
但图灵没有拿到这笔奖学金。
在现在看来，这是件不可思议的事：即使是可计算性理论的奠基人，在这笔奖学金上竟然都得不到普林斯顿的青睐。但从当时的情况来看，图灵的遭遇又很合情合理。当时他只是一名小研究员，在学术上名气不大，论文也不多。即使关于图灵机的论文是可计算性理论的奠基石，但脱胎于逻辑的这个领域仍需时间洗练。没有人能参透未来，所以普林斯顿只能从现实角度考虑，而这个考虑的结果，就是拒绝图灵的申请。
但即使没有奖学金，普林斯顿对图灵来说，依然有着相当的吸引力。当时普林斯顿大学数学系与高等研究院共用一幢大楼，可谓人才济济。单在数理逻辑，丘奇自不用提，丘奇的学生克林（Kleene）和罗瑟（Rosser）也是一等一的好手，就连前文反复提到的哥德尔，在一年前访问过普林斯顿，而且计划再次访问。当时在普林斯顿的学者常常开这样的玩笑：如果希望瞻仰数学界的某位领头羊，只要呆在普林斯顿就好，他们总会过来的。人才与人才是相互吸引的，图灵选择冒险，自然有他的理由。
可惜人算不如天算。克林与罗瑟刚刚拿到博士学位，在外校取得了一席教职，已经离开了普林斯顿。哥德尔下一次访问要等到1939年。当时普林斯顿在可计算性理论上能拿得出手的，大概就只有丘奇。丘奇的λ演算在日后同样枝繁叶茂，但那将是本系列的另一个故事。
然而，丘奇的研究方式与图灵格格不入，他追求一切概念的严谨与形式化，甚至到达了难以容忍任何模糊描述的地步。从丘奇和图灵各自提出的可计算性的模型，也能看出二人研究风格的差异。丘奇的λ演算从模型本身的描述开始就充满了一种严谨精确、不可更改的气度，如同数学王国中又一块晶莹璀璨的宝石，可望而不可即；而图灵的图灵机则更为灵动直观，似乎在机械工房中就能找到它的身影，每个人都能明白它的原理。
可以想象这两种迥异的研究风格相遇时必然产生的矛盾。当年二人如何合作研究，在今天剩下的文件中只能窥见一鳞半爪，细节已然遗失于历史的尘埃之中。但从图灵的信件可以推测，他们一开始的合作并不顺利。尽管丘奇为人友善，尽管图灵勤勤恳恳，尽管二人都可以说是数理逻辑领域中的佼佼者，但他们首次合作并没有产生什么成果。当然，数学研究就是这样，失败才是正常情况，甚至可以说，数学研究就是在不断的失败上前进的。
幸而，图灵在数学上的兴趣不仅限于数理逻辑。从冯·诺依曼听来的一个有关群论的问题引起了图灵的兴趣，他很快就解决了这个问题，令冯·诺依曼对他大加青眼。也幸亏有了这个群论问题，图灵在普林斯顿的第一年不算颗粒无收。
但图灵最希望做的，还是有关数理逻辑的问题，他希望继续留在普林斯顿，跟随丘奇继续研究，虽然剑桥也有着强烈的吸引力。在再三的劝说后，他又申请了第二年的奖学金。这次，因为有冯·诺依曼的保荐，结果毫无悬念。
值得玩味的是，冯·诺依曼的信中只字未提图灵在数理逻辑方面的成就。但以后见之明看来，图灵在可计算性理论上的工作，远远比他在群论上的工作意义重大而深远。此中对比，意味深长。然而我们不能说奖学金的管理者做错了什么，只能说他们错失了一段佳话。
图灵在普林斯顿的生活踏入第二年。作为博士导师的丘奇，向图灵提出了一个新的题目：探求超越哥德尔不完备性定理的方法。
图灵再次抓住了这个机遇。

一致的扩充
哥德尔的不完备性定理（参见希尔伯特之梦，以及梦的破灭以及计算的极限（零）），其实描述的就是数学本身的界限。在此之前，数学家认为真理必可达到，而希尔伯特的那句“我们必须知道，我们必将知道”，正是这项信念奏出的最强音。但哥德尔打破了这种幻想，他证明了，对于强得足以包含算术而又不自相矛盾的数学系统而言，“真”与“可证明”是两个彻底不同的概念。在这些系统中，存在着无法证明的真理。
哥德尔的不完备性定理有两条。
第一，一个“合适的”包含了算术系统的数学系统不可能同时是一致和完备的，也就是说，如果它没有自相矛盾，那么必定存在这样的命题，它们是真的，但无法证明。
第二，在这样的系统中，我们可以将“系统本身没有自相矛盾”表述为系统中的一个命题，而这个命题正是一个无法被证明的真命题。假设我们有一个包含算术系统，但又没有自相矛盾的数学系统TT，我们将表达“TT没有自相矛盾”的命题记作Cons(T)Cons(T)，那么，哥德尔的第二不完备性定理说的就是Con(T)Con(T)在TT中无法被证明。
你可能会有这样的疑问：如果把Cons(T)Cons(T)当作一条公理加进TT中，那么得到的新系统不就能证明TT没有自相矛盾了吗？这是否与哥德尔的定理矛盾？
但如果将Cons(T)Cons(T)作为新的公理，我们研究的公理系统就不再是TT，而是另一个系统T1=T∪{Cons(T)}T1=T∪{Cons(T)}。虽然在新的系统T1T1中的确能证明Cons(T)Cons(T)，但它只表达了原有系统TT没有自相矛盾，而对于新系统T1T1，它不能表达这一点。结合了新的公理之后，表达系统本身没有自相矛盾的命题同样会产生变化。这就像一场猫捉老鼠的游戏，我们自以为封死了一切退路，把猎物逼进了墙角，但事实却是按下葫芦浮起瓢，在我们不知道的地方又出现了新的漏洞，狡猾的猎物得以全身而退。


值得一提的是，这种对公理系统的扩充方法有其独特之处：虽然新的系统比原来多了一条公理，阐述了原有体系的一致性，的确使公理系统变得更强大，但在某种意义上，这又是最保守的扩充方法。它仅仅假定了原有系统的一致性，看似没有引入什么新的知识，而得出的新系统的一致性也与原来的系统相同：如果原有系统是一致无矛盾的，阐述这一点的新公理自然不会引发矛盾；而如果原有系统本身就存在矛盾，那么它能证明一切命题，无论是真是假，那么加入新的公理也不会改变这一点。
这可能不是最有趣的扩充方法，但却是最稳妥的。如果随便添加公理，我们得到的更有可能得到的是一个自相矛盾的无用系统。与其矛盾，不如稳健。
但要用这种方法在系统内部证明自身的一致性，实际上并不可行。的确，我们可以多次重复添加公理的过程，得到从T_1、T_2开始的一系列理论系统，但它们的一致性是相同的，都依赖于起始的数学系统T，而且这一点是可以证明的。既然在起始的系统中不能证明自身的一致性，那么之后的一系列系统，无论重复多少次，都不可能证明自身的一致性。
那么，如果我们重复无限次，添加无限条公理呢？这样的话，无论使用了多少条公理，总有比它们更大的一条公理将会断言前面公理的一致性，一环扣一环，直至无穷，整个系统岂不是无懈可击？
系统的证明
从某个理论T0=TT0=T开始，逐次添加关于新理论一致性的公理Cons(Ti)Cons(Ti)，不断得到T1=T0+Cons(T0),T2=T1+Cons(T1),T3,…T1=T0+Cons(T0),T2=T1+Cons(T1),T3,…，一直到最后包含无穷条公理的T∞T∞，其中每一条公理都有更大的公理来断言它的一致性。似乎我们就得到了一个超越哥德尔不完备性定理的数学系统。
但事情当然不会那么顺利。
首先，在包含无穷条公理的数学系统中，如何在系统内部谈论它的一致性，这并非顺理成章。的确，从理论上来说，包含任意的无穷条公理的数学系统是存在的。但如果要在这种系统内思考，很快就会遇到困境。先不说在系统中进行推理，就算是阅读一个证明，也并非显然。要理解这一点，需要对“形式证明”有更具体的理解。
一个数学系统内的形式证明，实际上是一串有限的命题组合，其中的命题要么是系统内的公理，要么是此前命题明白无误的简单逻辑推论，而最后出现的命题就是这个形式证明要得出的结论，也就是要证明的定理。这种一环套一环的组合方式，恰好保证了最后结论的正确性。而我们在阅读一个形式证明时，也只需要顺次检查这些命题，看看每一个命题是否本身就是公理或者此前命题的推论，就能验证这个证明的正确性。
而如果要在系统内部用命题表达系统本身的一致性，就要用到哥德尔在证明他的不完备性定理时用到的技术。简单来说，我们需要“阅读证明”的这个过程能够完全机械化，即使将人脑换成图灵机，也可以完成类似的验证。但如果数学系统本身包含无穷条公理的话，这个机械的阅读过程可能甚至连第一步都无法开始：如果有无穷条公理，那么面对一个命题，又如何知道它是否一个公理呢？
打个比方，数学系统好比是座仓库，里边装的都是公理。现在有人给我们一件东西，比如说一本书，我们的任务则是查看仓库里是否有一模一样的存货。如果仓库里只有有限样东西，一个个清点总能完成任务；但如果仓库容纳了无数物件，即使仓库的确有相应的存货，如果清点的次序不当，也有可能永远也碰不上我们的目标。

同样，要判断某个命题是否给定的数学系统中的公理，如果公理只有有限条，那么一个一个比较，总能在有限时间内判断出来。但对于无穷条公理的情况，这种方法有着严重的缺陷。如果检查的命题的确是公理，那么有朝一日总会停止；但反过来，如果我们检查了很久，仍然没有找到它是公理的证据的话，因为我们没有清点公理的一般方法，所以同样无法断言是否有遗漏。
所以一般而言，在一个包含无穷条公理的数学系统中，我们甚至无法在有限时间内机械地判断一个证明是否正确。尽管形式上仍然可以对形式证明进行定义，但我们几乎无法有效地考察这样的定义。同样，在这类系统中，有关形式证明的概念，尤其是系统本身的一致性，也如同处于矛盾中的说谎者，根本无法被表达。在这些系统中，难以谈及有关证明论的问题。
然而，在数学家们平常使用的数学系统中，不乏包含无穷条公理的例子。其中包括策梅洛-弗兰克公理系统，它被认为是现代数学的公认基础；还有皮亚诺算术的一阶逻辑版本，这个版本在数理逻辑的研究中经常出现。虽然这些系统同样包含无穷条公理，但数学家们在使用这些系统进行证明时没有一丝的踌躇，似乎其中形式证明的意义理所当然，与我们之前的结论背道而驰，这又是为什么呢？
答案很简单：这些数学系统拥有特殊的性质，虽然包括无穷条公理，却能在有限的时间内判断某个命题是否其中的公理。在数理逻辑中，这些系统被称为可有效生成的公理系统。
“可有效生成的公理系统”，顾名思义，这种系统里的公理都是可以“有效生成”的，也就是说，存在一台图灵机，可以“生成”所有的公理，将它们一一打印到纸带上，而打印出来的命题则必定是系统中的公理。可以说，这样的公理系统可以约化为一台图灵机。
回到仓库的比喻的话，一个可有效生成的数学系统同样是公理的仓库，但其中有着某种规律。比如一个包揽全世界所有书的仓库（它的别名叫图书馆），要判断某样物品是否有存货就太简单了：只要是书，那就有存货；如果不是书，那就没有。无需费力找到具体的对应，但同样可以确定仓库中是否存在相同的存货。

如果一个数学系统是可有效生成的，那么可以构造一个图灵机来判断某个证明是否正确。它能仅仅承认那些系统内正确的证明，对于错误的证明则一律拒绝。那么，即使有无穷条公理，我们仍然能通过这台图灵机考察关于形式证明的性质，从而可以谈论所有有关证明论的问题，包括我们关心的系统一致性。
而我们希望讨论的扩充系统，也就是通过无穷次扩充得到的数学系统，的确是一个可有效生成的系统。所以，我们对它一致性的讨论是有意义的。
对于读者来说，可能会感觉这些围绕着无穷条公理的讨论仅仅是一种吹毛求疵。但对于数学，特别是数理逻辑而言，精确性无比重要。在日常生活中，我们使用的语言太模糊太杂乱，人们的本意常常迷失在语言当中，有时连人本身都不理解口中的言说。但在数理逻辑中，一切含糊都被符号明晰，没有歧义，没有矛盾，对就是对，错就是错。这种确定性，正是数学真理性的所在。

有限的障壁
无限扩充得到的公理系统T∞T∞，虽然能在其中表达系统本身的一致性，但它的一致性却不像我们想象中的那么显然。虽然对于其中的每一条新公理Cons(Tk)Cons(Tk)，都有比它更强大的另一条公理Cons(Tk+1)Cons(Tk+1)保证它的一致性，但这真的能证明包含无数条新公理的系统是一致无矛盾的吗？
我们重温一下一致性的定义：一个公理系统是一致无矛盾的，当且仅当系统中不存在对于假命题的证明。也就是说，无论系统有多大有多复杂，只要系统本身不能证明任意一个假命题，比如说“1=2”，那么这个系统就是一致的。
我们现在尝试考虑无限扩充得到的公理系统T∞T∞。要超越哥德尔不完备性定理，就需要在系统内部证明有关系统本身一致性的命题Cons(T∞)Cons(T∞)。假设系统中存在一个这样的形式证明PP，这意味着什么呢？
我们知道，形式证明的长度是有限的，毕竟无论是人类还是计算机，都无法完整阅读无限长的证明。所以，证明PP用到的公理也只有有限条。既然有限，那么其中形如Cons(Tk)Cons(Tk)的公理也有限，对应的kk必然有一个最大值，不妨设为NN。那么，证明PP中的所有公理，在更小的系统TN+1TN+1中早已存在，所以证明PP在TN+1TN+1中同样有效。也就是说，仅仅在TN+1TN+1中就可以证明T∞T∞的一致性，它也蕴含了更小的系统TN+1TN+1的一致性。
也就是说，因为形式证明的长度是有限的，如果无限扩充后的系统T∞T∞能超越不完备性定理，证明它自身的一致性，那么在之前有限次扩充中，必然已经存在一个系统，它能证明自身的一致性。根据之前的论述，这也表示一开始的出发点——也就是系统TT——也能证明自身的一致性，而这是不可能的。
尽管我们尝试用无限来突破不完备性定理，但名为“有限”的障壁挡住了我们的去路。

（图片来自http://www.personal.psu.edu/afr3/blogs/SIOW/）
在某种意义上，我们能够处理的，只有“有限”，而无法处理真正的“无限”。那些我们看似能抓住的“无限”，实际上也只是通过某种“有限”的手段确立的。而在“无限”的海洋中，我们无法辨别的，远多于我们能认识到的。
我们无法认识一切，相对地，我们永远有着等待探索的世界。
既然从一致性的方向无法突破，那么从另一个方向呢？哥德尔不完备性定理断言，对于合适的数学系统而言，一致性与完备性是两立的，那么，是否可以不停地扩充系统，在保证一致性的前提下，使它能证明越来越多的命题呢？最后又是否能得到一个完备的系统，在其中可以证明所有真命题呢？
为了回答这个问题，图灵将眼光投向了无穷的彼岸。

计算的极限（六）：无穷的彼岸
从点集开始
为了超越哥德尔不完备性定理，为了获得一个既不自相矛盾又能证明其中一切真理的数学系统，图灵需要从皮亚诺公理开始，一次又一次地添加新的公理，得到越来越大的数学系统。但无论添加多少次，在获得的系统中，一致性与完备性仍然不可两立，即使添加无穷条公理，也无法跨越“有限”所设置的障壁。要达到原本的目的，图灵必须尝试添加更多的公理。但既然已经添加了无限条新公理，新的公理还会起作用吗？又要怎么去描述“无穷之后”的新公理？“无穷之后”又是什么？
无独有偶，在大约五十年前的十九世纪80年代，另一位数学家也碰到了类似的问题，而他的工作正好给图灵提供了描述“无穷之后”的语言。
这位数学家叫格奥尔格·康托尔，集合论之父。

年青的康托尔，来自Wikipedia
虽然康托尔最大的贡献是为集合论奠基，但他科研生涯的起点与集合论相去甚远。他师从库默尔和魏尔斯特拉斯，博士论文的题目自然也是与数论相关。让他转向集合论研究的关键人物，是爱德华·海涅（Eduard Heine），一位专攻数学分析的数学家。康托尔博士毕业后不久，就在德国的哈雷大学找到了一份教职，而他的新同事中就有海涅。正是海涅鼓励康托尔研究有关三角级数的问题，他对康托尔提出了这样一个问题：什么样的函数拥有唯一的三角级数表达？
三角级数，顾名思义，是由正弦和余弦这些三角函数组成的级数。无论是正弦还是余弦，它们的图像都如同周期性的波纹，而实际上它们也的确描绘了各种各样的简谐振动。在数学上而言，它们是一些特别简单的周期函数，有着特别美妙的特性。但现实往往是复杂的，在工程中，为了实际应用，我们常常逼切地需要计算与工程中出现的函数有关的各种数量和性质。但这些来源于现实的一般函数，几乎不存在任何规律，同样缺乏任何可资利用的特性。于是，如何借助简单而规则的三角函数，来表达复杂而无序的一般函数，这自然同时吸引了数学家、物理学家与工程师。
三角级数正滥觞于此。在1822年，法国数学家傅里叶在他的著作《热的解析理论》中，为了研究热传导的现象，将热量的分布函数分解为三角函数的级数和，并且提出一个构想：所有函数都能表达为三角级数。
当然，事情并没有那么简单。尽管现实中遇到的函数（连续函数）都拥有这样的表达，但对于更为复杂的函数，这却不一定成立。另外一个问题是，对于任意的一个函数，尽管都可以通过傅里叶变换得到对应的三角级数，但谁也不知道会不会有另外一个三角级数也会给出同样的函数。也就是说，虽然通过傅里叶变换，可以知道必定存在一般函数的三角级数表达，但这种表达是否唯一，却并非显然。
康托尔一开始希望解决的，就是这个问题。
凡事总得一步一步来。在1870年，康托尔证明了某个区间上的连续函数必定有唯一的三角级数表达，后来又证明了，即使函数在区间中的有限个点处不连续，也不影响这种表达的唯一性。最后，他在1872年证明了一个非常广泛而复杂的结论：如果函数在区间上大体是连续的，只有在某个点集P上的点不连续，那么如果P满足某个复杂的性质，那么函数就有唯一的三角级数表达。

线性函数的傅里叶级数展开，来自Wikipedia
而正是这个“复杂的性质”，向康托尔暗示了无穷之外另有洞天。

对于任意的点集P，我们可以构造另一个点集P'，它包含所有可以用P中的点无限逼近的点。用数学的术语来说，点集P中的某一点p在P'中，当且仅当对于任意小的距离e，都存在P中不同于p但与p距离小于e的点。既然e可以要多小有多小，这也就是说可以用P中的其他点无穷逼近我们所考虑的点p。这样构造出来的点集P'，又叫P的导集。导集P'本身也是点集，所以它同样有自己的导集，记作P''。导集的导集也有自己的导集，如此反复，直至无穷。我们可以将P取n次导集操作后的结果记为P(n)。
容易知道，一个点集的导集必定是点集的一个子集。实际上，从不太严谨的观点来看，求导集这一操作可以看作一个将点集中那些“离散”的点，也就是那些与所有其他点“保持某个距离”的孤零零的点（或者叫孤立点），从点集中去掉的操作。在一次又一次求导集的操作中，由于我们不停地去掉孤立点，可能会有新的点因为我们除去了它的所有“邻居”而变为新的孤立点，所以多次求导集并非没有意义。
导集的定义并不直观，它的性质也相当复杂。对于一个只有有限个点的点集来说，它的导集必然是空集；而对于一个区间来说，它的导集就是它本身；由数列0.1, 0.01, 0.001, ...组成的点集，它的导集就是仅仅包含0一个点的集合，它的二次导集就是空集。给定一个正整数n，通过一点点思考，再加上一点点数学分析的知识，很容易构造这样的集合，在求它的逐次导集时，前n次得到的都不是空集，最后第n+1次得到的才是空集。有兴趣的读者可以自己尝试构造一下。


而康托尔的定理中所谓“复杂的性质”，就是上述的性质：如果对于一个点集P，我们对它进行逐次求导集后，在有限次操作后能得到空集，那么即使函数在其上不连续，只要在区间的其它地方都连续，那么它就必然有唯一的三角级数表示。
当然，也有一些集合，无论求多少次的导集，也不会得到空集。但康托尔发现，如果恰当地定义集合的“极限”，那么可以通过有限次求出的导集定义“无限次”的导集，记为P(ω)。之所以用ω，大概是因为这是最后一个希腊字母，代表着终结，正适合“无限”这个概念。
那么，这个挂上“终结”标签的无穷次导集，是否的确是导集这个操作的终结呢？按理说，已经进行了无穷次的导集操作，再操作一次也是无限次，同样无限次的操作，应该只会得到相同的结果。但康托尔发现了一些违背我们期望的集合，即使取了无穷次的导集，得到的结果仍然存在着孤立点，可以通过再次取导集除去。这到底意味着什么？
这一定意味着，我们并没有完全理解无穷。但康托尔的观点甚至更加激进：他认为我们连自然数都没有理解透彻！

数量与顺序

回想我们清点物品，比如说桌子上的书，又或者盒子中的巧克力时，我们到底干了些什么？我们指着一个物体，说一声“一”，又指着另一个物品，说一声“二”，再指着又一个物品，说一声“三”。在这里，“一”、“二”、“三”到底代表什么？最自然的解释是，因为我们正在清点，所以这些数字代表的就是我们清点过的物品的数量。另一种同样自然的解释是，这些数字代表我们清点的次序，“一”就是第一个物品，“二”就是第二个，如此类推。
也就是说，我们平时使用的自然数，实际上有数量与顺序的双重意义。在清点时，我们指着一个物品说“五”，实际上说了两件事情，一是之前一共清点了五件物品，二是现在指着的物品是第五件。对于任何一个自然数，这两重意义总是同时出现，难以分割，所以我们自然难以察觉到，在喃喃自语清点物品时，我们口中说出的每一个数字，实际上都有着双重的含义，而这两种含义实际上是完全不同的。
而康托尔的洞见之一，就是对于无穷而言，这双重的含义不再重合，也不再同时出现在同一个“数字”上。本来数量与顺序就是两种截然不同的东西，两种含义不同才自然。
同样一堆物品，可以有许多不同的清点顺序。比如说光的三原色，可以是红蓝绿，也可以是蓝红绿，还可以是红绿蓝。对于清点顺序的唯一要求，就是对于任意两个物品，清点的时候总是能分出个先后，而且要求有一个物品是“第一次被清点”的，也就是说是所有物品中最先被清点的。用数学术语说，就是要求物品之间有一个全序关系，并且有一个最小元素。
但从另一个方面来看，一堆物品的数量应该是一个固定的值，一个只依赖于这堆物品本身的值，一个从属于这堆物品的固有属性。即使我们需要通过清点这种方式来得知物品的数量，但这个数量应该独立于清点的方式，无论我们如何清点，这堆物品的数量应该都是相同的。
对于有限个物品来说，如果不考虑物品之间的差异的话，清点的方法只有一种。无论是红蓝绿还是绿红蓝，实际上都是1-2-3这个清点顺序。所以对于有限而言，数量和顺序之间可以一一对应起来，所以我们只需要自然数这一个概念，就能同时描述有限的数量与有限的顺序，每一个自然数也因此具有双重的含义。但对于无限个物品来说，即使是同一堆东西，我们也可以有无穷无尽的清点方法。我们最常接触的有无限个元素的集合，就是所有自然数组成的集合，这个集合就可以有许多种不同的清点方法。

最自然的方法当然是从小数到大：
0, 1, 2, 3, 4, ...
也可以先数偶数，再数奇数：
0, 2, 4, 6, ..., 1, 3, 5, 7, ...
也可以先数质数，再数合数，最后数1：
2, 3, 5, 7, 11, ..., 4, 6, 8, 9, 10, ..., 1
当然也可以先数比5大的所有数，然后再数剩下的：
6, 7, 8, ..., 0, 1, 2, 3, 4, 5
清点的方法无穷无尽，但自然数的个数应该是一个固定的量，独立于这些各不相同的清点方法。康托尔洞察到了这一点，他意识到，对于无穷而言，需要用两个不同的概念，分别描述数量与顺序。为此，他提出了基数与序数两个概念，前者描述集合的数量，后者描述清点的顺序。这两个概念一直沿用至今。给出一个清点的顺序，自然能得到集合中元素的数量，所以一个序数对应着唯一的基数；但对于某个特定的集合，它可以有许多种不同的清点方法，所以一个基数可以对应许许多多不同的序数。对于有限的集合来说，它们的基数对应着唯一的序数，所以可以将二者混为一谈，这正是我们常用的自然数。
在厘清有关无限的观念滞后，关于点集导集的谜题就自然消解了：当我们说“进行了无限次导集操作之后再取导集，也是相当于取了无限次导集时”，实际上我们谈论的是操作的数量；但导集毕竟是一个操作，逐次重复操作的结果有着内在的顺序关系，先有前面的结果，再有后面的结果。导集的结果，实际上对应的是序数，而我们却用基数的观念来思考，当然会导致似是而非的结果。
实际上，许多关于无穷的看似矛盾结论，都可以归根于我们在日常经验中对数量与顺序的混淆。比如说有人会认为偶数比自然数少，是因为自然数除了偶数之外还有奇数，但实际上这种说法隐含了“先数偶数再数奇数”的这一清点顺序，用这种方法偶数会比自然数先清点完，而我们现在知道，对于无限个物品来说，可以有无数种不同的清点方法，清点方法一先一后穷尽，并不必然代表数量一大一小，关于无穷的怪论也就自然消解了。我们在日常生活中接触到的物体都只有有限个，所以将基数和序数混为一谈也没有关系，但对于导集这种可以产生无穷个对象的机制来说，基数与序数，也就是数量与顺序，一定不能混淆。
以此为基础，康托尔意识到了集合的重要性，并以此为基础发展出了朴素集合论，也意识到“无穷”也有无穷个不同的级别，并称之为“超穷”，意即超验（超越日常经验）的无穷。经过第三次数学危机之后，由朴素集合论发展而来的公理集合论已经成为公认的数学基础。对公理集合论的研究，已经成为了数理逻辑的重要研究方向之一。而超穷基数与序数也已经成为数学研究中不可或缺的概念。希尔伯特这位大数学家的评价或许最为恰当：“没有人能将我们驱逐出康托尔创造的这片乐园”。

序数构成的螺旋，图片来自Wikipedia
但康托尔本人的命运却远不如他的理论那么幸运。他提出的基数与序数，一开始并没有得到理解，也因为涉及到无穷，以及无穷种无穷，而被当时执德国数学界牛耳的数学家克罗内克所排挤与敌视。克罗内克的格言是“上帝创造了自然数，其余一切均是人为”。他连超越数也不承认，康托尔提出的“超越经验的无穷”，也就是拥有无穷个阶别的无穷，对于这位“统治”当年德国数学界的数学家来说自然是“大逆不道”，甚至到了多次在公开场合言语攻击康托尔的程度。再加上康托尔的理论本来就难以为当时的数学家所理解，因此康托尔在当时的数学界过得并不特别好，一直郁郁不得志，这种压力可能也是他患上精神分裂症的诱因之一。康托尔那辗转于疗养所的晚年，也许部分而间接地要归根于他那伟大的洞察。
生命是灰色的，而理论之树常青。

无穷的彼岸
但对于五十年后的数学界来说，基数和序数的概念早已被广泛接受，图灵对此自然也非常熟悉。利用序数的概念，来探寻无穷扩充之后的公理体系，亦是水到渠成之事。窥探无穷的彼岸，不再是一件不可思议又充满矛盾的事，而是确确实实令人信服的数学手段。
对一个公理系统进行扩充，可以看成对公理系统的一种操作，正如取导集可以看成对点集的一种操作。对于无限次操作之后得到的结果，再施加一次操作，也是有意义的。对于操作来说，重要的不是数量，而是操作的顺序，而序数正适合标记这种顺序。
利用序数，我们能表达无穷次扩充后得到的公理体系。就算无穷次扩充之后，我们仍能一次又一次地进行扩充，直到无穷；但仍能继续扩充，直到无穷次无穷，无穷次无穷次无穷，无穷次无穷次无穷次无穷，如此等等，不一而足；但这并不是终点，我们甚至还能继续进行体系的扩充，达到连用“无穷次无穷次……无穷”也需要重复无穷遍的地方……这令人头晕目眩，但序数可以轻易表达这一切，而这只是序数涵盖领域的九牛一毛而已。
于是，我们能一刻不停地扩充原有的体系，得到一个又一个的新体系，这个过程永无止尽，每一个新的体系都比原来的更强大，而每个体系都拥有自己的一个序数，标志着它们在这个超穷的扩充过程中出现的顺序。每一个能表达出来的序数，都对应着一个公理系统。而所有这些公理体系，依由它们对应的序数，组成了一整个层次结构。

图灵将这一系列的公理系统称为序数逻辑，这个原创的体系正是他的博士论文的研究内容，而提出新研究体系的博士论文，可是凤毛麟角。
他希望这个工具能在某种意义上超越哥德尔不完备性定理。虽然任何一个（可有效生成的）公理体系都不可能同时是一致而完备的，但对于一系列的一致的公理体系而言，这种限制并不存在。即使其中每个公理体系都有不可证明的命题，但如果对于任意的命题，都能在序列中找出一个能证明或否定它的一致的公理体系，那么，在作为一个整体的意义上，这一系列的公理体系是完备的。当然，这与哥德尔不完备性定理并不矛盾，因为一系列可有效生成的公理体系，它们合并起来并不一定是可有效生成的，既然定理的前提不适用，那么定理的结论自然也不适用。
那么，在这个层次结构中的一个“证明”，应该是怎么样的呢？
因为命题总是要在某个体系中被证明，所以首先要指定一个体系，相当于指定这个体系对应的序数，剩下的就是直接写出这个命题在对应体系中的证明。当我们要检验一个证明时，首先查看指定的序数，然后查看对应的体系中的公理，知道公理之后就能如同一般的证明一样进行检验了。也就是说，跟一般的证明相比，在层次结构中的证明只是多了“指定证明所在体系的序数”这一步，似乎没什么了不得的。
但魔鬼往往潜藏于细节之中，这一步并不像想象中那么容易。

直觉与技巧
序数是超穷的，比无穷还要无穷，但证明的长度是有限的。所以，我们实际上不能任意指定序数，而只能指定那些我们用有限个符号能够表达的序数。所以，实际上我们指定系统用的不是序数，而是序数的一种表达方式。这种表达方式要满足两个条件：表达式的长度是有限的；如果某个序数能够被表达，那么小于它的所有序数也应该能被表达。当然还有一些技术上的条件，但我们暂时按下不表。
满足这两个条件的序数表达方法很多，图灵选择的是其中最复杂的一种：克林-O表达。这种方法用自然数的因子分解来表达序数。虽然这种方法并不能表达所有序数，但在某种意义上，它已经是最强大的表达序数的方法。但与强大能力相随的是这种方法极端的复杂性。实际上，要判断某个自然数是不是一个序数的表达，这是一个高度不可计算的任务，虽然对于特定的自然数，可能可以进行判断，但不存在统一的判断程序。
既然不可计算，那么也无法验证，那么这种证明还有意义吗？
要回答这个问题，我们先回想一下：在做数学证明题的时候，我们到底在做什么？

第一步，一定是审题，弄清楚题目讲的是什么数学内容，是立体几何还是圆锥曲线，又或者是各种函数。不仅是简单的分类，有时一类问题会伪装成另一类问题，比如戴着“圆锥曲线”帽子的数列，或者披着“概率”外衣的组合。搞清楚具体的问题，搞清楚要证明的结论，这才是完整的审题。第二步，才开始正式的证明，在前一步的结果指引下，用对应领域的定理，慢慢探索从条件到结论的路径。而写在答卷上的，就是第二步得出的证明。审题虽然重要，但并不体现在证明中。
数学的可靠性，植根于证明的严谨性。但如何得到一个证明，却难以仅仅依赖严谨的逻辑。比如，命题需要用哪一个数学体系，这就难以用逻辑判断，需要数学家本人的直觉。也就是说，证明某个命题，其实需要两个部分的工作：第一部分来源于直觉，指引着证明的方向；第二部分来源于技巧，将直觉付诸实践。
作为一名数学家，图灵对数学证明中发生的一切当然深有体会。他认为，这种直觉与技巧的关系，与他的序数逻辑当中的证明不谋而合：指定序数的步骤，相当于直觉，告诉我们应该在超穷的层级结构中的哪一个数学体系中寻找证明；具体证明的步骤，相当于技巧，从直觉指定的公理出发，一步一步迈向需要的结论。而序数逻辑甚至将直觉与技巧的关系发挥到了极致：需要用到直觉的，只有开头的一步，但这一步是高度不可计算的，是逻辑不可能完成的任务；而剩下的，则是完全逻辑化的证明，甚至可以用机械完成。也就是说，可以说在序数逻辑的证明中，直觉与技巧的部分完全独立，一览无遗。
图灵认为，这正是他的序数逻辑存在的意义。
但世事往往不如人意。图灵研究的序数逻辑，主要是通过一致性断言扩充而得到的，而这种序数逻辑并没有图灵所期盼的那种完备性。图灵只能证明，他的序数逻辑对于一小类命题（所谓的Π00类）是完备的。这并不尽如人意，但至少第一次跳出了哥德尔不完备性定理的界限。
然而，以后见之明看来，图灵的博士论文中，最大的贡献并不是序数逻辑。在论文第四节中，图灵提出了一个孤立的新概念，这个概念对于论文的其他部分并无深刻贡献，图灵也未曾深入探讨，这使整个第四节看似无关紧要。但在后学看来，这个新概念却是整篇博士论文中最重要的部分，甚至比序数逻辑更重要。可以说，这个概念后来开创了可计算性理论的又一片新天地。
这个概念，叫谕示（oracle）。
（感谢@NEKOinHeaven的漫画插图）