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

康托尔、哥德尔、图灵——永恒金色对角线.doc康托尔、哥德尔、图灵——永恒的金色对角线
康托尔、哥德尔、图灵——永恒的金色对角线
1/22
康托尔、哥德尔、图灵——永恒的金色对角线
康托尔、哥德尔、图灵——永恒的金色对角线
我看到了它，却不敢相
boolGod_algo(char*program,char*input)
{
if(<program>haltson<input>)
returntrue;
returnfalse;
}
这里我们假设if的判断语句里面是你天才思考的结晶，它能够像上帝一样洞察一切程序的
宿命。现在，我们从这个God_algo出发导出一个新的算法：
boolSatan_algo(char*program)
{
if(God_algo(program,program)){
while(1);//loopforever!
returnfalse;//cannevergethere!
}
else
returntrue;
康托尔、哥德尔、图灵——永恒的金色对角线
康托尔、哥德尔、图灵——永恒的金色对角线
2/22
康托尔、哥德尔、图灵——永恒的金色对角线
}
正如它的名字所暗示的那样，这个算法便是一切邪恶的根源了。当我们把这个算法运用到
它自身身上时，会发生什么呢？
Satan_algo(Satan_algo);
我们来分析一下这行简单的调用：
显然，Satan_algo(Satan_algo)这个调用要么能够运行结束返回（停机），要么不能返回
loopforever）。
如果它能够结束，那么Santa_algo算法里面的那个if判断就会成立（因为
God_algo(Santa_algo,Santa_algo)将会返回true），从而程序便进入那个包含一个无穷循
环while(1);的if分支，于是这个Satan_algo(Satan_algo)调用便永远不会返回（结束）了。
而如果Satan_algo(Satan_algo)不能结束（停机）呢，则if判断就会失败，从而选择另一
个if分支并返回true，即Satan_algo(Satan_algo)又能够返回（停机）。总之，我们有：
Satan_algo(Satan_algo)能够停机=>它不能停机
Satan_algo(Satan_algo)不能停机=>它能够停机
所以它停也不是，不停也不是。左右矛盾。
于是，我们的假设，即God_algo算法的存在性，便不成立了。正如拉格朗日所说：“陛下，
我们不需要（上帝）这个假设”[4]。
这个证明相信每个程序员都能够容易的看懂。然而，这个看似不可捉摸的技巧背后其实隐藏着深刻的数学原理（甚至是哲学原理）。在没有认识到这一数学原理之前，至少我当时是对于图灵如何想出这一绝妙证明感到无法理解。但后面，在介绍完了与图灵的停机问题“同构”的Ycombinator之后，我们会深入哥德尔的不完备性定理，在理解了哥德尔不完备
性定理之后，我们从这一同样绝妙的定理出发，就会突然发现，离停机问题和神奇的Ycombinator只是咫尺之遥而已。当然，最后我们会回溯到一切的尽头，康托尔那里，看看
停机问题、Ycombinator、以及不完备性定理是如何自然而然地由康托尔的对角线方法推
导出来的，我们将会看到这些看似神奇的构造性证明的背后，其实是一个简洁优美的数学
康托尔、哥德尔、图灵——永恒的金色对角线
康托尔、哥德尔、图灵——永恒的金色对角线
3/22
康托尔、哥德尔、图灵——永恒的金色对角线
方法在起作用。
YCombinator
了解Ycombinator的请直接跳过这一节，到下一节“哥德尔的不完备性定理”。
让我们暂且搁下但记住绕人的图灵停机问题，走进函数式编程语言的世界，走进由跟图灵机理论等价的lambda算子发展出来的另一个平行的语言世界。让我们来看一看被人们一代一代吟唱着的神奇的YCombinator
康托尔、哥德尔、图灵——永恒的金色对角线
康托尔、哥德尔、图灵——永恒的金色对角线
4/22
康托尔、哥德尔、图灵——永恒的金色对角线
关于

YCombinator

的文章可谓数不胜数，这个由师从希尔伯特的著名逻辑学家