康托对角线
此为搬运好文，原文地址：对角线方法之后的故事 | Matrix67: The Aha Moments
对角线方法之后的故事
同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：
事实上，实数区间 (0, 1) 就已经是一个不可数的集合了。换句话说，你绝不可能用“第一个数是某某某，第二个数是某某某”的方式把 0 到 1 之间的所有实数一个不漏地列举出来。我们大致的证明思路是，假设你把实数区间 (0, 1) 里的所有数按照某种顺序排列起来，那么我总能找到至少一个 0 到 1 之间的实数，它不在你的列表里，从而说明你的列表并不全。把你的列表上的数全写成 0 到 1 之间的无限小数（如果是有限小数，可以在其后面添加数字 0 ，把它变成无限小数）：
那么我就构造这么一个小数，小数点后第一位不等于 a1 的第一位，小数点后第二位不等于 a2 的第二位，总之小数点后第 i 位不等于 ai 的第 i 位。这个数属于实数区间 (0, 1) ，但它显然不在你的列表里，因为它和你列表里的每一个数都有至少一位是不同的。这样，我们就证明了实数区间是不可数的。
这就是传说中的“对角线方法”。第一次看到这个对角线方法的证明之后，想必所有人都会拍案叫绝，大呼巧妙。但是，冷静下来思考一下，你会发现对角线方法里面还有不少值得注意的问题。一个经典的问题就是，上述证明究竟在什么地方用到了“实数区间”这个条件？为什么同样的方法不能用来证明 0 到 1 之间的有理数是不可数的呢？我当然可以把 0 到 1 之间的全体有理数都写成无限小数，也可以假设它们已经排列成了 a1, a2, a3, …
我当然也可以像刚才那样，用对角线方法取出一个不在列表里的数，从而说明有理数是不可数的。这个“证明”错在哪儿呢？它错在，最后用对角线方法取得的数不保证是一个有理数，因此如果它不在上述列表中，并不会对“有理数是可数的”这一结论造成威胁。下面，我会给出一个更隐蔽的误用对角线方法的例子，你还能看出问题出在哪里吗？
对于某个实数，如果存在一个算法，它能给出该实数小数点后任意多位的数字，我们就把这个实数叫做“可计算数”。说得更简单一些，可计算数就是那些能够编写程序打印出来的数。因此，不但所有整数、有理数都是可计算数，所有代数数也都是可计算数，事实上很多超越数（比如 π 和 e ）也都是可计算数。但是注意到，所有可能的程序代码的数量是可数的，因为我们能够按照代码长度从小到大把它们一一列举出来（代码长度相等时可以按字典序排序）。因而，所有的可计算数也是可数的，它只占全体实数中很小很小的一部分。
不过，利用对角线方法，我们能够“证明”一个完全相反的结论：可计算数是不可数的。
同样地，我们只考虑 (0, 1) 区间内的可计算数。我们首先把所有的可计算数列成一张表，然后利用对角线方法，找出一个与列表中任意一个数都不相等的数。问题的关键就是，这个数本身是可计算数吗？仔细一想，还真是！由于每一个 ai 本身都是可计算的，因此我们可以在有限的时间里得到它的第 i 位数。我们再把“不同于第 i 位数字”的含义规定死，严格按照 0→1, 1→2, …, 8→9, 9→0 的规则选取相异的数字。 现在，让 i 从 1 开始递增，我们便能依次找出 a1 的第一位， a2 的第二位， a3 的第三位等等，每找到一个新的数字，便按照规则输出一个不同的数字。因而，这个数显然是可计算的。但是，这个可计算数却不在列表里，说明你的列表并不全。 Tada ，可计算数是不可数的。
这个证明错在哪里呢？这个证明错在，我们一开始就凭空假设了一个可计算数列表，这个列表的生成规则是不透明的。这本来没啥（事实上我们在证明实数不可数时也是这么做的），但关键是，如果这个列表本身并不是通过某种方式计算出来的，最后用对角线法得到的数也就不是可计算的。那么，如果我们修改一下证明，事先给定一种生成可计算数列表的方案呢？麻烦就麻烦在这里：可计算数确实是可数的，确实能够一个一个地列举出来，但我们不见得能找出一个具体的列举算法。大家或许会奇怪，我们先依次列举出所有可能的程序代码，然后划掉那些不合法的代码，不就列出了所有的可计算数吗？问题就出在，我们不能有效地判断哪些代码是不合法的。这里“不合法的代码”含义很多，它有可能是根本无法正确编译的代码，也有可能是将会输出非数字字符的代码，还有可能是在某一步之后陷入死循环永远输不出下一个数字的程序代码。后面两个问题显然很难办，因为你不知道程序运行后将在什么地方开始就不合法了，也无法知道程序迟迟没能输出下一位数是因为真的遇到死循环了还是只需要再等一等。因此，仅用模拟运行的方法，我们无法在有限的时间里判断代码的合法性。有没有可能不模拟运行代码，依靠某种方法提前“预知”一段代码是否是合法的呢？在 1936 年的一篇著名论文中， Turing 证明了，这在理论上就是不可行的，再牛的算法，再牛的程序员也不能做到。这个结论可以重新叙述为，不存在这样的一个算法，它能判断一段代码运行之后究竟是会无限地运行下去，还是最终会在某一时刻停止下来。后来，人们就把它叫做“停机问题”。
了解停机问题的朋友可能会惊呼，这简直是引入停机问题的一个绝佳切入口啊！事实上， Turing 在那篇著名的论文中，就是这样引入停机问题的。注意，如果“预知代码运行结果”的算法真的存在，我们就会得出“可计算数是不可数的”这么一个荒谬的结论，这已经证明了这种算法是不存在的。不过，为了让证明更具说服力， Turing 还给出了一些更具体的分析（警告：下文非常绕人，小心走火入魔）。
如果我们真的发明了这样一种判断代码合法性的算法，那么我们就能编写出一个这样的程序，它将自动枚举所有可能的并且合法的代码，同时模拟运行这些代码（这是可以实现的，事实上 Turing 在论文中已经给出了在一个程序内部模拟另一个程序的方法，用现在的话说就相当于是用 C 语言写了一个 C 语言解释器），找出第 i 个代码将会输出的第 i 个数字，然后自己输出一个和它不同的数字。可见，这个程序本身是合法的，因为它模拟运行的都是合法的代码，不会被卡死，同时它也只会输出数字，不会输出别的东西。因此，这个程序代码本身也在合法代码的列表里。不妨假设它是第 n 个合法的代码吧。现在，运行这个程序，这个程序便会开始枚举所有合法的代码。总有一个时候，这个程序将会枚举到第 n 个代码，也就是这个程序本身的代码。这个程序将会模拟运行这个程序本身，试图找出它将输出的第 n 位数字是什么，然后输出一个与之不同的数。你会发现，此时矛盾已经出现了：它怎么能在第 n 位输出一个不同于它在第 n 位应该输出的数呢？
而实际情况则更有意思：这个程序永远卡在这里了。当这个程序遇到第 n 个代码（也就是它本身）时，这个程序将会模拟它本身的运行。这个程序将会模拟它本身模拟前 n – 1 个程序的代码，找出它本身在前 n – 1 位输出了什么。然后这个程序将会模拟它本身模拟第 n 个代码。于是，这个程序将会模拟它本身模拟它本身又一次模拟之前的代码，并再次遇到自己的代码⋯⋯你会发现，这个程序将会陷入一个死循环，这与它本身是合法程序相矛盾。 Turing 用这种方法证明了，预知代码的行为是永远不可能实现的。
集合论、可数集、不可数集、可计算数、不可计算数、对角线方法、Turing 机、停机问题、 Chaitin 常数、 Kolmogorov 复杂度、数理逻辑、 Gödel 不完备定理⋯⋯这是一个异常庞大的话题，它们之间彼此联系，形成一张巨大的网。似乎目前还没有一条漂亮的线索能够将这张网一次性地呈现出来，我们一次只能看到这张网的其中一角。这篇文章是我在读《The Annotated Turing》时看到的和想到的一些东西，如果你对这个话题感兴趣，我的 Blog 里还有一些类似的文章：
可数集与不可数集的介绍：http://www.matrix67.com/blog/archives/416
以及一些扩展：http://www.matrix67.com/blog/archives/2172
停机问题的介绍：http://www.matrix67.com/blog/archives/55
Chaitin 常数：http://www.matrix67.com/blog/archives/901
Chaitin 定理：http://www.matrix67.com/blog/archives/1392
刘未鹏大牛的两篇文章明显比我写得更好（标题也比我写的都帅多了）：
图灵机杂思 http://blog.csdn.net/pongba/article/details/621723
康托尔、哥德尔、图灵——永恒的金色对角线 http://mindhacks.cn/?p=13
当然，《GEB》和《皇帝的新脑》也是两本不得不看的奇书。
