2011-12-07 16:35| 
37 Comments | 本文内容遵从同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：
事实上，实数区间 (0, 1) 就已经是一个不可数的集合了。换句话说，你绝不可能用“第一个数是某某某，第二个数是某某某”的方式把 0 到 1 之间的所有实数一个不漏地列举出来。我们大致的证明思路是，假设你把实数区间 (0, 1) 里的所有数按照某种顺序排列起来，那么我总能找到至少一个 0 到 1 之间的实数，它不在你的列表里，从而说明你的列表并不全。把你的列表上的数全写成 0 到 1 之间的无限小数（如果是有限小数，可以在其后面添加数字 0 ，把它变成无限小数）：
a1 = 0.0147574628...
a2 = 0.3721111111...
a3 = 0.2323232323...
a4 = 0.0004838211...
a5 = 0.0516000000...
.........
那么我就构造这么一个小数，小数点后第一位不等于 a1 的第一位，小数点后第二位不等于 a2 的第二位，总之小数点后第 i 位不等于 ai 的第 i 位。这个数属于实数区间 (0, 1) ，但它显然不在你的列表里，因为它和你列表里的每一个数都有至少一位是不同的。这样，我们就证明了实数区间是不可数的。
这就是传说中的“对角线方法”。第一次看到这个对角线方法的证明之后，想必所有人都会拍案叫绝，大呼巧妙。但是，冷静下来思考一下，你会发现对角线方法里面还有不少值得注意的问题。一个经典的问题就是，上述证明究竟在什么地方用到了“实数区间”这个条件？为什么同样的方法不能用来证明 0 到 1 之间的有理数是不可数的呢？我当然可以把 0 到 1 之间的全体有理数都写成无限小数，也可以假设它们已经排列成了 a1, a2, a3, …
a1 = 0.1111111111...
a2 = 0.3267676767...
a3 = 0.5302000000...
a4 = 0.0439439439...
a5 = 0.1126000000...
.........
我当然也可以像刚才那样，用对角线方法取出一个不在列表里的数，从而说明有理数是不可数的。这个“证明”错在哪儿呢？它错在，最后用对角线方法取得的数不保证是一个有理数，因此如果它不在上述列表中，并不会对“有理数是可数的”这一结论造成威胁。下面，我会给出一个更隐蔽的误用对角线方法的例子，你还能看出问题出在哪里吗？
对于某个实数，如果存在一个算法，它能给出该实数小数点后任意多位的数字，我们就把这个实数叫做“可计算数”。说得更简单一些，可计算数就是那些能够编写程序打印出来的数。因此，不但所有整数、有理数都是可计算数，所有代数数也都是可计算数，事实上很多超越数（比如 π 和 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》和《皇帝的新脑》也是两本不得不看的奇书。
用得到“可计算数”这个概念的人应该都可以马上发现问题。。
翻来覆去还是那点事啊
抢板凳。。
好文！大赞！
前排！
挺长的牛文～
前排慢慢看～
= =前排
最后那绕人的话再绕几次看看
想起P=NP？啊！！
最后一段。。看的我小激动了。。
这个证明错在最开始的地方：其实我们没有办法把可计算数列成一张表。
---------------------------------------------------------
把上面的"可计算数"换成"实数",那么用对角线法证明实数不可数岂不也是错的?
回复：你说得对，我这里写得确实不好。已经做了一些修改。
我觉得那个对角线证明错在，构造出来的，不在列表中的那个数，不是由有限长度的程序生成的。
看到停机问题就知道又入坑了……这种各领域问题之间的暗地关联性一直很吸引我……当初谁能想到分数维度的图形这种看起来颇抽象的东西能够广泛地描述自然界很多构造呢……当初谁又能想到离散的干涉条纹却恰恰验证了光波的连续性呢……
对角线对应的实数是属于（0,1）区间的实数就是实质性地利用了（0,1）区间这个条件。
回來看看。
另外对角线法证明的实际是非负整数的无限序列的集合是不可数的。这个集合恰好和01区间存在一一对应。对角线法证明和01区间的拓扑结构没有关系，别混淆了。
有意思。“这个证明错在，我们一开始就凭空假设了一个可计算数列表，但这个列表的生成规则是不透明的”。既然把可计算数一个接一个列出来的规则不透明，那把实数一个接一个列出来的规则同样不透明，就都不能用对角线法了。我觉得严谨的证明是用|2^A|>|A|这个定理及其证明，证明(0,1)中的实数与自然数的子集（即幂集的元素）一一对应。
看了文章，对原以为清晰的概念犯迷糊了：“可数”、“可列表”、“与自然数集等势”是完全等价的概念吗？
这个问题应该是想说是对于一些问题我们只能给出存在性证明,但无法给出构造性证明(无法举出实例).至于本题的列表属不属于这个范畴,我不知道
但本题的证明逻辑是不严谨的,它只是给出了一种对列表进行构造的方法(程序排序法),然后证明这种方法是不成立的(停机问题),但却试图由此推出任何构造方法都不成立,这个逻辑不对
对角线法用到的序列可以看成是自然数集合到｛0， 1， 2， 3， 4， 5， 6， 7， 8， 9｝的映射。全体这样的映射构成一个集合，这个集合与自然数不等势。
想当年上大学时候，离散数学的第一节课学的就是这个，当时确实很震撼。
关于停机问题罗杰·彭罗斯的《皇帝新脑》里有个直接用对角线法的证明有点意思
Everyone can change this page!
这玩意到底是干什么用的...
求答复。
对角线法可以得出一个数，和任何已知的数“表示”不同，但是表示不同不等于值不同，比如1=0.9999....那么，对角线法真的正确吗？
17L:程序的数量是可数的，可计算数当然也是可数的，重点不在这
22L:原证明直接给出一种偷懒的方法：不要选择0和9，就是说，每次选择一个和0，9，当前数的当前位都不同的数字
17L:程序的数量是可数的，可计算数当然也是可数的，重点不在这
22L:原证明直接给出一种偷懒的方法：不要选择0和9，就是说，每次选择一个和0，9，当前数的当前位都不同的数字
orz
其实感觉刘未鹏最后那段不怎么靠谱。。集合不能枚举吧。。
@yh
这个方法好像不太靠谱，任何进制应该是等价的，如果用2进制，那么如何不选呢？
@yh
这个方法好像有问题，任何进制应该是等价的，如果用2进制，那么如何不选呢？
但是不能保证一段代码只能给出一个数吧，如果认为执行一个死循环的次数是可数的，那么递归一个死循环让复杂度变成2^可数就是不可数的，这样用一段代码执行不可数次也是可能的，如何保证一段代码不会得到不可数个可计算数呢？
上面关于那个执行不可数次的例子有问题，应该改成，一个无穷进行下去的递归，每次有两个分支，不过这个在实际上是应该做不到的
上面那个做法有问题，应该改成一个有两个分支的无穷进行下去的递归。
题目所指的可计算数是由有限长度程序生成的，而用对角线法构造的那个数所对应之程序是无限长的，因此不在题目所指的程序集合内，没有矛盾。
显然无限长程序的集合的范数等于实数集的范数，所以其对应可计算数集合的范数等于实数集的范数。
把对角线方法中的小数点全部去掉，不就是证明正整数不可数了吗……
在一本叫做从1到无穷大的书里看到过
"但是注意到，所有可能的程序代码的数量是可数的，因为我们能够按照代码长度从小到大把它们一一列举出来（代码长度相等时可以按字典序排序）。因而，所有的可计算数也是可数的，它只占全体实数中很小很小的一部分。"
为什么程序代码的数量是可数的，所以可计算数也是可数的？一个实数不能由无限种程序来打印吗？
写得不错，很有意思。
在“可计算数是不可数的”的“证明”中，首先就给出了一张有无穷多个“可计算数”的表，然后根据这张无穷表来构造一个不在该表中的元素，这个构造过程会终止吗?如果不会终止，那么这个所谓的“不在该表中的元素”也就不是可计算的数了，也就不存在矛盾，从而该“证明”就自然地是无效的了。
因为不懂音乐，geb看了一点就放弃了