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

康托尔、哥德尔、图灵——永久的金色对角线
康托尔、哥德尔、图灵——永久的金色对角线
1/23
康托尔、哥德尔、图灵——永久的金色对角线
康托尔、哥德尔、图灵 ——永久的金色对角线
我看到了它,却不敢相信它。 ——康托尔
哥德尔的康托尔、哥德尔、图灵——永久的金色对角线
康托尔、哥德尔、图灵——永久的金色对角线
1/23
康托尔、哥德尔、图灵——永久的金色对角线
康托尔、哥德尔、图灵 ——永久的金色对角线
我看到了它,却不敢相信它。 ——康托尔
哥德尔的不齐备性定理震惊了
20世纪数学界的天空,其数学意义推翻了希尔伯特的形式
化数学的雄伟计划,其哲学意义直到
21世纪的今日仍旧不断被延长到各个自然学科,深
刻影响着人们的思想。图灵为认识决希尔伯特有名的第十问题而提出有效计算模型,从而
作出了可计算理论和现代计算机的奠定性工作,有名的停机问题给出了机械计算模型的能
力极限,其深刻的意义和美丽的证明使它成为可计算理论中的标记性定理之一。丘齐,跟
图灵同时代的天才,则从另一个抽象角度提出了
lambda算子的思想,与图灵机抽象的倾
向于硬件性不同,丘齐的lambda
算子理论是从数学的角度进行抽象,不关怀运算的机械
过程而只关怀运算的抽象性质,只用最简短的几条公义便成立起了与图灵机完整等价的计
算模型,其表现出来的数学抽象美开出了函数式编程语言这朵奇葩,
Lisp、Scheme、
Haskell这些以抽象性和简短美为特色的语言到现在仍旧活跃在计算机科学界,固然因为其实质上源于lambda算子理论的抽象方式不切合人的思想习惯从而注定无法成为主流的编程语言[2],但是这仍旧无法阻碍它们成为编程理论以致计算机学科的最正确教本。而出生于
函数式编程语言的奇特的 Ycombinator 到现在仍旧让人们堕入深邃的震惊和反省中间
但是,这全部的全部,看似不很有关却又有点有关,仔细思虑其关系却又有点一头雾水的
背后,其实隐约藏着一条线,这条线把它们从实质上串到了一起,而顺着光阴的河流逆流
而上,我们将会看到,这条线的终点,不是他人,正是只手扒开被不严实性问题困扰的 19
世纪数学界阴森天空的天才数学家康托尔,康托尔创建性地将一一对应和对角线方法运用
到无量会合理论的成立中间,这个被希尔伯特称为 “谁也无法将我们从康托尔为我们创建的
乐园中驱赶出去 ”、被罗素称为 “19世纪最伟大的智者之一 ”的人,他在会合论方面的工作终
于遣散了不严实性问题带来的阴霾,忧如一道金色的阳光刺破乌云, 19世纪的数学终于看
到了真实严格化的曙光,数学终于得以站在了亘古未有的牢固的基础之上;会合论到现在还是数学里最基础和最重要的理论之一。而康托尔当初在研究无量会合时最具天才的方法之
一——对角线方法——则带来了极其深远的影响,其纯粹而直指事物实质的思想如洪钟大
吕般响彻数学和哲学的每一个角落 [3]。跟着本文的睁开,你将会看到,方才提到的全部,
歌德尔的不齐备性定理,图灵的停机问题, lambda算子理论中奇特的 Ycombinator、以致
有名的罗素悖论、剪发师悖论等等,其实都源自这个简短、纯粹而同时又是最优美的数学
方法,反过来说,从康托尔的对角线方法出发,我们能够易如反掌地推导出哥德尔的不完
备性定理,而由后者又能够轻易导出停机问题和 Ycombinator,实质上,我们将会看到,
后二者也能够直接由康托尔的对角线方法导出。特别是 Ycombinator,这个形式上绕来绕
去,实质上捉摸不透,看上去神奇莫测的算子,其实不过一个特别自但是然的推论,假如从哥德尔的不齐备性定理出发,它甚至比停机问题还要来得直接简单。总之,你将会看到这些看似高深的理论是怎样由一个至为简单而又至为深刻的数学方法得出的,你将会看到最纯粹的数学美。
图灵的停机问题 (TheHaltingProblem)
认识停机问题的能够直接跳过这一节,到下一节“YCombinator”,认识后者的再跳到下一节“哥德尔的不齐备性定理”
我们还是从图灵有名的停机问题提及,一来它相对来说是我们要说的几个定应中间最简单的,二来它也最切近程序员。实质上,我从前曾写过一篇对于图灵机的文章,有兴趣的读者能够从那篇开始,那篇主假如从理论上论述,所以这里我们打算避开抽象的理论,换一种切合程序员思想习惯的直观方式来加以解说。
停机问题
不存在这样一个程序(算法),它能够计算任何程序(算法)在给定输入上能否会结束
(停机)。
那么,怎样来证明这个停机问题呢?反证。假定我们某一天真做出了这么一个极度聪慧的全能算法(就叫God_algo吧),你只需给它一段程序(二进制描绘),再给它这段程序的输入,它就能告诉你这段程序在这个输入上会不