神奇的数学，神奇的lamda演算

今天读了一篇〈康托尔、哥德尔、图灵——永恒的金色对角线〉（刘未鹏）(博客资源中可以下载），感慨颇深。机缘巧合之下读到这篇文章，读了第一段我就入迷，不得不继续下去，于是我花了一晚上读完了这篇12页的文章。一部精美的数学史展现在我的眼前，原来在计算机的背后竟有这么美妙的数学理论。
截取该文前言，有兴趣的人可以搜索这篇文章读完。

哥德尔的不完备性定理震撼了20世纪数学界的天空，其数学意义颠覆了希尔伯特的形式化数学的宏伟计划，其哲学意义直到21世 纪的今天仍然不断被延伸到各个自然学科，深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型，进而作出了可计算理论和现代计算 机的奠基性工作，著名的停机问题给出了机械计算模型的能力极限，其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐，跟图灵同时代的天 才，则从另一个抽象角度提出了lambda算子的思想，与图灵机抽象的倾向于硬件性不同，丘齐的lambda算子理论是从数学的角度进行抽象，不关心运算的机械过程而只关心运算的抽象性质，只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型，其体现出来的数学抽象美开出了函数式编程语言这朵奇葩，Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界，虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言，然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…

然而，这一切的一切，看似不很相关又有点相关，认真思考其关系却又有点一头雾水的背后，其实隐隐藏着一条线，这条线把它们从本质上串到了一起，而顺着时光的河流逆流而上，我们将会看到，这条线的尽头，不是别人，正是只手拨开被不严密性问题困扰的19世纪数学界阴沉天空的天才数学家康托尔，康托尔创造性地将一一对应和对角线方法运用到无穷集合理论的建立当中，这个被希尔伯特称为“谁也无法将我们从康托尔为我们创造的乐园中驱逐出去”、被罗素称为“19世纪最伟大的智者之一”的人，他在集合论方面的工作终于驱散了不严密性问题带来的阴霾，仿佛一道金色的阳光刺破乌云，19世 纪的数学终于看到了真正严格化的曙光，数学终于得以站在了前所未有的坚固的基础之上；集合论至今仍是数学里最基础和最重要的理论之一。而康托尔当初在研究 无穷集合时最具天才的方法之一——对角线方法——则带来了极其深远的影响，其纯粹而直指事物本质的思想如洪钟大吕般响彻数学和哲学的每一个角落[1]。随着本文的展开，你将会看到，刚才提到的一切，歌德尔的不完备性定理，图灵的停机问题，lambda算子理论中神奇的Y combinator、乃至著名的罗素悖论、理发师悖论等等，其实都源自这个简洁、纯粹而同时又是最优美的数学方法，反过来说，从康托尔的对角线方法出发，我们可以轻而易举地推导出哥德尔的不完备性方法，而又后者又可以轻易导出停机问题和Y combinator，实际上，我们将会看到，后两者也可以直接由康托尔的对角线方法导出。尤其是Y combinator， 这个形式上绕来绕去，本质上捉摸不透，效果上神秘莫测的算子，其实只是一个非常自然而然的推论，如果从哥德尔的不完备性定理出发，它甚至比停机问题还要来 得直接简单。总之，你将会看到这些看似深奥的理论是如何由一个至为简单而又至为深刻的数学方法得出的，你将会看到最纯粹的数学美。

接着该文顺序介绍了图灵停机问题（完美的证明了不存在一个算法可以判定给定的程序和给定的输入条件下是否能够停机），lamda演算基础（lamda演算其精妙看了真的让人感叹！再加上Y combinator，这个仅有2个公理的公理系统竟然和图灵机等价，也就是具有图灵机同等的计算能力，这也是我们当今计算机的计算模型），Y cominator，歌德尔不完备性定理，康托尔对角线方法。佩服佩服！
太完美了，不敢相信居然还有这样的理论。而歌德尔不完备性证明竟然只是他的博士论文。真不知道这些伟大的思维是怎么诞生地，真不知道他们为何可以有这样不同寻常的想象力。我实在太佩服了，我开始相信哲学了，也许哲学真的是一切学问的学问，也许他真的就是所谓的metaphysics.
引用康托尔的一句话“我看到了它，却不敢相信它”
学了这么久计算机，我觉得我越来越不懂计算机这个东西了。