一切从逻辑开始
1900年的巴黎，在世纪交替之际，希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的“希尔伯特计划”的最后一步。这位数学界的巨人，打算让整个数学体系矗立在一个坚实的地基上，一劳永逸地解决所有关于对数学可靠性的种种疑问。一切都为了回答三个问题：
数学是完备的吗？也就是 说，面对那些正确的数学陈述，我们是否总能找出一个证明？数学真理是否总能被证明？
数学是一致的吗？也就是说，数学是否前后一致，不会得出某个数学陈述又对又不对的结论？数学是否没有内部矛盾？
数学是可判定的吗？也就是说，能够找到一种方法，仅仅通过机械化的计算，就能判定某个数学陈述是对是错？数学证明能否机械化？
希尔伯特明确提出这三个问题时，已是28年后的1928年。在这28年间，数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久，仅仅三年后，哥德尔就得到了前两个问题的答案，尽管这个答案不是希尔伯特所希望看到的。
哥德尔的答案分两部分。
第一，任何包含了算术的数学系统都不可能同时拥有完备性和一致性，也就是说，如果一个数学系统包含了算术的话，要么它是自相矛盾的，要么存在一些命题，它们是真的，但我们却无法证明。这说明，希尔伯特的前两个问题不可能同时为真。在这里，“算术”有着精确的含义，就是皮亚诺公理，一组描述了自然数的公理。
第二，任何包含了算术的数学系统，如果它是一致的，那么我们不能在它的内部证明它本身的一致性。这说明，我们没有希望解决第二个问题。
这就是著名的哥德尔不完备性定理，与其说它回答了希尔伯特的前两个问题，不如说它阐述了为什么我们根本不可能解决这两个问题。
哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化，然后给每个符号串赋予一个数字，这个过程被称为哥德尔配数法。借助数学归纳法，我们可以建立针对所有自然数的陈述，而这样的陈述本身对应着一个数字，这个数字也符合陈述本身的要求。换言之，这个陈述陈述了它本身的性质。哥德尔正是通过这样魔法般的自指，完成了他的证明。这个证明之所以重要，是因为它第一次提供了一套完整的数学工具和方法，用于证明有关数学证明的不可能性。这本身就是数学的一次重大胜利，说明数学的力量强大得可以用纯粹逻辑的方法，证明它本身的力量是有界限的。在数学的领地上，有些东西我们不知道，也不可能知道。
希尔伯特的前两个问题已经解决，只剩下最后一个问题。然而，如果一个数学系统不完备的话，它显然不可能是可判定的，因为机械化的计算本身也可以看成一种证明，而在一个不完备的系统中，真理不总能被证明。所以，最后一个问题只对完备的数学系统有意义。
所幸，完备的数学系统是存在的。同样是哥德尔，他证明了所谓“一阶谓词演算”的逻辑系统是完备的，这被称为哥德尔完备性定理。一阶谓词演算是一个比较弱的逻辑系统，在其中我们甚至不能有效唯一地描述算术。比如说，自然数系统符合皮亚诺公理的一阶版本，但它并不是唯一的，还有无数种所谓“非标准模型”同样符合这套一阶系统。在一阶谓词演算中，对于一套公理系统，如果一个命题在所有的模型中都正确，那么必定可以形式地证明这个命题，这就是一阶谓词演算的完备性。在一阶谓词演算中，真理总能被证明。
在这个弱得多的逻辑系统中，我们有了完备性，真的命题必定可以被证明。那么，它是不是可判定的？我们能不能找到一种机械计算的方法，判定其中数学陈述的对错？数学称述的真假，是否可判定的？这个问题，就是希尔伯特的可判定性问题。
复杂的简单机器
在纽曼教授的数理逻辑课上，图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天，他刚刚完成在剑桥国王学院的四年本科学习，以优异的成绩被选为学院研究员，正准备在数学界大显身手，数理逻辑自然而然吸引了他的兴趣。图灵清楚地意识到，解决可判定性问题的关键，在于对“机械计算”的严格定义。考究希尔伯特的原意，这个词大概意味着“依照一定的有限的步骤，无需计算者的灵感就能完成的计算”，这在没有电子计算机的当时，算是相当有想象力又不失准确的定义。
但图灵的想法更为单纯。什么是“机械计算”？机械计算就是一台机器可以完成的计算，这就是图灵的回答。
用机器计算的想法并不新鲜。17世纪的莱布尼兹就曾设想过用机械计算来代替哲学家的思考，而19世纪的Charles Babbage和Ada Lovelace就设计出了功能强大的“分析机”，只可惜Babbage欠缺管理才能，这台超越了时代的机器始终没有完全造好。但图灵需要的机器，跟先驱设想的机器稍有不同。它必须足够简单，简单得显然能造出实物，也可以用一目了然的逻辑公式描述它的行为；它又必须足够复杂，有潜力完成任何机械能完成的计算。图灵要找的，是一种能产生极端复杂行为的简单机器。
这并非易事，但图灵做到了，据说这是他某次长跑过后，在某块草坪上发呆的成果。他设计了一类机器，然后定义“机械计算”为“这类机器可以完成的计算”。他设计的这类机器，正是日后以他名字命名的图灵机。
图灵机的示例。绿点指示处为当前状态，每条规则的4项分别是：当前位置读入的字符、当前位置写入的字符、纸带的移动方向、将要转移到的状态。
图灵机的结构非常简单，它由两部分组成：一个读写头，还有一条两边无限延长的纸带，纸带被划分为小格，每格中只能有0和1两种符号。读写头的限制则稍微宽松一些，虽然每次只能对着纸带上的一个格子，但它本身可以处于不同的状态，虽然状态的数目是有限的。在所有状态中，有一个特殊的“停机”状态，读写头一旦处于停机状态，就会停止运作；但如果读写头一直没有到达停机状态的话，它就会永远运转下去。
整台图灵机的秘密在于读写头的状态转移表，它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则，就是“如果在状态A的读写头对着符号x，那么对当前格子写入符号y，将纸带左移一格/右移一格/保持不动，然后转移到状态B”。状态转移表就是由一系列这样的简单规则组成的。可以说，状态转移表就相当于图灵机的源代码。
实际上，我们平时笔算乘法的思维过程，跟一台图灵机的运转非常相似：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息移动笔尖，在纸上写下符号；而指示我们写什么怎么写的，则是早已背好的九九乘法表，以及简单的加法。如果将一个笔算乘法的人看成一台图灵机，纸带就是用于记录的纸张，读写头就是这个人和他手上的笔，读写头的状态就是大脑的精神状态，而状态转移表则是笔算乘法的规则，包括九九表、列式的方法等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来，图灵机虽然看起来简单，但它足以作为机械计算的定义。
既然图灵机如此简单，能不能将它“升级”，赋予更多的硬件和自由度，使它变得更强大呢？比如说，让它拥有多条纸带和对应的读写头，而纸带上也不再限定两种符号，而是三种四种甚至更多种符号？的确，放宽限制之后，在某种程度上，对于相同的任务我们能设计出更快的图灵机，但从本质上来说，“升级”后的图灵机能完成的任务，原来的图灵机也能完成，虽然也许会慢些。也就是说，这种“升级”在可计算性上并没有意义，放宽限制后的机器能计算的，原来的机器也能完成。既然计算能力没有质的变化，无论采取什么样的结构，用多少种符号，都无所谓。
图灵机的一大优点，就是它的简单。只要给出状态转移表，任何一个人都可以模拟一台图灵机的计算。对工程师而言，在现实中用机械建造一台图灵机也并非什么难事。对于程序员来说，写一个模拟图灵机的简单程序更是不在话下。但如此简单的机器，它又能做什么呢？它真的能充当“机械计算”的定义吗？
计算的极限（一）：所有机器的机器，与无法计算的问题
所有机器的机器
图灵机非常简单，只要明白了它的运作过程，任何一个受过足够训练的计算机系本科生都可以写出一个模拟图灵机运行的程序。只消输入状态转移表和纸带的输入内容，程序就可以一步一步模拟相应的图灵机在纸带上爬来爬去的过程。对于一些熟悉图形编程的程序员来说，做个模拟动画也问题不大。即使不用计算机，靠人手一步步操作，也是一件小孩子也能完成的事。图灵机就是这么简单的一种机器。
虽然看上去简单，但实际上图灵机能做的事情远远超出一般的想象。只要有足够长的纸带和足够好的耐心，今天的电脑能做的计算，一台精心设计的图灵机也能完成。诀窍在于，电脑中的电路是有限的，电路的状态也是有限的，我们可以用图灵机去模拟电脑中的电路状态。只要有足够长的纸带，那就可以模拟出足够大的寄存器、内存和硬盘；而CPU中的电路，虽然所有可能的状态极其多，但终究是有限的，可以用图灵机模拟，虽然这台图灵机的状态转移表将会有着令人头痛的大小，以及令人偏头痛的复杂程度。但是，从原则上来说，用图灵机模拟一台电脑是完全可能的，虽然每次“读写内存”时，读写头都需要花长得令人咋舌的时间在纸带上来回奔波。
也就是说，从原则上来说，只要配备适当的输入和输出设备，以及极其好的耐心，我们完全可以用图灵机上网、玩游戏甚至执行自己写的程序。特别地，存在一台特定的编写程序专用的图灵机T，我们可以在纸带上写程序，将它输入到T，然后T就能执行这个程序。那么，如果我们将方才本科生写的那个可以模拟任意图灵机运行的程序（暂且把它称为程序P），写在纸带上输入到T中，让T去执行的话，原本的机器T就摇身一变，变成了一台可以根据输入的状态转移表来模拟任何一台图灵机的图灵机。
更精确地说，因为程序P的长度是有限的，我们可以将它直接写进原来机器的状态转移表，得到一台新的机器UTM。UTM会在纸带上读取两样东西：一台图灵机M的状态转移表的二进制编码，以及作为M的初始输入的纸带数据。然后，UTM会根据M的状态转移表和初始输入数据，在纸带上模拟M的运作过程。换言之，UTM是一台可以模拟任何图灵机的图灵机。它是所有机器的机器，所谓的通用图灵机（Universal Turing Machine）。当然，通用图灵机并不是唯一的，只要一台图灵机能完成根据状态转移表模拟任意图灵机的任务，它就是通用图灵机。
一台通用图灵机，数据具体格式请参见来源：http://rendell-attic.org/gol/utm/utmprog.htm
通用图灵机的想法，在如今这个计算机泛滥的时代，似乎并不新鲜。但在图灵的1935年，电子计算机甚至仍未问世，机械计算机还只能执行内设的一套指令。即使是Charles Babbage和Ada Lovelace的超越时代的设想，其中执行外部程序的概念也相当含混不清。在这种历史背景下，要归纳出通用图灵机这个概念，本身就需要极为丰富的想象力，而且这种图灵机是否存在，这是个远非显然的问题。而图灵不仅设想到了这个概念，而且正确地判断出它的存在性，这需要何等非凡的直觉！
但单纯的直觉终究不能令人信服，数学家讲究的是逻辑和证明。而要证明通用图灵机的存在，最直接的方法莫过于直接给出一个通用图灵机的实例。这并不简单，如果读者想尝试一下的话，我建议先尝试构造一个能做二进制加法的图灵机。为了降低难度，可以假设纸带上有第三种符号，表示空白，但即使如此，要构造一个能做加法的图灵机，远比想象中的困难。可想而知，通用图灵机的构造肯定更为复杂繁琐。即使是图灵，他在一开始给出的构造也是有问题的，而这些问题甚至在后来的勘误中也没有成功修正。比构造更麻烦的是证明给出的图灵机的确是一台通用图灵机，在图灵解决希尔伯特可判定性问题的论文中，有关通用图灵机的构造和证明占了相当大的篇幅。这部分非常繁复琐碎，而且其中还有错误，如果细细研读的话，绝对有诱发剧烈偏头痛的危险。
幸运的是，无论细节多么复杂，图灵的想法还是被逻辑学家们接受了。一旦领会到图灵机的能力，接受了通用图灵机的构想，再检查几个能完成基本任务的图灵机之后，大部分数学家都会认为通用图灵机的确存在，尽管他们并不一定会细看图灵的详细构造。而现代电子计算机的发展，更是验证了通用图灵机的存在：每一台电脑都相当于一台通用图灵机。
通用图灵机的存在，从侧面说明了图灵机这个计算模型的强大之处：图灵机作为一类机器，其中一个特例就可以模拟整个类别中的任意一台机器，宛如能折射大千世界的一滴水珠。但在这种强大的背后，隐隐也暗藏着不安定的因素。哥德尔不完备性定理告诉我们，有时候越强大的数学理论，因为能表达的概念太多，甚至连理论的命题和证明都能表达，反而会导致不能被证明的真命题的存在。如果一个系统足以描述它自己，那魔法般的自指将是不可避免的。图灵机如此强大，它的其中一台就可以模拟所有图灵机，会不会导致不能用计算来回答的问题存在呢？
很不凑巧，答案是会。
无法计算的问题
在哥德尔不完备性定理的证明中，哥德尔构造了一个描述了本身不可证明性的自指命题，通过这个命题完成了他的证明。要想照葫芦画瓢的话，那些关于图灵机本身的问题，将会是很好的候补。
关于图灵机，最简单的问题是什么呢？回想一下图灵机的运作过程，一台图灵机从初始状态开始，根据纸带上的内容，一边不断变换状态，一边更改纸带的内容，如此往复永无休止，除非它遇上了表示停机的那个状态，才能从这机械的计算过程中跳出，获得静息的安乐。一个自然的问题是：一台图灵机什么时候会停机呢？
更严格地说，会不会停机并不是图灵机本身的属性，它跟纸带的初始输入也有关系。对于同一台图灵机，不同的纸带输入也可能导致不同的结果和行为。比如说，我可以设计一台图灵机，它的任务只有一个：一步一步向右移动，寻找输入中的第一个1。如果输入纸带上全是0的话，那么，这台图灵机自然不会停止；但只要纸带上有一个1，那么它就会停止。所以，真正严谨的问题是：给定一台图灵机M以及一个输入I，如果我们将I输入M，然后让M开始运行，这时M是会不停运转下去，还是会在一段时间后停止？我们将这个问题称为停机问题。
初看起来，停机问题并不难。既然我们有通用图灵机这一强大的武器，那么只需要用它一步步模拟M在输入I上的计算过程就可以了。如果模拟过程在一段时间后停止了，我们当然可以得出“M在输入I上会停止”这个结论。问题是，在模拟过程停止之前，我们不可能知道整个计算过程到底是不会停止，它可能会在3分钟后停止，可能要等上十年八载，更有可能永远都不会停止。换句话说，用模拟的方法，我们只能知道某个程序在某个输入上会停止，但永远不能确定那些不停止的状况。所以说，单纯的模拟是不能解决停机问题的。
实际上，停机问题比我们想象中要复杂得多。
举个例子，我们可以编写一个程序GC，它遍历所有大于等于6的偶数，尝试将这样的偶数分成两个素数的和。如果它遇到一个不能被分解为两个素数之和的偶数，它就停机并输出这个偶数；否则，它就一直运行下去。用现代的工具编写GC这样的程序，对于计算机系的学生最多只能算一次大作业；用图灵机实现的话，也不是什么极端困难的事。然而，GC是否会停止可是牵涉到了哥德巴赫猜想。如果哥德巴赫猜想是正确的，每个大于等于6的偶数都能分解为两个素数之和的话，那么GC自然会一直运行下去，不会停机；如果哥德巴赫猜想是错误的话，必定存在一个最小的反例，它不能分解为两个素数之和，而GC在遇到这个反例时就会停机。也就是说，GC是否永远运行下去，等价于哥德巴赫猜想是否成立。如果我们能判定GC是否会停止，那我们就解决了哥德巴赫猜想。
数学中的很多猜想，比如说3x+1猜想、黎曼猜想等，都可以用类似的方法转化为判断一个程序是否会停止的问题。如果存在一个程序，能判断所有可能的图灵机在所有可能的输入上是否会停止的话，那么只要利用这个程序，我们就能证明一大堆重要的数学猜想。我们可以说，停机问题比所有这些猜想更难更复杂，因为这些困难的数学猜想都不过是一般的停机问题的一个特例。如果停机问题可以被完全解决，我们能写出一个程序来判断任意图灵机是否会停机的话，那么相当多的数学家都要丢饭碗了。
停机问题如此复杂，机械的计算看起来没有足够的力量来完全解决它。停机问题似乎是不可计算的。但要想严格证明这个结论，似乎仍要求助于深藏在图灵机之中，那魔法般的自指。
计算的极限（二）：自我指涉与不可判定
矛盾的自我指涉
在现实中，证明某种东西不存在是非常困难的。要证明某种东西存在，只要举出一个例子就可以了；但要证明某种东西不存在，就要想办法排除所有的可能性，而在现实生活中，这几乎是不可能的。所以，只要能排除那些比较主要的可能性，任务就算完成。但在数学中，情况大不相同：通过形式逻辑的方法，我们可以确实地证明某种数学对象不存在。这都要归功于数学那彻底的抽象化和形式化。
数学家在证明某个数学对象不存在的时候，经常会来一招“欲擒故纵”：首先假设它存在，那么它必然具有某些特定的性质，再利用这些性质，用严密的逻辑推理引出一个不可能的结论。既然结论是不可能的，而逻辑推理又没有问题，那么一定是推理的出发点出了差错：作为推理基础的那个东西，其实并不存在。这种证明方法，就是反证法。
现在，我们尝试用反证法证明停机问题是不可计算的。
按照反证法的格式，我们先反其道而行之，假设停机问题是可以计算的。根据定义，这说明存在一台图灵机P，使得向它输入某个图灵机M的状态转移表编码<M>，以及初始输入I，图灵机P就能在有限步运算内，判断出机器M在输入I上是否会停止。
接下来，我们将要用图灵机P构造一个逻辑上不可能存在的结构，这将是证明的关键。
我们来考虑一个新的图灵机R，它的输入是某个图灵机M的状态转移表编码<M>。图灵机R先“调用”图灵机P，判断图灵机M在初始输入<M>上是否会停止。用现代的计算机语言来说，就相当于调用函数P(<M>,<M>)。如果图灵机P得出的结论是机器M在输入<M>上会停止的话，图灵机R接下来就会进入死循环；否则，如果机器M在输入<M>上不会停机的话，图灵机R就停止。
图灵机R的构造有两个奇怪之处。
首先，在图灵机R的运作中，它尝试判断一台图灵机M在它自身的编码<M>上的运作情况。此时，图灵机M不仅是程序，同时也是数据。这提醒我们，其实程序和数据没有实质的区别。程序只是一种特殊的数据，能够被分析、整理、改写。
事实上，我们每天都在使用处理程序的程序。比如说杀毒软件，其实就是一种扫描程序的程序。它检查每个程序的内容，判断程序中有没有威胁计算机安全的恶意代码。用杀毒软件扫描它自身，实际上就是让这个程序运作在它自身的代码之上。我们也可以用记事本打开记事本的程序本身，或者用压缩软件打一个包含它程序本身的压缩包。这些例子都说明了一个道理：程序就是一种数据。正因为程序就是数据，我们才得以完成图灵机的自我指涉。
其次，在图灵机R的构造中，如果M在<M>上停机，那么R就不停机；如果M在<M>上不停机，那么R就停机。这就是说谎者悖论的翻版：它的行为要与自己的判断相悖。
这样，我们就凑齐了说谎者悖论的两个要素：自我指涉和自我否定。剩下的，就是如何将这两个要素组合在一起，引出不可调和的矛盾了。
为了引出矛盾，我们来考虑图灵机R在自己的编码<R>上的运行情况。
如果R在<R>上停机的话，R必定没有进入死循环。所以，在调用图灵机P时，得到的必然是“图灵机R在输入<R>上不会停机”，才能避免死循环。但图灵机P的这个结论不符合我们的假设，出现了逻辑矛盾，所以R不可能在<R>上停机。
如果R在<R>上不停机的话，因为图灵机P必定在有限时间内完成计算，所以R必定进入了死循环。而R进入死循环的先决条件是，在调用图灵机P时，得到的是“图灵机R在输入<R>上停机”。而图灵机P的这个结论，同样不符合我们的假设。由于同样的逻辑矛盾，R同样不可能在<R>上不停机。
所以，根据严密的逻辑，我们构造的图灵机R在自己的编码<R>上，既不可能停机又不可能不停机，这是不可能的。另一方面，我们的逻辑推理也是没有问题的。尽管多么不情愿，剩下的可能性只有一种：我们假设的那个能完美解决停机问题的图灵机P，根本不存在！也就是说，停机问题是不可计算的。
这个结论，我们称之为停机定理。以上的论述，作为停机定理的证明远远不算严谨，还有很多细枝末节需要填充。但这些细节都是技术性的，并不妨碍主要的思想：矛盾的自我指涉。
停机定理的证明，一如哥德尔不完备性定理的证明，核心是化了妆的说谎者悖论。图灵机的能力如此强大，一台通用图灵机就可以完成一切图灵机的工作，将所有图灵机作为数据处理。也正因如此，图灵机不能解决某些牵涉它自身的问题，否则总会存在一些自我否定的“说谎者”，利用能解决牵涉自身问题的那些图灵机，完成被逻辑所禁止的，致命的自我指涉。图灵机的能力，在必然的逻辑推演下，同时也成了它的枷锁。
不可判定的重复
实际上，图灵一开始并没有证明停机定理。他证明的是：不存在这样的程序，能判断任意图灵机是否会至少打印出一个1。这里的“1”可以换成任意的符号。这个证明的方法要稍复杂些，不过本质上仍然是通过自我否定与自我指涉来制造悖论。而事实上，许多（但不是所有）有关图灵机的问题，都能用同样的方法被证明是不可计算的。这样，图灵手上就有了一套不可计算的问题，可以开始考虑希尔伯特的问题了。
我们回顾一下希尔伯特的问题。哥德尔证明了，所谓的“一阶谓词演算”是完备的。也就是说，在这个数学系统中，每个真理都能被证明，“真”和“能被证明”这两个概念是一致的。希尔伯特的可判定性问题是：是否存在一种计算过程，可以在有限步运算内，判断在这个完备的数学系统中每个命题的真假？
一阶谓词演算作为数学系统，在能力上实在是比不上数学家们常用的逻辑系统：它连自然数都不能很好地定义。但图灵发现，这个稍弱的数学系统已经足以表达图灵机的运行过程。对于每个图灵机M，通过巧妙然而机械化的操作，图灵都能构造出一阶谓词演算中的一个命题U(M)，使得U(M)成立当且仅当图灵机M会至少打印出一个1！也就是说，命题U(M)是否为真与图灵机M的运行过程息息相关。
剩下的证明就如同探囊取物了。如果希尔伯特的可判定性问题是可以计算的话，必定存在一台图灵机H，可以在有限时间内，判断每个命题的真假。对于一台图灵机M，我们要知道它是否会至少打印出一个1，可以先机械化地计算出与M有关的命题U(M)，然后用图灵机H去判断U(M)的真假，从而判断图灵机M是否会至少打印出一个1。也就是说，利用图灵机H，我们可以用计算回答一个不可计算的问题，而这是不可能的。所以，图灵机H并不存在，希尔伯特的可判定性问题的答案只有三个字：不可能。
希尔伯特的期望，又一次化为泡影。逻辑弄人。
图灵确信自己解决了希尔伯特的判定问题后，很快将他的想法写成了论文，它的题目是：
《论可计算数，及其在可判定性问题上的应用》（On Computable Numbers, With an Application to the Entscheidungsproblem）
他将论文交给了数理逻辑课的纽曼教授。这篇论文在纽曼教授的桌上放了几个星期。当教授终于有时间细读图灵的论文时，一开始根本不敢相信希尔伯特的问题竟然能通过对如此简单的机器的论证而解决，但无懈可击的逻辑论证最终战胜了怀疑。这无疑是划时代的工作，最终埋葬了希尔伯特的宏伟计划。
但正当纽曼教授联系各方，想办法发表图灵的论文时，从大西洋彼岸的普林斯顿，寄来了一篇论文：
《初等数论中的一个不可解问题》（An unsolvable problem of elementary number theory）
它的作者是丘奇（Alonzo Church），普林斯顿大学的一位年轻数学教授，当时在数理逻辑这一领域已经小有名气。而这篇文章的最后一句话是：
In particular, if the system of Principia Mathematica be ω-consistent, its Entscheidungsproblem is unsolvable.
（特别地，如果《数学原理》中的系统是ω-一致的话，它的可判定性问题是不可解的。）
对于图灵来说，这绝对不是一个好消息，因为这与他的结果是一样的。
那么，丘奇又是如何得到这个结论的呢？
计算的极限（三）：函数构成的世界
函数构成的世界
丘奇作为图灵在数学上的前辈，思考的问题自然比图灵要深远得多。图灵考虑的问题，仅仅是希尔伯特的可判定性问题，而丘奇当时思考的，是如何重构数学的基础。
当时正是第三次数学危机勃发之际，数学界各路人马对数学基础应该置于何处争论不休。当时公理化集合论刚刚建立，作为新事物，自然有人持观望态度，而丘奇就是其中一位，他觉得自己可以创造一个更好的理论，以此作为数学的基础。与其选择集合与包含这两个概念，他选择了数学中另一个重要的概念：函数。
数学家眼中的函数，比你想像的要广泛得多。在中学数学中，说到函数，自然会联想起它在平面直角坐标系的图像。这是因为中学数学中的函数，大部分情况下不过是从实数到实数的映射而已。而数学家眼中的函数，可能与程序员眼中的函数更相似：它们更像是一个黑箱，从一边扔进去某个东西，另一边就会吐出来另一个东西。
我们并没有限定能扔进黑箱的东西。事实上，将黑箱本身扔进黑箱也是可以的。对这种把戏，数学家们再熟悉不过了，在泛函分析这一数学分支中，数学家们就经常研究一种叫“算子”的数学概念，在某些特殊情况下，就是那些将一个函数变成另一个函数的函数。所以，不去限定能扔进黑箱的东西，似乎也没什么问题。
分崩离析的世界
丘奇最初建立λ演算的目的，是希望将它作为一种逻辑推理的方法。我们可以将某些逻辑公理表达为λ项；对于某个逻辑命题，我们可以先将其转化为λ项，再根据λ演算的法则将它不断简化，而命题正确与否就蕴含在计算结果之中。
通过这种方法，丘奇成功地在λ演算的框架下表达了不少的数学系统。λ演算看起来是如此的成功，甚至达到了无所不能的程度。
但如果我们还记得哥德尔的教训的话，无所不能有时并不一定是什么好事，因为在数学和逻辑的领域中，对于有意义的逻辑系统，强大的表达能力必然伴随着坚不可摧的限制。如果一个系统无所不能，那么更大的可能是它本身就自相矛盾。就像一个理论，如果对的也好错的也罢，正面反面都能解释得通，那相当于完全没有解释。
果然，几乎在丘奇向学术界展示他的λ演算的同时，Kleene和Curry就证明了，作为一个逻辑推理系统，λ演算在本质上就存在着矛盾，它是不一致的。通过适当地构造一些λ项，Kleene和Rosser成功地利用λ演算找到了一切命题的证明，甚至包括那些错误的命题！一个连错误的命题都能证明的逻辑系统，也就是说一个不一致的逻辑系统，没有任何意义。
值得一提的是，上面这几位后来都成为了数理逻辑界的大人物。Kleene和Rosser是丘奇的学生，而Curry则师从希尔伯特。我们后面还会讲到这位Curry教授，他的事迹之一就是有整整三个不同的编程语言是以他的名字命名的，连中间名都用上了，影响力可见一斑。
事实上，丘奇当初在筑建λ演算之时，就已模糊地认识到了这个问题，但他觉得这只是一种幻象，通过某些适当的限制，就能摆脱这些恼人的问题。但丘奇错了，实际上这是一个本质性的问题。
那么，问题的根源在何处？
我想，读过本系列之前文章的读者应该都猜到了，又是那绕不过去的自我指涉！
但是，自我指涉在什么地方呢？
还记得λ项是什么东西呢？它的原型是函数，但不是一般的函数。在定义λ项之时，我们允许它将任意的λ项转化为另一个λ项。既然是任意的λ项，那么当然也包括它自己。如果将λ项看成程序的话，那又是一个可以将自己当作输入数据的程序。与图灵机不同的是，在λ演算之中，根本没有数据和程序之分，一切都是λ项，它们既是程序，也是数据。
丘奇没有就此止步。虽然λ演算不能如他所愿成为数学的推理基础，作为一个计算模型似乎倒也不错。我们可以将一个计算过程看成函数，将输入数据转化为输出数据的函数。于是丘奇将“可有效计算”定义为“可以用λ演算表达的函数”。这时，自我指涉的特性就成为了不可多得的优点，因为这实际上说明λ演算有强大的计算能力。利用自我指涉的特性，通过相似的构造方法，丘奇同样解决了希尔伯特的可判定性问题，得到了与图灵相同的结论。
丘奇在构想λ演算之时，瞄准的是更为基本的数学基础模型，但它却成为了可计算性的模型，真可谓“无心插柳柳成荫”。这就是图灵看到的那篇论文的由来。
不难想象图灵当时读到这篇论文时的心情。如果将数学比作攀山，当你千辛万苦登上一座处女峰，却蓦然发现山顶已经插上了别人的旗帜，你大概会觉得一切都似乎失去了意义。
但数学毕竟不是攀山，不同的路径可能有不同的景致，要论高下为时尚早。况且要比较两者，要先知道两者解决的到底是不是同一个问题。虽然图灵和丘奇解决的都是同一个问题，但他们对“可计算性”各自做了不同的假定。图灵认为“可计算的问题”就是图灵机可以解决的问题，而丘奇则认为那应该是λ演算可以解决的问题。
问题是，图灵机和λ演算这两个计算模型，它们解决问题的能力一样吗？两种视点下的可计算性，到底是殊途同归，还是貌合神离？
计算的极限（四）：机械计算的圭臬
殊途同归
大洋彼岸寄来的论文，对于图灵来说，并不是什么好消息。在看到丘奇的论文后，图灵有过何等反应，至今恐怕已不可考。面对着一位在数理逻辑方面已然小有名气的职业数学家，与自己一起独立发现了相同的突破性结果。往好处想，这说明图灵自己的水平已经达到了当时数理逻辑研究的前沿；往坏处想，重复了别人的结果，哪怕是独立发现的，似乎都有些不对味儿。
然而，在下定论之前，图灵还有一件事情要搞清楚。他和丘奇对“可计算性”的定义，分别建筑在图灵机与λ演算之上。那么，在不同的基础上定义的两种“可计算性”，是貌合神离还是本为一体？
图灵机与λ演算，两者似乎都在平平无奇中暗藏玄机。作为计算模型，它们有很多相似之处，比如自我指涉的能力。但它们看起来又是如此不同，图灵机是一台在工程上能建造的机器，而λ演算则是一个彻头彻尾的数学模型。看起来，要回答这个问题，并非易事。
图灵知道，丘奇也知道，他们已经踏入了一个新领域。昔日希尔伯特在他的二十三个问题中，一语带过的那个“机械化的运算”，即将被赋予精确的数学含义。但正因如此，踏出的第一步必须慎之又慎，尤其对于“可计算性”这个最基础的定义，必须做到毫不含糊。为此，为了消除模棱两可之处，图灵机与λ演算是否能力相当，这是个必须回答的问题。
知己知彼，百战不殆。为了解答这个问题，图灵开始钻研λ演算，试图弄清到底λ演算能计算什么。终于，他证明了，所有λ演算能计算的函数，他的图灵机也能计算，反之亦然。也就是说，λ演算与图灵机的计算能力是等价的，两种模型定义的“可计算性”实际上殊途同归。他将这个结果作为附录补充到了他的论文。
对于图灵来说，这既是个坏消息，也是个好消息。坏消息是，他的结果与丘奇的重复了，对于发表文章来说，这不是什么好事情。好消息是，他的结果与丘奇的重复了，但他对可计算性的定义与丘奇的截然不同，而且两种看似毫无关系的定义，在实质上是相同的，这说明，他们对可计算性的定义，这最初的一步踏出的方向是正确的。一个人提出的定义很可能忽视某个方面，但现在两个截然不同的定义引向相同的结果，在交叉印证下，几无出错之虞。
可以说，图灵的工作面世之日，正是可计算性理论呱呱坠地之时。
也难怪纽曼教授一开始不相信图灵的工作。仅仅二十出头，刚刚踏入科学界的年轻人，就解决了如此重要的问题，而且为一个全新的领域立下了奠基石，这种人，即使在剑桥这个英国顶尖学府，也可谓难得一见。倒不如说，一开始不相信，这才是正常的反应。
但即便不相信，数学证明就是证明。即使纽曼教授并不专精于数理逻辑，还是能看出图灵论文的过人之处。他决定为图灵争取发表的机会。
这并非易事。因为从结论上说，图灵重复了丘奇的结果，所以最初联系的几个期刊的编辑都婉拒了纽曼的要求：他们只看到了论文的结论，没看到论文的精髓。最后，纽曼找到了当时伦敦皇家学会学报的编辑，经过三催四劝，终于说服编辑发表图灵的文章。
《论可计算数，及其在可判定性问题上的应用》，图灵的这篇文章，后来被认为是伦敦皇家学会学报发表过的最重要的文章之一。
万变之宗
乘着远洋货轮，图灵的论文很快传到了大洋彼岸，在普林斯顿掀起了一阵旋风。
在普林斯顿高等研究院的哥德尔，与丘奇有过不少碰面的机会。他读过丘奇的论文，大概也听过丘奇本人介绍他的λ演算。但哥德尔对λ演算一直颇有微词。实际上，作为一种计算模型，λ演算从未得到他的认可。它与人们日常接触到的“计算”毫无相似之处，更像是符号的堆砌和推演。虽然其中的计算的确可以机械性地完成，但要证明这一点绝非易事。事实上，这是一个远非显然的定理，证明也相当复杂。总而言之，λ演算并不像机械的计算，更像智慧的推理。
实际上，哥德尔自己也有一套“机械计算”的模型，那正是他在证明哥德尔不完备性定理时发展出来的递归函数体系。这套体系将“机械计算”定义为递归函数能计算的内容，而递归函数，顾名思义，就是可以用某些递归方式定义的整数函数。但哥德尔对他自己的模型同样不满意，原因同样是他的模型似乎需要太多的聪明才智，不像一台机器。
但图灵的论文瞬间就令哥德尔为之折服。
任何人，只要看一眼图灵机的定义，都会认同图灵机的计算完全是机械演算，完全可以造出一台可以运作的实际的图灵机。而更重要的是，图灵机抓住了“机械计算”的神韵。
机械计算是什么？是机器可以做出的计算。但机器可以千奇百怪，要用三言两语抓住本质，似乎不太可能。那么，何不反其道而行之？与其想像这些机器共有的特性，不如寻找它们共有的限制。
这正是图灵在论文中的做法。他总结了以下几个机器计算的限制：
第一：一台机器只有有限个可以分辨的状态；一台机器能分辨的表示数据的符号只有有限种。
开关或开或合，电路或通或断，中间的变化是跳跃式的。即使是连续的电信号，由于不可避免的热噪声影响，通过测量能分辨出的状态同样只有有限个。虽然现代的计算机看似有无限可能，但这只是幻觉。CPU和内存中的电路，数量虽然庞大无比，但总归是有限的，它们的通断形成的不同状态亦是如此。同理，虽然符号、信号在细节上可以有无数种变化，但由于精度等问题，即使是人，也无法事无巨细将所有细节一一分辨出来，更何况机器。
第二：机器的每一步操作需要的时间有一个下限，而每次操作最多只能读入与改写外部有限个符号。在某次操作读写某处的符号后，下一步机器读写的符号与之前符号的距离应该是有界的。
由于物理的限制，不存在速度无限的物体。无论任何机器，都不能在有限的时间内作出无限次操作，当然也不可能有无限次读入与改写。同样，读写头移动的速度是有限的，所以两次操作读写符号的距离当然也有限制。
第三：在某步操作中，机器的行动完全取决于它当时的内部状态以及读取到的符号。
机器就是机器，它应该做的，就是按照预先规划的图纸一步一步执行。没有异想天开，没有灵光一现，只有照章办事，只有步步为营。
这几个限制看起来相当合理，甚至显得理所当然。但就从如此平平无奇的限制出发，图灵用缜密的逻辑说明了，一台服从这些限制的机器能计算的问题，必定可以用一台特定的图灵机解决。也就是说，任何一台服从这些限制的机器，无论设计如何精巧，构成如何复杂，它的计算能力都不可能超越图灵机，无一例外。
我们甚至可以说，图灵机的设计本身，正是这些限制的一种体现。图灵很可能一开始就意识到了这些限制，再由此出发，去定义他的图灵机。哥德尔之所以对图灵机击节叹赏，大概也正因蕴含在它定义中的，图灵对“机械计算”的深刻洞察。相比之下，虽然与之等价的λ演算也尚算精致，但对于“机械计算”只得其形未得其神，显然逊色不少。
现在，希尔伯特在他的问题中那模糊的“机械计算”，终于有了一个精确的定义：机械计算，就是图灵机能做的计算。这又被称为图灵-丘奇论题，正是可计算性理论的奠基石。
除了λ演算与递归函数以外，还有许多计算系统与图灵机等价。波斯特对应问题，计数器机，马尔可夫算法，甚至元胞自动机，这些计算模型都与图灵机等价。但以我们的后见之明来看，图灵机仍然是机械计算最自然最有用的模型之一。
也正因这篇论文，图灵得到了到普林斯顿读博深造的机会，在丘奇的指导下，得以继续探索可计算性的无限可能。在大洋彼岸等待图灵的，又是可计算性理论的一篇新章。
计算的极限（五）：有限的障壁
难料的世事
美国普林斯顿大学，1936年9月底。
离乡别井，总是一种冒险。即使是一衣带水的英国与美国，文化与传统上的微妙差异，不知制造了多少惶惑。而图灵这时来到普林斯顿，可以说是双重冒险。他刚申请了普林斯顿的奖学金，但却受不了漫长的等待：精英荟萃的普林斯顿实在太诱人了。虽然图灵当时已是剑桥国王学院的研究员，每年有一笔比上不足比下有余的薪金，但人在他乡，经济上需要更多余裕。多申请一笔普林斯顿的奖学金，自然也合乎常理。
但图灵没有拿到这笔奖学金。
在现在看来，这是件不可思议的事：即使是可计算性理论的奠基人，在这笔奖学金上竟然都得不到普林斯顿的青睐。但从当时的情况来看，图灵的遭遇又很合情合理。当时他只是一名小研究员，在学术上名气不大，论文也不多。即使关于图灵机的论文是可计算性理论的奠基石，但脱胎于逻辑的这个领域仍需时间洗练。没有人能参透未来，所以普林斯顿只能从现实角度考虑，而这个考虑的结果，就是拒绝图灵的申请。
但即使没有奖学金，普林斯顿对图灵来说，依然有着相当的吸引力。当时普林斯顿大学数学系与高等研究院共用一幢大楼，可谓人才济济。单在数理逻辑，丘奇自不用提，丘奇的学生克林（Kleene）和罗瑟（Rosser）也是一等一的好手，就连前文反复提到的哥德尔，在一年前访问过普林斯顿，而且计划再次访问。当时在普林斯顿的学者常常开这样的玩笑：如果希望瞻仰数学界的某位领头羊，只要呆在普林斯顿就好，他们总会过来的。人才与人才是相互吸引的，图灵选择冒险，自然有他的理由。
可惜人算不如天算。克林与罗瑟刚刚拿到博士学位，在外校取得了一席教职，已经离开了普林斯顿。哥德尔下一次访问要等到1939年。当时普林斯顿在可计算性理论上能拿得出手的，大概就只有丘奇。丘奇的λ演算在日后同样枝繁叶茂，但那将是本系列的另一个故事。
然而，丘奇的研究方式与图灵格格不入，他追求一切概念的严谨与形式化，甚至到达了难以容忍任何模糊描述的地步。从丘奇和图灵各自提出的可计算性的模型，也能看出二人研究风格的差异。丘奇的λ演算从模型本身的描述开始就充满了一种严谨精确、不可更改的气度，如同数学王国中又一块晶莹璀璨的宝石，可望而不可即；而图灵的图灵机则更为灵动直观，似乎在机械工房中就能找到它的身影，每个人都能明白它的原理。
可以想象这两种迥异的研究风格相遇时必然产生的矛盾。当年二人如何合作研究，在今天剩下的文件中只能窥见一鳞半爪，细节已然遗失于历史的尘埃之中。但从图灵的信件可以推测，他们一开始的合作并不顺利。尽管丘奇为人友善，尽管图灵勤勤恳恳，尽管二人都可以说是数理逻辑领域中的佼佼者，但他们首次合作并没有产生什么成果。当然，数学研究就是这样，失败才是正常情况，甚至可以说，数学研究就是在不断的失败上前进的。
幸而，图灵在数学上的兴趣不仅限于数理逻辑。从冯·诺依曼听来的一个有关群论的问题引起了图灵的兴趣，他很快就解决了这个问题，令冯·诺依曼对他大加青眼。也幸亏有了这个群论问题，图灵在普林斯顿的第一年不算颗粒无收。
但图灵最希望做的，还是有关数理逻辑的问题，他希望继续留在普林斯顿，跟随丘奇继续研究，虽然剑桥也有着强烈的吸引力。在再三的劝说后，他又申请了第二年的奖学金。这次，因为有冯·诺依曼的保荐，结果毫无悬念。
值得玩味的是，冯·诺依曼的信中只字未提图灵在数理逻辑方面的成就。但以后见之明看来，图灵在可计算性理论上的工作，远远比他在群论上的工作意义重大而深远。此中对比，意味深长。然而我们不能说奖学金的管理者做错了什么，只能说他们错失了一段佳话。
图灵在普林斯顿的生活踏入第二年。作为博士导师的丘奇，向图灵提出了一个新的题目：探求超越哥德尔不完备性定理的方法。
图灵再次抓住了这个机遇。
来源: 科学松鼠会