计算似乎无所不能，宛如新的上帝。但即使是这位“上帝”，也逃不脱逻辑设定的界限。第一位发现这一点的，便是图灵。
1900年的巴黎，在世纪交替之际，希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的“希尔伯特计划”的最后一步。这位数学界的巨人，打算让整个数学体系矗立在一个坚实的地基上，一劳永逸地解决所有关于对数学可靠性的种种疑问。一切都为了回答三个问题：
希尔伯特明确提出这三个问题时，已是28年后的1928年。在这28年间，数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久，仅仅三年后，哥德尔就得到了前两个问题的答案，尽管这个答案不是希尔伯特所希望看到的。
哥德尔的答案分两部分。
这就是著名的哥德尔不完备性定理，与其说它回答了希尔伯特的前两个问题，不如说它阐述了为什么我们根本不可能解决这两个问题。
哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化，然后给每个符号串赋予一个数字，这个过程被称为哥德尔配数法。借助数学归纳法，我们可以建立针对所有自然数的陈述，而这样的陈述本身对应着一个数字，这个数字也符合陈述本身的要求。换言之，这个陈述陈述了它本身的性质。哥德尔正是通过这样魔法般的自指，完成了他的证明。这个证明之所以重要，是因为它第一次提供了一套完整的数学工具和方法，用于证明有关数学证明的不可能性。这本身就是数学的一次重大胜利，说明数学的力量强大得可以用纯粹逻辑的方法，证明它本身的力量是有界限的。在数学的领地上，有些东西我们不知道，也不可能知道。
希尔伯特的前两个问题已经解决，只剩下最后一个问题。然而，如果一个数学系统不完备的话，它显然不可能是可判定的，因为机械化的计算本身也可以看成一种证明，而在一个不完备的系统中，真理不总能被证明。所以，最后一个问题只对完备的数学系统有意义。
所幸，完备的数学系统是存在的。同样是哥德尔，他证明了所谓“一阶谓词演算”的逻辑系统是完备的，这被称为哥德尔完备性定理。一阶谓词演算是一个比较弱的逻辑系统，在其中我们甚至不能有效唯一地描述算术。比如说，自然数系统符合皮亚诺公理的一阶版本，但它并不是唯一的，还有无数种所谓“非标准模型”同样符合这套一阶系统。在一阶谓词演算中，对于一套公理系统，如果一个命题在所有的模型中都正确，那么必定可以形式地证明这个命题，这就是一阶谓词演算的完备性。在一阶谓词演算中，真理总能被证明。
在这个弱得多的逻辑系统中，我们有了完备性，真的命题必定可以被证明。那么，它是不是可判定的？我们能不能找到一种机械计算的方法，判定其中数学陈述的对错？数学称述的真假，是否可判定的？这个问题，就是希尔伯特的可判定性问题。
注：希望更深入了解哥德尔不完备性定理的读者，可以重温旧文《希尔伯特之梦，以及梦的破灭》
在纽曼教授的数理逻辑课上，图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天，他刚刚完成在剑桥国王学院的四年本科学习，以优异的成绩被选为学院研究员，正准备在数学界大显身手，数理逻辑自然而然吸引了他的兴趣。图灵清楚地意识到，解决可判定性问题的关键，在于对“机械计算”的严格定义。考究希尔伯特的原意，这个词大概意味着“依照一定的有限的步骤，无需计算者的灵感就能完成的计算”，这在没有电子计算机的当时，算是相当有想象力又不失准确的定义。
但图灵的想法更为单纯。什么是“机械计算”？机械计算就是一台机器可以完成的计算，这就是图灵的回答。
用机器计算的想法并不新鲜。17世纪的莱布尼兹就曾设想过用机械计算来代替哲学家的思考，而19世纪的Charles Babbage和Ada Lovelace就设计出了功能强大的“分析机”，只可惜Babbage欠缺管理才能，这台超越了时代的机器始终没有完全造好。但图灵需要的机器，跟先驱设想的机器稍有不同。它必须足够简单，简单得显然能造出实物，也可以用一目了然的逻辑公式描述它的行为；它又必须足够复杂，有潜力完成任何机械能完成的计算。图灵要找的，是一种能产生极端复杂行为的简单机器。
这并非易事，但图灵做到了，据说这是他某次长跑过后，在某块草坪上发呆的成果。他设计了一类机器，然后定义“机械计算”为“这类机器可以完成的计算”。他设计的这类机器，正是日后以他名字命名的图灵机。
图灵机的示例。绿点指示处为当前状态，每条规则的4项分别是：当前位置读入的字符、当前位置写入的字符、纸带的移动方向、将要转移到的状态。
图灵机的结构非常简单，它由两部分组成：一个读写头，还有一条两边无限延长的纸带，纸带被划分为小格，每格中只能有0和1两种符号。读写头的限制则稍微宽松一些，虽然每次只能对着纸带上的一个格子，但它本身可以处于不同的状态，虽然状态的数目是有限的。在所有状态中，有一个特殊的“停机”状态，读写头一旦处于停机状态，就会停止运作；但如果读写头一直没有到达停机状态的话，它就会永远运转下去。
整台图灵机的秘密在于读写头的状态转移表，它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则，就是“如果在状态A的读写头对着符号x，那么对当前格子写入符号y，将纸带左移一格/右移一格/保持不动，然后转移到状态B”。状态转移表就是由一系列这样的简单规则组成的。可以说，状态转移表就相当于图灵机的源代码。
实际上，我们平时笔算乘法的思维过程，跟一台图灵机的运转非常相似：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息移动笔尖，在纸上写下符号；而指示我们写什么怎么写的，则是早已背好的九九乘法表，以及简单的加法。如果将一个笔算乘法的人看成一台图灵机，纸带就是用于记录的纸张，读写头就是这个人和他手上的笔，读写头的状态就是大脑的精神状态，而状态转移表则是笔算乘法的规则，包括九九表、列式的方法等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来，图灵机虽然看起来简单，但它足以作为机械计算的定义。
既然图灵机如此简单，能不能将它“升级”，赋予更多的硬件和自由度，使它变得更强大呢？比如说，让它拥有多条纸带和对应的读写头，而纸带上也不再限定两种符号，而是三种四种甚至更多种符号？的确，放宽限制之后，在某种程度上，对于相同的任务我们能设计出更快的图灵机，但从本质上来说，“升级”后的图灵机能完成的任务，原来的图灵机也能完成，虽然也许会慢些。也就是说，这种“升级”在可计算性上并没有意义，放宽限制后的机器能计算的，原来的机器也能完成。既然计算能力没有质的变化，无论采取什么样的结构，用多少种符号，都无所谓。
图灵机的一大优点，就是它的简单。只要给出状态转移表，任何一个人都可以模拟一台图灵机的计算。对工程师而言，在现实中用机械建造一台图灵机也并非什么难事。对于程序员来说，写一个模拟图灵机的简单程序更是不在话下。但如此简单的机器，它又能做什么呢？它真的能充当“机械计算”的定义吗？
正是80年前，1930年，希尔伯特在他退休时演讲的最后六个单词，也是鼓舞一代数学家的六个单词。尽管当时第三次数学危机仍然阴魂不散，但他们坚信，数学大厦的基础是坚实的。他们也坚信，任何数学真理，只要通过一代又一代人的不断努力，都能用逻辑的推理将其整合到数学的大厦中。
这是何等的气魄！这是何等的梦想！
但就在演讲前夕，他的同胞哥德尔，作出了一个断言，彻底打碎了这个梦。
希尔伯特
希尔伯特是一位名副其实的数学大师，有人将他称为“数学界最后一位全才”，他看待数学的眼光也是相当深刻的。师从林德曼，希尔伯特在23岁便以一篇关于不变量理论的论文跻身数学界。他的证明方法在当时相当具有争议性。
在这篇论文中，他使用了非构造性的证明，也就是说他只能证明某个数学对象的存在性，却无法将它具体指出。比如说，一个报告厅有100个座位，有99位听众进去了，我可以断定一定有一个空座位，这就是一种非构造性证明。但我没办法将具体的空座位指出来，希尔伯特也无法具体构造所要证明的对象，所以当时也受到了一些数学家的批评。
另外，他的证明依赖于对无穷的对象使用排中律，从而遭到了不少人的质疑。
排中律，说的就是一件事非真即假，这再明白不过了，为什么还有反对的意见呢？
比如说这样一个命题：π中含有任意长度的连续数字9。如果我们接受排中律的话，这个命题非真即假。但无论这个命题是真是假，我们都无法在实际上验证，因为要验证这个命题，我们都要将π无穷地计算下去，而这是不可能做到的。所以，人们对于将排中律用到这种无穷的情况仍有顾虑，因为这不是他们的直觉能掌握的范围。
我们不知道是否因为这件事，希尔伯特动起了为整个数学寻求一个坚实基础的念头，但我们可以知道，在经过多年在不同数学领域富有成果的涉猎后，希尔伯特将目光投向了整个数学。对平面几何学的严格公理化可能是他在这方面的第一个尝试，但他的思考绝不仅限于几何。他的目标是将整个数学体系严格公理化，然后用元数学——证明数学的数学——来证明整个数学体系是坚实的。
为了这个目标，他制定了著名的希尔伯特计划。
首先，将所有数学形式化，让每一个数学陈述都能用符号表达出来，让每一个数学家都能用定义好的规则来处理这些已经变成符号的陈述。这使数学家可以摆脱自然语言的模糊性，取而代之的是毫无含糊之处的符号语言。比如说，我们如果想说“存在一个集合是空的”，我们就必须解释什么是存在，什么是空，等等。但如果用符号表达这句话的话，就成了：
，这就毫无含糊之处了。
然后，证明数学是完整的，也就是说所有真的陈述都能被证明，这被称为数学的完备性；证明数学是一致的，也就是说不会推出自相矛盾的陈述，这被称为数学的一致性。完备性保证了我们能证明所有的真理，只要是真的就可以证明；一致性确保我们在不违背逻辑的前提下获得的结果是有意义的，不会出现一个陈述，它既是真的又是假的。
最后，找到一个算法，可以机械化地判定数学陈述的对错，这被称为数学的可判定性。
如果这个计划完成了，那意味着什么？首先，一致性是很重要的，因为我们不能接受比如说“哥德巴赫猜想既对又不对”这样的结论，一致性就保证了自相矛盾的情况不会出现。在保证数学的一致性这个前提下，我们又有数学的完备性，也就是说只要是真的都可以证明。这其实就是说，对于任意一个数学猜想，不管它有多难，只要假以时日，通过一代又一代人的努力，总是可以知道这个猜想对不对，并且证明或否定它。换句话说，我们知道，在数学中，通过逻辑，我们必定能知道我们想要知道的东西，这只是个时间问题。
我们必须知道，我们必将知道。
这是个雄心勃勃的计划，但希尔伯特并不认为这是不可能的。他提出，先在基础的数学系统进行这样的形式化，然后再将其推广到更广阔的数学系统中，最后实现整个计划。于是，整个计划便归结于在算术系统中进行这样的形式化，并且在它的内部证明它的完备性、一致性和可判定性。算术系统可以说是非常基础的，我们做算术，对自然数做加法、乘法和数学归纳法，就都用到了这个系统。但我们平时只是凭直觉来理解这个系统，而数学家追求的是用逻辑的方法来定义它，这样他们才会觉得安心。
这似乎不太困难。算术系统并不是一个很复杂的系统，它早在1889年就被皮亚诺归结成一个有5条公理的系统，其中只有最后一条数学归纳法公理比较复杂。我们可以想象，希尔伯特本人也认为这是可以解决的问题。他将算术公理系统的相容性列入了他那23道希尔伯特问题中，位列第二，希望20世纪的数学家能给出一个证明。这份1900年写出的问题表，后来证明是相当具有前瞻性的，即使情况并不一如希尔伯特预计的那样。
1931年，仅仅在他退休一年之后，希尔伯特第二问题即告解决，尽管解决的方式是希尔伯特所没有预料到的。
逻辑弄人。
哥德尔
可以说，哥德尔粉碎了希尔伯特计划。
在希尔伯特退休之时，哥德尔才刚刚登上数学舞台。在某种意义上，正是希尔伯特间接将哥德尔引领到数理逻辑这个领域的。在希尔伯特和他的学生阿克曼合著的《数理逻辑原理》中，他们提到了这样一个问题：在形式系统中，真的命题是否都是可证明的？这正是哥德尔博士论文的主题。在这篇论文中，哥德尔证明了一阶谓词演算是完备的，这就是不太著名的哥德尔完备性定理。一阶谓词演算是一种能力比较弱的数学系统，如果只是应用它的话，我们连自然数都定义不了，就更别说做算术了。自然，哥德尔的目光是不会仅仅局限于此的。
在完成博士论文之后，哥德尔便着手探索更一般的数学系统。一年后，也就是1931年，他对算术系统的探索即告胜利。这个胜利，也就是希尔伯特计划的失败。他的结论，就是哥德尔不完备性定理，一共有两个。
第一，他证明了，对于任意的数学系统，如果其中包含了算术系统的话，那么这个系统不可能同时是完备的和一致的。也就是说，要是我们能在一个数学系统中做算术的话，那么要么这个系统是自相矛盾的，要么有那么一些结论，它们是真的，我们却无法证明。
第二，他证明了，对于任意的数学系统，如果其中包含了算术系统的话，那么我们不能在这个系统内部证明它的一致性。这就是希尔伯特第二问题答案的一部分。
其实，这里“任意的数学系统”之中的“任意”并不是完全的任意。这些系统必须是可以显式地规定出来的，用数学的术语来说就是可有效生成的。但对于我们熟悉的像欧几里德公理这样的形式系统来说，这的确是相当任意了。
哥德尔证明这两个定理的武器，就是希尔伯特在他的计划中使用的武器：形式化。在哥德尔的证明中，他先将所有的数学陈述以及它们的证明用符号形式地表达出来，然后利用哥德尔自己发明的一个重要技巧——哥德尔数化——将所有这些陈述和证明变为一个个的自然数。那么，借助数学归纳公理，我们可以递归地建立针对所有自然数的陈述，而一个这样的陈述同时又是一个自然数，所以它描述了自己。换句话说，这个陈述陈述了它自己。
自指
这种自指的情况，在数学上很有用，也非常凶险。它是不少悖论的源泉。第一个例子当然是说谎者悖论：“这句话是错的”。第二个就是罗素悖论，它引起了第三次数学危机，这也可以说是希尔伯特计划的一个动因。
我们来看看它的一个通俗版本，叫理发师悖论。
在一个小镇内，只有一名理发师，他在理发店门外公布了这样一个原则：只为不会自己理发的人理发。那么，他的头发谁理呢？要是他自己理的话，他就会自己理发了，那么根据他的原则，他不应该为自己理发；要是他不给自己理发的话，根据他的原则，他倒是应该给自己理发。逻辑似乎在这里失效了。
这种逻辑上的混乱局面，背后就是罗素悖论：定义一个集合，它包含所有不包含自身的集合，它是否包含自身？从上面的分析，我们可以看到，一切问题在于“包含自身”这种自指的描述。后来，在策梅洛和弗兰克等逻辑学家的努力下，通过在集合论中添加正则公理等限制，才将这种危险的自指从集合论中排除。当然，这是后话了。
这种自指的性质，尽管危险，但在哥德尔的妙手中，它就变成了证明的利器。他构造了一个命题，这个命题说的正是它自身的不可证明性。如果用类似说谎者悖论的语言来表达的话，就是：“不存在对这个命题的形式证明。”如果它是真的，那么它是不可证明的，说明系统是不完备的，因为存在一个真的而又不可证明的命题。如果它是假的，那么存在一个它的证明，这样它应该是真的，说明系统是自相矛盾的、不一致的。这就是哥德尔的第一个不完备性定理：如果有自然数的话，完备性和一致性不可得兼，这个系统要么自相矛盾，要么存在不能证明也不能否证的命题。
然后，我们来仅仅考虑一致性的问题。假定系统是一致的，也就是说不会自相矛盾的，那么我们刚才提到的命题就是不可证明的。如果我们能在系统内部证明系统的一致性的话，我们就相当于在系统内部证明了那个命题，这与不可证明性是矛盾的。也就是说，我们做了错误的假设：能在系统内部证明系统本身的一致性。由此，哥德尔证明了他的第二个不完备性定理。
他的这两个不完备性定理，对于希尔伯特计划是个沉重的打击：计划的第二步被证明是无法实行的。如果我们假定数学不会自相矛盾的话，我们就必须承认数学是不完备的，也就是说有这么一些数学命题是不可判定的：我们既不能证明它们为真，也不能证明它们为假。但很多数学家仍然认为，这并不威胁数学的正常发展，因为他们觉得有意义的数学命题极不可能是这样的。换句话说，数学家们仍然相当乐观。
同样是哥德尔，这次连同科恩，给这些数学家敲响了警钟：数学家研究的“有意义”的数学命题也可能是不可判定的。他们解决的又是一个希尔伯特问题：由康托尔提出的连续统假设。这个问题位于列表之首，是一个纯粹的集合论问题。哥德尔证明了连续统假设和策梅洛-弗兰克集合论是相容的，也就是说二者之间没有矛盾；科恩证明了从策梅洛-弗兰克集合论出发不能证明连续统假设。这两个结果综合起来，其实就说明了连续统假设在策梅洛-弗兰克集合论中是不可判定的。要是你知道策梅洛-弗兰克集合论正是解决第三次数学危机的武器和现代数学的逻辑基础，你就会明白这到底意味着什么。
哥德尔的魔鬼第一次露出了真面目。希尔伯特第一问题竟然就是不完备性定理中预言的那类不知真假的怪异命题的一个实例，这实在令人泄气。
既然希尔伯特计划的第二步都被证明是不可行的，那么第三步也就没有必要继续下去了。第三步是寻求一个能机械证明所有数学定理的程序，著名的停机定理也否定了这种可能性。停机定理的证明相对比较简单，也是利用自指的技巧，证明这样程序是不可能存在的。
至此，希尔伯特那宏伟的计划宣告全盘失败。
有些事情，我们确实不知道，即使对于数字，这是逻辑说的。
既然对全部数学真理进行形式化是不可能的，数学家们只好退而求其次，尝试形式化他们熟悉的数学。法国的布尔巴基学派在这方面似乎走得最远。这是在巴黎高师的一帮数学家，继承了希尔伯特的一些理念，目标是将所有已知的数学在集合论的坚实基础上重建。他们出版了九本这方面的专著，每一部都以严密的公理化方法吸引着后来者的目光。他们的每本著作都会经过多次的修订，据说明年他们又会出版一本新修订的著作。
布尔巴基办公室门牌，fwjmath拍摄
令希尔伯特在天国的灵魂有所安慰的是，算术系统的一致性被证明了。这个证明用到了不在算术系统内的超限归纳法，它可以被视为一种加强版的数学归纳法，是用在无穷序数上的。这其实就假定了策梅洛-弗兰克集合论的一致性。当初康托尔建立无穷集合论时，曾遭到不少人的攻击，这时希尔伯特挺身而出，为康托尔和他的无穷集合论疾呼：“没人能将我们从康托尔创造的乐园中赶出来。”如今，康托尔的无穷集合论衍生出来的超限归纳法反过来又部分实现了希尔伯特的梦，这是冥冥之中的安排，还是希尔伯特的敏锐眼光所致？恐怕没人能说得清楚。
但哥德尔的魔鬼仍在肆虐。越来越多的数学问题被证明是不可判定的，这些不可判定的问题也越来越初等。乍看起来并非不可捉摸，但到头来却不可判定。比如说，如果我们用可数种颜色对每一个实数染色，是否必定存在4个互不相等的数a,b,c,d，使得它们的颜色都相同，而又满足a+b=c+d？这看起来怎么也不像没有一个确切结论的问题，但有人证明了它实际上和连续统假设的否定是等价的，也就是说，在策梅洛-弗兰克集合论内，它也是不可判定的。这就给数学家们心头压上了一块大石：谁也不知道自己辛辛苦苦做了十几年的题目，会不会突然有一天被证明是在现有数学体系中不可判定的。
尽管这样，哥德尔的不完备性定理仍然带给我们很多教益。至少我们知道了，有些东西我们不可能知道。在哥德尔的这个划时代的证明之后，数学家对数学的基本工具——证明——有了新的认识。专门研究数学证明的证明论，在他的启发下蓬勃发展。但是，哥德尔教给我们最重要的一点是：
数学，如同人生，如同爱情，有些东西是真的，你却永远无法证明。
关于程序算法艺术与实践更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.
原文：http://blog.csdn.net/songzitea/article/details/50678087
