上接《哥德尔不完备定理》 4. 大道至简 —— 康托尔的天才 “ 大道至简 ” 这个名词或许更多出现在文学和哲学里面，一般用在一些模模糊糊玄玄乎乎的哲学观点上。然而，用在这里，数学上，这个名词才终于适得其所。大道至简，看上去最复杂的理论其实建立在一个最简单最纯粹的道理之上。 康托尔在无穷集合和超限数方面的工作主要集中在两篇突破性的论文上，这也是我所见过的最纯粹最美妙的数学论文，现代的数学理论充斥了太多复杂的符号和概念，很多时候让人看不到最本质的东西，当然，不否认这些东西很多也是有用的，然而，要领悟真正的数学美，像集合论和数论这种纯粹的东西，真的非常适合。不过这里就不过多谈论数学的细节了，只说康托尔引入对角线方法的动机和什么是对角线方法。 4.1. 神奇的一一对应 康托尔在研究无穷集合的时候，富有洞察性地看到了对于无穷集合的大小问题，我们不能再使用直观的 “ 所含元素的个数 ” 来描述，于是他创造性地将一一对应引入进来，两个无穷集合 “ 大小 ” 一样当且仅当它们的元素之间能够构成一一对应。这是一个非常直观的概念，一一对应嘛，当然个数相等了，是不是呢？然而这同时就是它不直观的地方了。对于无穷集合，我们日常的所谓 “ 个数 ” 的概念不管用了，因为无穷集合里面的元素个数本就是无穷多个。不信我们来看一个小小的例子。我们说自然数集合能够跟偶数集合构成一一对应，从而自然数集合跟偶数集合里面元素 “ 个数 ” 是一样多的 。怎么可能？偶数集合是自然数集合的真子集，所有偶数都是自然数，但自然数里面还包含奇数呢，说起来应该是二倍的关系不是？不是！我们只要这样来构造一一对应： 1 2 3 4 … 2 4 6 8 … 用函数来描述就是 f(n) = 2n 。检验一下是不是一一对应的？不可思议对吗？还有更不可思议的，自然数集是跟有理数集一一对应的！对应函数的构造就留给你解决吧，提示，按如下方式来挨个数所有的有理数： 1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1 … 用这种一一对应的手法还可以得到很多惊人的结论，如一条直线上所有的点跟一个平面上所有的点构成一一对应（也就是说复数集合跟实数集合构成一一对应）。以致于连康托尔自己都不敢相信自己的眼睛了，这也就是为什么他在给戴得金的信中会说 “ 我看到了它，却不敢相信它 ” 的原因。 然而，除了一一对应之外，还有没有不能构成一一对应的两个无穷集合呢？有。实数集合就比自然数集合要 “ 大 ” ，它们之间实际上无法构成一一对应。这就是康托尔的对角线方法要解决的问题。 实数集和自然数集无法构成一一对应？！ 我们只需将实数的小数位展开，并且我们假设实数集能够与自然数集一一对应，也就是说假设实数集 可列 ，所以我们把它们与自然数一一对应列出，如下： 1 a 10 .a11a12a13… 2 a 20 .a21a22a23… 3 a 30 .a31a32a33… 4 … 5 … （注： aij 里面的 ij 是下标 ） 现在，我们构造一个新的实数，它的第 i 位小数不等于 aii 。也就是说，它跟上面列出的每一个实数都至少有一个对应的小数位不等，也就是说它不等于我们上面列出的所有实数，这跟我们上面假设已经列出了所有实数的说法相矛盾。所以实数集只能是不可列的，即不可与自然数集一一对应！这是对角线方法的最简单应用。 4.2. 对角线方法 —— 停机问题的深刻含义 对角线方法有很多非常奇妙的结论。其中之一就是文章一开始提到的停机问题。我想绝大多数人刚接触停机问题的时候都有一个问题，图灵怎么能够想到这么诡异的证明，怎么能构造出那个诡异的 “ 说停机又不停机，说不停机又停机 ” 的悖论机器。马上我们就会看到，这其实只是对角线方法的一个直接结论。 还是从反证开始，我们假设存在这样一个图灵机，他能够判断任何程序在任何输入上是否停机。由于所有图灵机构成的集合是一个可列集（也就是说，我们可以逐一列出所有的图灵机，严格证明见我以前的一篇文章《 图灵机杂思 》），所以我们可以很自然地列出下表，它表示每个图灵机分别在每一个可能的输入（ 1,2,3,… ）下的输出， N 表示无法停机，其余数值则表示停机后的输出： 1 2 3 4 … M1 N 1 N N … M2 2 0 N 0 … M3 0 1 2 0 … M4 N 0 5 N … … M1 ， M2 ， M3 … 是逐一列出的图灵机，并且，注意，由于程序即数据，每个图灵机都有唯一编码，所以我们规定在枚举图灵机的时候 Mi 其实就代表编码为 i 的图灵机，当然这里很多图灵机将会是根本没用的玩意，但这不要紧。此外，最上面的一行 1 2 3 4 … 是输入数据，如，矩阵的第一行代表 M1 分别在 1 ， 2 ， 3 ， … 上面的输出，不停机的话就是 N 。 我们刚才假设存在这样一个图灵机 H ，它能够判断任何程序在任何输入上能否停机，换句话说， H(i,j) （ i 是 Mi 的编码）能够给出 “Mi(j)” 是 N （不停）呢还是给出一个具体的结果（停）。 我们现在来运用康托尔的对角线方法，我们构造一个新的图灵机 P ， P 在 1 上的输出行为跟 M1(1)“ 不一样 ” ，在 2 上的输出行为跟 M2(2)“ 不一样 ” ， … 总之 P 在输入 i 上的输出跟 Mi(i) 不一样。只需利用一下我们万能的 H ，这个图灵机 P 就不难构造出来，如下： P(i): if( H(i, i) == 1 ) then // Mi(i) halts return 1 + Mi(i) else // if H(i, i) == 0 (Mi(i) doesn’t halt) return 0 也就是说，如果 Mi(i) 停机，那么 P(i) 的输出就是 Mi(i)+1 ，如果 Mi(i) 不停机的话， P(i) 就停机且输出 0 。这就保证了 P(i) 的输出行为跟 Mi(i) 反正不一样。现在，我们注意到 P 本身是一个图灵机，而我们上面已经列出了所有的图灵机，所以必然存在一个 k ，使得 Mk = P 。而两个图灵机相等当且仅当它们对于所有的输入都相等，也就是说对于任取的 n ，有 Mk(n) = P(n) ，现在令 n=k ，得到 Mk(k)=P(k) ，根据上面给出的 P 的定义，这实际上就是： Mk(k) = P(k) = 1+Mk(k) if Mk(k) halts 0 if Mk(k) doesn’t halt 看到这个式子里蕴含的矛盾了吗？如果 Mk(k) 停机，那么 Mk(k)=1+Mk(k) ；如果 Mk(k) 不停机，则 Mk(k)=0 （给出结果 0 即意味着 Mk(k) 停机）；不管哪种情况都是矛盾。于是我们得出，不存在那样的 H 。 这个对角线方法实际上说明了，无论多聪明的 H ，总存在一个图灵机的停机行为是它无法判断的。这跟哥德尔定理 “ 无论多 ‘ 完备 ’ 的形式化公理系统，都存在一个 ‘ 哥德尔命题 ’ 是无法在系统内推导出来的 ” 从本质上其实是一模一样的。只不过我们一般把图灵的停机问题称为 “ 可判定问题 ” ，而把数学的称为 “ 可证明问题 ” 。 等等！如果我们把那个无法判定是否停机的图灵机作为算法的特例纳入到我们的 H 当中呢？我们把得到的新的判定算法记为 H1 。然而，可惜的是，在 H1 下，我们又可以相应地以同样的手法从 H1 构造出一个无法被它（ H1 ）判定的图灵机来。你再加，我再构造，无论你加多少个特例进去，我都可以由同样的方式构造出来一个你无法够到的图灵机，以彼之矛，攻彼之盾。其实这也是哥德尔定理最深刻的结论之一，哥德尔定理其实就说明了无论你给出多少个公理，即无论你建立多么完备的公理体系，这个系统里面都有由你的那些公理出发所推导不到的地方，这些黑暗的角落，就是人类直觉之光才能照射到的地方！ 本节我们从对角线方法证明了图灵的停机问题，我们看到，对角线方法能够揭示出某种自指结构，从而构造出一个 “ 悖论图灵机 ” 。实际上，对角线方法是一种有深远影响的方法，哥德尔的证明其实也是这个方法的一则应用。证明与上面的停机问题证明如出一辙，只不过把 Mi 换成了一个形式系统内的公式 fi ，具体的证明就留给聪明的你吧 :) 我们现在来简单的看一下这个奇妙方法的几个不那么明显的推论。 4.3. 罗素悖论 学过逻辑的人大约肯定是知道著名的罗素悖论的，罗素悖论用数学的形式来描述就是： R = {X:X 不属于 X}; 这个悖论最初是从康托尔的无穷集合论里面引申出来的。当初康托尔在思考无穷集合的时候发现可以称 “ 一切集合的集合 ” ，这样一个集合由于它本身也是一个集合，所以它就属于它自身。也就是说，我们现在可以称世界上存在一类属于自己的集合，除此之外当然就是不属于自己的集合了。而我们把所有不属于自己的集合收集起来做成一个集合 R ，这就是上面这个著名的罗素悖论了。 我们来看 R 是否属于 R ，如果 R 属于 R ，根据 R 的定义， R 就不应该属于 R 。而如果 R 不属于 R ，则再次根据 R 的定义， R 就应该属于 R 。 这个悖论促使了集合论的公理化。后来策梅罗公理化的集合论里面就不允许 X 属于 X （不过可惜的是，尽管如此还是没法证明这样的集合论不可能产生出新的悖论。而且永远没法证明 —— 这就是哥德尔第二不完备性定理的结论 —— 一个包含了 PA 的形式化公理系统永远无法在内部证明其自身的一致（无矛盾）性。从而希尔伯特想从元数学推出所有数学系统的一致性的企图也就失败了，因为元数学的一致性又得由元元数学来证明，后者的一致性又得由元元元数学来证明 … ）。 这里我们只关心罗素是如何想出这个绝妙的悖论的。还是对角线方法！我们罗列出所有的集合， S1,S2,S3 … S1 S2 S3 … S1 0 1 1 … S2 1 1 0 … S3 0 0 0 … … … 右侧纵向列出所有集合，顶行横向列出所有集合。 0/1 矩阵的 (i,j) 处的元素表示 Si 是否包含 Sj ，记为 Si(j) 。现在我们只需构造一个新的 0/1 序列 L ，它的第 i 位与矩阵的 (i,i) 处的值恰恰相反： L(i) = 1-Si(i) 。我们看到，这个新的序列其实对应了一个集合，不妨也记为 L ， L(i) 表示 L 是否包含 Si 。根据 L 的定义，如果矩阵的 (i,i) 处值为 0 （也就是说，如果 Si 不包含 Si ），那么 L 这个集合就包含 Si, 否则就不包含。我们注意到这个新的集合 L 肯定等于某个 Sk （因为我们已经列出了所有的集合）， L = Sk 。既然 L 与 Sk 是同一集合，那么它们肯定包含同样的元素，从而对于任意 n ，有 L(n) = Sk(n) 。于是通过令 n=k ，得到 L(k) = Sk(k) ，而根据 L 的定义， L(k) = 1- Sk(k) 。这就有 Sk(k) = 1-Sk(k) ，矛盾。 通过抽象简化以上过程，我们看到，我们构造的 L 其实是 “ 包含了所有不包含它自身的集合的集合 ” ，用数学的描述正是罗素悖论！ 敏锐的你可能会注意到所有集合的数目是不可数的从而根本不能 S1,S2… 的一一列举出来。没错，但通过假设它们可以列举出来，我们发现了一个与可列性无关的悖论。所以这里的对角线方法其实可以说是一种启发式方法。 同样的手法也可以用到证明 P(A) （ A 的所有子集构成的集合，也叫幂集）无法跟 A 构成一一对应上面。证明就留给聪明的你了 :) 4.4. 希尔伯特第十问题结出的硕果 希尔伯特是在 1900 年巴黎数学家大会上提出著名的希尔伯特第十问题的，简言之就是是否存在一个算法，能够计算任意 丢番图方程 是否有整根 。要解决这个问题，就得先严格定义 “ 算法 ” 这一概念。为此图灵和丘齐分别提出了图灵机和 lambda calculus 这两个概念，它们从不同的角度抽象出了 “ 有效（机械）计算 ” 的概念，著名的 图灵——丘齐命题 就是说所有可以有效计算出来的问题都可以由图灵机计算出来。实际上我们已经看到，丘齐的 lambda calculus 其实就是数学推理系统的一个形式化。而图灵机则是把这个数学概念物理化了。而也正因为图灵机的概念隐含了实际的物理实现，所以冯 · 诺依曼才据此提出了奠定现代计算机体系结构的 冯·诺依曼体系结构 ，其遵循的，正是图灵机的概念。而 “ 程序即数据 ” 的理念，这个发端于数学家哥德尔的不完备性定理的证明之中的理念，则早就在黑暗中预示了可编程机器的必然问世。 4.5. 对角线方法 —— 回顾 我们看到了对角线方法是如何简洁而深刻地揭示出自指或递归结构的。我们看到了著名的不完备性定理、停机问题、 Y Combinator 、罗素悖论等等等等如何通过这一简洁优美的方法推导出来。这一诞生于康托尔的天才的手法如同一条金色的丝线，把位于不同年代的伟大发现串联了起来，并且将一直延续下去 … P.S 1 . lambda calculus 里面的 “ 停机问题 ” 实际上 lambda calculus 里面也是有 “ 停机问题 ” 的等价版本的。其描述就是：不存在一个算法能够判定任意两个 lambda 函数是否等价。所谓等价当然是对于所有的 n, 有 f(n)=g(n) 了。这个问题的证明更加能够体现对角线方法的运用。仍然留给你吧。 2 . 负喧琐话 ( http://blog.csdn.net/g9yuayon) 是个非常不错的 blog:) 。 g9 的文字轻松幽默，而且有很多名人八卦可以养眼，真的灰常 … 灰常 … 不错哦。此外 g9 老兄还是个理论功底非常扎实的牛。所以， anyway ，看了他的 blog 就知道啦！最初这篇文章的动机也正是看了上面的一篇 关于Y Combinator的铸造过程的介绍 ，于是想揭示一些更深的东西，于是便有了本文。 3. 文章起名《康托尔、哥德尔、图灵 —— 永恒的金色对角线》其实是为了纪念看过的一本好书 GEB ，即《 Godel 、 Escher 、 Bach-An Eternal Golden Braid 》中文译名《哥德尔、埃舍尔、巴赫 —— 集异璧之大成》 —— 商务印书馆出版。对于一本定价 50 元居然能够在 douban 上卖到 100 元的二手旧书，我想无需多说。另，幸福的是，电子版可以找到 :) 4 . 其实很久前想写的是一篇《从哥德尔到图灵》，但那篇写到 1/3 不到就搁下了，一是由于事务，二是总觉得少点什么。呵呵，如今把康托尔扯进来，也算是完成当时扔掉的那一篇吧。 5. 这恐怕算是写得最曲折的一篇文章了。不仅自己被这些问题搞得有点晕头转向（还好总算走出来），更因为要把这些东西自然而然的串起来，也颇费周章。很多时候是利用吃饭睡觉前或走路的时间思考本质的问题以及如何表达等等，然后到纸上一气呵成。不过同时也锻炼了不拿纸笔思考数学的能力，呵呵。 6. 关于图灵的停机问题、 Y Combinator 、哥德尔的不完备性定理以及其它种种与康托尔的对角线之间的本质联系，几乎查不到完整系统的深入介绍，一些书甚至如《 The Emperor’s New Mind 》也只是介绍了与图灵停机问题之间的联系（已经非常的难得了）， google 和 baidu 的结果也是基本没有头绪。很多地方都是一带而过让人干着急。所以看到很多地方介绍这些定理和构造的时候都是弄得人晕头转向的，绝大部分人在面对如 Y Combinator 、不完备性定理、停机问题的时候都把注意力放在力图理解它是怎么运作的上面了，却使人看不到其本质上从何而来，于是人们便对这些东东大为惊叹。这使我感到很不痛快，如隔靴搔痒般。这也是写这篇文章的主要动机之一。 Reference [1] 《数学——确定性的丧失》 [2] 也有观点认为函数式编程语言之所以没有广泛流行起来是因为一些实际的商业因素。 [3] Douglas R.Hofstadter的著作《Godel, Escher, Bach: An Eternal Golden Braid》（《哥德尔、艾舍尔、巴赫——集异璧之大成》）就是围绕这一思想写出的一本奇书。非常建议一读。 [4] 《数学——确定性的丧失》 [5] 虽然我觉得那个系徽做得太复杂，要表达这一简洁优美的思想其实还能有更好的方式。 [6] 关于如何在lambda calculus系统里实现“+”操作符以及自然数等等，可参见 这里， 这里，和 这里。 [7] g9的blog（负暄琐话） http://blog.csdn.net/g9yuayon/ 上有一系列介绍lambda calculus的文章（当然，还有其它好文章:)），非常不错，强烈推荐。最近的两篇就是介绍Y combinator的。其中有一篇以javaScript语言描述了迭代式逐步抽象出Y Combinator的过程。 [8] 实际上这只是第一不完备性定理，它还有一个推论，被称为第二不完备性定理，说的是任一个系统T内无法证明这个系统本身的一致性。这个定理的证明核心思想如下：我们前面证明第一不完备性定理的时候用的推断其实就表明 Con/T -> G(g) （自然语言描述就是，由系统T的无矛盾，可以推出G(g)成立），而这个“Con/T -> G(g)”本身又是可以在T内表达且证明出来的（具体怎么表达就不再多说了）——只需要用排中律即可。于是我们立即得到，T里面无法推出Con/T，因为一旦推出Con/T就立即推出G(g)从而推出UnPr(G(g))，这就矛盾了。所以，Con/T无法在T内推出（证明）。 |
