康托尔、哥德尔、图灵——永恒的金色对角线.pdf

康托尔、哥德尔、图灵——永恒的金色对角 线 来自C++罗浮宫 ，作者 ：刘未鹏 [1] 我看到了它，却不敢相信它 。 ——康托尔 计算机是数学家一次失败思考的产物。 ——无名氏 哥德尔的不完备性定理震撼了20世纪数学界的天空 ，其数学意义颠覆了希尔伯特的形式化数学的 宏伟计划 ，其哲学意义直到21世纪的今天仍然不断被延伸到各个自然学科 ，深刻影响着人们的思 维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型 ，进而作出了可计算理论和现代 计算机的奠基性工作 ，著名的停机问题给出了机械计算模型的能力极限，其深刻的意义和漂亮的 证明使它成为可计算理论中的标志性定理之一。丘齐 ，跟图灵同时代的天才 ，则从另一个抽象角 度提出了lambda算子的思想 ，与图灵机抽象的倾向于硬件性不同，丘齐的lambda算子理论是从数 学的角度进行抽象 ，不关心运算的机械过程而只关心运算的抽象性质 ，只用最简洁的几条公理便 建立起了与图灵机完全等价的计算模型 ，其体现出来的数学抽象美开出了函数式编程语言这朵奇 葩 ，Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学 界 ，虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主 [2] 流的编程语言 ，然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函 数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中… 然而 ，这一切的一切 ，看似不很相关却又有点相关 ，认真思考其关系却又有点一头雾水的背后 ， 其实隐隐藏着一条线 ，这条线把它们从本质上串到了一起 ，而顺着时光的河流逆流而上 ，我们将 会看到 ，这条线的尽头 ，不是别人 ，正是只手拨开被不严密性问题困扰的19世纪数学界阴沉天空 的天才数学家康托尔 ，康托尔创造性地将一一对应和对角线方法运用到无穷集合理论的建立当中 ，这个被希尔伯特称为“谁也无法将我们从康托尔为我们创造的乐园中驱逐出去”、被罗素称为 “19世纪最伟大的智者之一”的人 ，他在集合论方面的工作终于驱散了不严密性问题带来的阴霾 ， 仿佛一道金色的阳光刺破乌云 ，19世纪的数学终于看到了真正严格化的曙光 ，数学终于得以站在 了前所未有的坚固的基础之上 ；集合论至今仍是数学里最基础和最重要的理论之一。而康托尔当 初在研究无穷集合时最具天才的方法之一——对角线方法——则带来了极其深远的影响 ，其纯粹 [3] 而直指事物本质的思想如洪钟大吕般响彻数学和哲学的每一个角落 。随着本文的展开 ，你将会看 到 ，刚才提到的一切 ，歌德尔的不完备性定理 ，图灵的停机问题 ，lambda算子理论中神奇的Y combinator、乃至著名的罗素悖论、理发师悖论等等 ，其实都源自这个简洁、纯粹而同时又是最 优美的数学方法 ，反过来说 ，从康托尔的对角线方法出发 ，我们可以轻而易举地推导出哥德尔的 不完备性定理 ，而由后者又可以轻易导出停机问题和Y combinator ，实际上 ，我们将会看到 ，后 两者也可以直接由康托尔的对角线方法导出。尤其是Y combinator ，这个形式上绕来绕去 ，本质 上捉摸不透 ，看上去神秘莫测的算子 ，其实只是一个非常自然而然的推论 ，如果从哥德尔的不完 备性定理出发 ，它甚至比停机问题还要来得直接简单。总之 ，你将会看到这些看似深奥的理论是 如何由一个至为简单而又至为深刻的数学方法得出的 ，你将会看到最纯粹的数学美。 图灵的停机问题(The Halting Problem) 了解停机问题的可以直接跳过这一节 ，到下一