-
【专栏】康托尔、哥德尔、图灵（13）
丘齐的lambda calculus其实就是数学推理系统的一个形式化。而图灵机则是把这个数学概念物理化了。而也正因为图灵机的概念隐含了实际的物理实现，所以冯•诺依曼才据此提出了奠定现代计算机体系结构的冯•诺依曼体系结构，其遵循的，正是图灵机的概念。 -
【专栏】康托尔、哥德尔、图灵（12）
当初康托尔在思考无穷集合的时候发现可以称“一切集合的集合”，这样一个集合由于它本身也是一个集合，所以它就属于它自身。也就是说，我们现在可以称世界上存在一类属于自己的集合，除此之外当然就是不属于自己的集合了。 -
【专栏】康托尔、哥德尔、图灵（11）
对角线方法能够揭示出某种自指结构，从而构造出一个“悖论图灵机”。实际上，对角线方法是一种有深远影响的方法，哥德尔的证明其实也是这个方法的一则应用。 -
【专栏】康托尔、哥德尔、图灵（10）
“大道至简”这个名词或许更多出现在文学和哲学里面，一般用在一些模模糊糊玄玄乎乎的哲学观点上。然而，用在这里，数学上，这个名词才终于适得其所。大道至简，看上去最复杂的理论其实建立在一个最简单最纯粹的道理之上。 -
【专栏】康托尔、哥德尔、图灵（9）
哥德尔的不完备性定理证明了数学是一个未完结的学科，永远有需要我们以人的头脑从系统之外去用我们独有的直觉发现的东西。哥德尔的不完备性定理最深刻的地方就是它揭示了自指（或称自引用，递归调用自身等等）结构的普遍存在性。 -
【专栏】康托尔、哥德尔、图灵（8）
哥德尔的不完备性定理被称为20世纪数学最重大的发现。现在我们知道为真但无法在系统内证明的命题不仅仅是这个诡异的“哥德尔命题”，还有很多真正有意义的明确命题，其中最著名的就是连续统假设。 -
【专栏】康托尔、哥德尔、图灵（7）
Y是一个lambda函数，它接受一个伪递归F，在内部生成一个f_gen，然后把f_gen应用到它自身（记得power_gen(power_gen)吧），得到的这个f_gen(f_gen)也就是F的不动点了（因为f_gen(f_gen) = F(f_gen(f_gen))），而根据不动点的性质，F的不动点也就是那个对应于F的真正的递归函数！ -
【专栏】康托尔、哥德尔、图灵（6）
数学竟是如此奇妙，由简单得无法再简单的lambda calculus系统的两条公理居然能够导出如此复杂如此令人目眩神迷的Y Combinator，而这些复杂性其实也只是荡漾在定理海洋中的涟漪，拨开复杂性的迷雾重又发现它们居然寓于极度的简洁之中。 -
【专栏】康托尔、哥德尔、图灵（5）
软件工程里面的一条黄金定律：“任何问题都可以通过增加一个间接层来解决”。不妨把它沿用到我们面临的递归问题上：没错，我们的确没办法在一个lambda函数的定义里面直接（按名字）来调用其自身。 -
【专栏】康托尔、哥德尔、图灵（4）
丘齐做出的这个lambda算子系统里面根本没法实现递归从而在计算能力上面有重大的缺陷？显然不是。马上你就会看到Y combinator是如何把一个看上去非递归的lambda表达式像变魔术那样变成一个递归版本的。