转－康托尔、哥德尔、图灵——永恒的金色对角线（二）

Kevin.Li

浏览: 8354 次
来自: ...

最近访客更多访客>>

woodding2008

InJavaWeTrust

qianxiaowei

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

知海无涯

算法数据结构八卦云计算游戏

哥德尔的不完备性定理

[注：了解哥德尔不完备性定理的可以跳到下一节，“大道至简——康托尔的天才”]

然而，漫长的Y Combinator征途仍然并非本文的最终目的，对于Y combinator的构造和解释，只是给不了解lambda calculus或Y combinator的读者看的。关键是你会看到Y combinator可以由哥德尔不完备性定理证明的一个核心构造式一眼瞧出来！

让我们的思绪回到1931年，那个数学界风起云涌的年代，一个名不经传的20出头的学生，在他的博士论文中证明了一个惊天动地的结论。

在那个年代，希尔伯特的数学天才就像太阳的光芒一般夺目，在关于数学严格化的大纷争中希尔伯特带领的形式主义派系技压群雄，得到许多当时有名望的数学家的支持。希尔伯特希望借助于形式化的手段，抽掉数学证明中的意义，把数学证明抽象成一堆无意义的符号转换，就连我们人类赖以自豪的逻辑推导，也不过只是一堆堆符号转换而已（想起lambda calculus系统了吧：）)。这样一来，一个我们日常所谓的，带有直观意义和解释的数学系统就变成了一个纯粹由无意义符号表达的、公理加上推导规则所构成的形式系统，而数学证明呢，只不过是在这个系统内玩的一个文字游戏。令人惊讶的是，这样一种做法，真的是可行的！数学的意义，似乎竟然真的可以被抽掉！另一方面，一个形式系统具有非常好的性质，平时人们证明一个定理所动用的推导，变成了纯粹机械的符号变换。希尔伯特希望能够证明，在任一个无矛盾的形式系统中所能表达的所有陈述都要么能够证明要么能够证伪。这看起来是个非常直观的结论，因为一个结论要么是真要么是假，而它在它所处的领域/系统中当然应该能够证明或证伪了（只要我们能够揭示出该系统中足够多的真理）。

然而，哥德尔的证明无情的击碎了这一企图，哥德尔的证明揭示出，任何足够强到蕴含了皮亚诺算术系统（PA）的一致（即无矛盾）的系统都是不完备的，所谓不完备也就是说在系统内存在一个为真但无法在系统内推导出的命题。这在当时的数学界揭起了轩然大波，其证明不仅具有数学意义，而且蕴含了深刻的哲学意义。从那时起这一不完备性定理就被引申到自然科学乃至人文科学的各个角落…至今还没有任何一个数学定理居然能够产生这么广泛而深远的影响。

哥德尔的证明非常的长，达到了200多页纸，但其中很大的成分是用在了一些辅助性的工作上面，比如占据超过1/3纸张的是关于一个形式系统如何映射到自然数，也就是说，如何把一个形式系统中的所有公式都表示为自然数，并可以从一自然数反过来得出相应的公式。这其实就是编码，在我们现在看来是很显然的，因为一个程序就可以被编码成二进制数，反过来也可以解码。但是在当时这是一个全新的思想，也是最关键性的辅助性工作之一，另一方面，这正是“程序即数据”的最初想法。

现在我们知道，要证明哥德尔的不完备性定理，只需在假定的形式系统T内表达出一个为真但无法在T内推导出（证明）的命题。于是哥德尔构造了这样一个命题，用自然语言表达就是：命题P说的是“P不可在系统T内证明”（这里的系统T当然就是我们的命题P所处的形式系统了），也就是说“我不可以被证明”，跟著名的说谎者悖论非常相似，只是把“说谎”改成了“不可以被证明”。我们注意到，一旦这个命题能够在T内表达出来，我们就可以得出“P为真但无法在T内推导出来”的结论，从而证明T的不完备性。为什么呢？我们假设T可以证明出P，而因为P说的就是P不可在系统T内证明，于是我们又得到T无法证明出P，矛盾产生，说明我们的假设“T可以证明P”是错误的，根据排中律，我们得到T不可以证明P，而由于P说的正是“T不可证明P”，所以P就成了一个正确的命题，同时无法由T内证明！

如果你足够敏锐，你会发现上面这番推理本身不就是证明吗？其证明的结果不就是P是正确的？然而实际上这番证明是位于T系统之外的，它用到了一个关于T系统的假设“T是一致（无矛盾）的”，这个假设并非T系统里面的内容，所以我们刚才其实是在T系统之外推导出了P是正确的，这跟P不能在T内推导出来并不矛盾。所以别担心，一切都正常。

那么，剩下来最关键的问题就是如何用形式语言在T内表达出这个P，上面的理论虽然漂亮，但若是P根本没法在T内表达出来，我们又如何能证明“T内存在这个为真但无法被证明的P”呢？那一切还不是白搭？

于是，就有了哥德尔证明里面最核心的构造，哥德尔构造了这样一个公式：

N(n) is unprovable in T

这个公式由两部分构成，n是这个公式的自由变量，它是一个自然数，一旦给定，那么这个公式就变成一个明确的命题。而N则是从n解码出的货真价实的公式（记得哥德尔的证明第一部分就是把公式编码吗？）。”is unprovable in T”则是一个谓词，这里我们没有用形式语言而是用自然语言表达出来的，但哥德尔证明了它是可以用形式语言表达出来的，大致思路就是：一个形式系统中的符号数目是有限的，它们构成这个形式系统的符号表。于是，我们可以依次枚举出所有长度为1的串，长度为2的串，长度为3的串… 此外根据形式系统给出的语法规则，我们可以检查每个串是否是良构的公式（well formed formula，简称wff，其实也就是说，是否符合语法规则，前面我们在介绍lambda calculus的时候看到了，一个形式系统是需要语法规则的，比如逻辑语言形式化之后我们就会看到P->Q是一个wff，而->PQ则不是），因而我们就可以枚举出所有的wff来。最关键的是，我们观察到形式系统中的证明也不过就是由一个个的wff构成的序列（想想推导的过程，不就是一个公式接一个公式嘛）。而wff构成的序列本身同样也是由符号表内的符号构成的串。所以我们只需枚举所有的串，对每一个串检查它是否是一个由wff构成的序列（证明），如果是，则记录下这个wff序列（证明）的最后一个wff，也就是它的结论。这样我们便枚举出了所有的可由T推导出的定理。然后为了表达出”X is unprovable in T”，本质上我们只需说“不存在这样一个自然数S，它所解码出来的wff序列以X为终结”！这也就是说，我们表达出了“is unprovable in T”这个谓词。

我们用UnPr(X)来表达“X is unprovable in T”，于是哥德尔的公式变成了：

UnPr( N(n) )

现在，到了最关键的部分，首先我们把这个公式简记为G(n)——别忘了G内有一个自由变量n，所以G现在还不是一个命题，而只是一个公式，所以谈不上真假：

G(n): UnPr( N(n) )

又由于G也是个wff，所以它也有自己的编码g，当然g是一个自然数，现在我们把g作为G的参数，也就是说，把G里面的自由变量n替换为g，我们于是得到一个真正的命题：

G(g): UnPr( G(g) )

用自然语言来说，这个命题G(g)说的就是“我是不可在T内证明的”。看，我们在形式系统T内表达出了“我是不可在T内证明的”这个命题。而我们一开始已经讲过了如何用这个命题来推断出G(g)为真但无法在T内证明，于是这就证明了哥德尔的不完备性定理[4]。

哥德尔的不完备性定理被称为20世纪数学最重大的发现（不知道有没有“之一”:) ）现在我们知道为真但无法在系统内证明的命题不仅仅是这个诡异的“哥德尔命题”，还有很多有真正有意义的明确命题，其中最著名的就是连续统假设，此外哥德巴赫猜想也有可能是个没法在数论系统中证明的真命题。

从哥德尔公式到Y Combinator

哥德尔的不完备性定理证明了数学是一个未完结的学科，永远有需要我们以人的头脑从系统之外去用我们独有的直觉发现的东西。罗杰·彭罗斯在《The Emperor's New Mind》中用它来证明人工智能的不可实现。当然，这个结论是很受质疑的。但哥德尔的不完备性定理的确还有很多很多的有趣推论，数学的和哲学上的。但哥德尔的不完备性定理最深刻的地方就是它揭示了自指（或称自引用，递归调用自身等等）结构的普遍存在性，我们再来看一看哥德尔命题的绝妙构造：

G(n): UnPr( N(n) )

我们注意到，这里的UnPr其实是一个形式化的谓词，它不一定要说“X在T内可证明”，我们可以把它泛化为一个一般化的谓词，P：

G(n): P( N(n) )

也就是说，对于任意一个单参的谓词P，都存在上面这个哥德尔公式。然后我们算出这个哥德尔公式的自然数编码g，然后把它扔给G，就得到：

G(g): P( G(g) )

是不是很熟悉这个结构？我们的Y Combinator的构造不就是这样一个形式？我们把G和P都看成一元函数，G(g)可不正是P这个函数的不动点么！于是，我们从哥德尔的证明里面直接看到了Y Combinator！

至于如何从哥德尔的证明联系到停机问题，就留给你去解决吧:) 因为更重要的还在后面，我们看到，哥德尔的证明虽然巧妙至极，然而其背后的思维过程仍然飘逸而不可捉摸，至少我当时看到G(n)的时候，“乃大惊”“不知所从出”，他怎么想到的？难道是某一个瞬间“灵光一现”？一般我是不信这一说的，已经有越来越多的证据表明一瞬间的“灵感”往往是潜意识乃至表层意识长期思考的结果。哥德尔天才的证明也不例外，我们马上就会看到，在这个神秘的构造背后，其实隐藏着某种更深的东西，这就是康托尔在19世纪80年代研究无穷集合和超限数时引入的对角线方法。这个方法仿佛有种神奇的力量，能够揭示出某种自指的结构来，而同时，这又是一个极度简单的手法，通过它我们能够得到数学里面一些非常奇妙的性质。无论是哥德尔的不完备性定理还是再后来丘齐建立的lambda calculus，抑或我们非常熟悉的图灵机理论里的停机问题，其实都只是这个手法简单推演的结果！

大道至简——康托尔的天才

“大道至简”这个名词或许更多出现在文学和哲学里面，一般用在一些模模糊糊玄玄乎乎的哲学观点上。然而，用在这里，数学上，这个名词才终于适得其所。大道至简，看上去最复杂的理论其实建立在一个最简单最纯粹的道理之上。

康托尔在无穷集合和超限数方面的工作主要集中在两篇突破性的论文上，这也是我所见过的最纯粹最美妙的数学论文，现代的数学理论充斥了太多复杂的符号和概念，很多时候让人看不到最本质的东西，当然，不否认这些东西很多也是有用的，然而，要领悟真正的数学美，像集合论和数论这种纯粹的东西，真的非常适合。不过这里就不过多谈论数学的细节了，只说康托尔引入对角线方法的动机和什么是对角线方法。

神奇的一一对应

康托尔在研究无穷集合的时候，富有洞察性地看到了对于无穷集合的大小问题，我们不能再使用直观的“所含元素的个数”来描述，于是他创造性地将一一对应引入进来，两个无穷集合“大小”一样当且仅当它们的元素之间能够构成一一对应。这是一个非常直观的概念，一一对应嘛，当然个数相等了，是不是呢？然而这同时就是它不直观的地方了。对于无穷集合，我们日常的所谓“个数”的概念不管用了，因为无穷集合里面的元素个数本就是无穷多个。不信我们来看一个小小的例子。我们说自然数集合能够跟偶数集合构成一一对应，从而自然数集合跟偶数集合里面元素“个数”是一样多的。怎么可能？偶数集合是自然数集合的真子集，所有偶数都是自然数，但自然数里面还包含奇数呢，说起来应该是二倍的关系不是？不是！我们只要这样来构造一一对应：

1 2 3 4 …

2 4 6 8 …

用函数来描述就是 f(n) = 2n。检验一下是不是一一对应的？不可思议对吗？还有更不可思议的，自然数集是跟有理数集一一对应的！对应函数的构造就留给你解决吧，提示，按如下方式来挨个数所有的有理数：

1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1 …

用这种一一对应的手法还可以得到很多惊人的结论，如一条直线上所有的点跟一个平面上所有的点构成一一对应（也就是说复数集合跟实数集合构成一一对应）。以致于康托尔自己都不敢相信自己的眼睛了，这也就是为什么他在给戴得金的信中会说“我看到了它，却不敢相信它”的原因。

然而，除了一一对应之外，还有没有不能构成一一对应的两个无穷集合呢？有。实数集合就比自然数集合要“大”，它们之间实际上无法构成一一对应。这就是康托尔的对角线方法要解决的问题。

实数集和自然数集无法构成一一对应？！

我们只需将实数的小数位展开，并且我们假设实数集能够与自然数集一一对应，也就是说，可列的，所以我们把它们与自然数一一对应列出，如下：

1 a10.a11a12a13…

2 a20.a21a22a23…

3 a30.a31a32a33…

. …

[注：aij里面的ij是下标，csdn blog对下标表示似乎有点问题]

现在，我们构造一个新的实数，它的第i位小数不等于aii。也就是说，它跟上面列出的每一个实数都至少有一个对应的小数位不等，也就是说它不等于我们上面列出的所有实数，这跟我们上面假设已经列出了所有实数的说法相矛盾。所以实数集只能是不可列的，即不可与自然数集一一对应！这是对角线方法的最简单应用。

对角线方法——停机问题的深刻含义

对角线方法有很多非常奇妙的结论。其中之一就是文章一开始提到的停机问题。我想绝大多数人刚接触停机问题的时候都有一个问题，图灵怎么能够想到这么诡异的证明，怎么能构造出那个诡异的“说停机又不停机，说不停机又停机”的悖论机器。马上我们就会看到，他其实只是对角线方法的一个直接结论。

还是从反证开始，我们假设存在这样一个图灵机，他能够判断任何程序在任何输入上是否停机。由于所有图灵机构成的集合是一个可列集（也就是说，我们可以逐一列出所有的图灵机，证明见我以前的一篇文章《图灵机杂思》），所以我们可以很自然地列出下表，它表示每个图灵机分别在每一个可能的输入（1,2,3,…）下的输出，n/a表示无法停机，其余数值则表示停机后的输出：

1 2 3 4 …

M1 n/a 1 n/a n/a …

M2 2 0 n/a 0 …

M3 0 1 2 0 …

M4 n/a 0 5 n/a …

… …

右侧纵向的M1,M2,M3 … 是逐一列出的图灵机，并且，注意，由于程序即数据，每个图灵机都有唯一编码，所以我们规定在枚举图灵机的时候Mi其实就代表编码为i的图灵机，当然这里很多图灵机将会是根本没用的玩意，但这不要紧。此外，最上面的一行1 2 3 4 … 是输入数据，如，矩阵的第一行代表M1分别在1,2,3, …上面的输出，不停机就是n/a。

我们刚才假设存在这样一个图灵机H，它能够判断任何程序在任何输入上能否停机，换句话说，H(i,j)（i是Mi的编码）能够给出“Mi(j)”是n/a（不停）呢还是给出一个具体的结果（停）。

我们现在来运用康托尔的对角线方法，我们构造一个新的图灵机P，P在1上的输出行为跟M1(1)“不一样”，在2上的输出行为跟M2(2)“不一样”，…总之P在输入i上的输出跟Mi(i)不一样。只需利用一下我们万能的H，这个图灵机P就不难构造出来，如下：

P(i) = 1 + Mi(i) if H(i,i) = 1 (if Mi(i) halts)

0 if H(i,i) = 0 (if Mi(i) doesn’t halt)

也就是说，如果Mi(i)停机，那么P(i)的输出就是Mi(i)+1，如果Mi(i)不停机的话，P(i)就停机且输出0。这就保证了P(i)的输出行为跟Mi(i)反正不一样。现在，我们注意到P本身是一个图灵机，而我们上面已经列出了所有的图灵机，所以必然存在一个k，使得Mk = P。而两个图灵机相等当且仅当它们对于所有的输入都相等，也就是说对于任取的n，有Mk(n) = P(n)，现在令n=k，得到Mk(k)=P(k)，根据上面给出的P的定义，这实际上就是：

Mk(k) = P(k) = 1+Mk(k) if Mk(k) halts

0 if Mk(k) doesn’t halt

看到这个式子的矛盾了吗？如果Mk(k)停机，那么Mk(k)=1+Mk(k)；如果Mk(k)不停机，则Mk(k)=0（给出结果0即意味着Mk(k)停机）；不管哪种情况都是矛盾。于是我们得出，不存在那样的H。

这个对角线方法实际上说明了，无论多聪明的H，总存在一个图灵机的停机行为是它无法判断的。这跟哥德尔定理“无论多‘完备’的形式化公理系统，都存在一个‘哥德尔命题’是无法在系统内推导出来的”从本质上其实是一模一样的。只不过我们一般把图灵的停机问题称为“可判定问题”，而把数学的称为“可证明问题”。

等等！如果我们把那个无法判定是否停机的图灵机作为算法的特例纳入到我们的H当中呢？我们把得到的新的判定算法记为H1。然而，可惜的是，在H1下，我们又可以相应地以同样的手法从H1构造出一个无法被它（H1）判定的图灵机来。你再加，我再构造，无论你加多少个特例进去，我都可以由同样的方式构造出来一个你无法够到的图灵机，以彼之矛，攻彼之盾。其实这也是哥德尔定理最深刻的结论之一，哥德尔定理其实就说明了无论你给出多少个公理，即无论你建立多么完备的公理体系，这个系统里面都有由你的那些公理出发所推导不到的地方，这些黑暗的角落，就是人类直觉之光才能照射到的地方！

本节我们从对角线方法证明了图灵的停机问题，我们看到，对角线方法能够揭示出某种自指结构，从而构造出一个“悖论图灵机”。实际上，对角线方法是一种有深远影响的方法，哥德尔的证明其实也是这个方法的一则应用。证明与上面的停机问题证明如出一辙，只不过把Mi换成了一个形式系统内的公式fi，具体的证明就留给聪明的你吧:)我们现在来简单的看一下这个奇妙方法的几个不那么明显的推论。

罗素悖论

学过逻辑的人大约肯定是知道著名的罗素悖论的，罗素悖论用数学的形式来描述就是：

R = {X:X不属于X};

这个悖论最初是从康托尔的无穷集合论里面引申出来的。当初康托尔在思考无穷集合的时候发现可以称“一切集合的集合”，这样一个集合由于它本身也是一个集合，所以它就属于它自身。也就是说，我们现在可以称世界上存在一类属于自己的集合，除此之外当然就是不属于自己的集合了。而我们把所有不属于自己的集合收集起来做成一个集合R，这就是上面这个著名的罗素悖论了。

我们来看R是否属于R，如果R属于R，根据R的定义，R就不应该属于R。而如果R不属于R，则再次根据R的定义，R就应该属于R。

这个悖论促使了集合论的公理化。后来策梅罗公理化的集合论里面就不允许X属于X（不过可惜的是，尽管如此还是没法证明这样的集合论不可能产生出新的悖论。而且永远没法证明——这就是哥德尔第二不完备性定理的结论——一个包含了PA的形式化公理系统永远无法在内部证明其自身的一致（无矛盾）性。从而希尔伯特想从元数学推出所有数学系统的一致性的企图也就失败了，因为元数学的一致性又得由元元数学来证明，后者的一致性又得由元元元数学来证明…）。

这里我们只关心罗素是如何想出这个绝妙的悖论的。还是对角线方法！我们罗列出所有的集合，S1,S2,S3 …

S1 S2 S3 …

S1 0 1 1 …

S2 1 1 0 …

S3 0 0 0 …

… …

右侧纵向列出所有集合，顶行横向列出所有集合。0/1矩阵的(i,j)处的元素表示Si是否包含Sj，记为Si(j)。现在我们只需构造一个新的0/1序列L，它的第i位与矩阵的(i,i)处的值恰恰相反：L(i) = 1-Si(i)。我们看到，这个新的序列其实对应了一个集合，不妨也记为L，L(i)表示L是否包含Si。根据L的定义，如果矩阵的(i,i)处值为0（也就是说，如果Si不包含Si），那么L这个集合就包含Si,否则就不包含。我们注意到这个新的集合L肯定等于某个Sk（因为我们已经列出了所有的集合），L = Sk。既然L与Sk是同一集合，那么它们肯定包含同样的元素，从而对于任意n，有L(n) = Sk(n)。于是通过令n=k，得到L(k) = Sk(k)，而根据L的定义，L(k) = 1- Sk(k)。这就有Sk(k) = 1-Sk(k)，矛盾。

通过抽象简化以上过程，我们看到，我们构造的L其实是“包含了所有不包含它自身的集合的集合”，用数学的描述正是罗素悖论！

敏锐的你可能会注意到所有集合的数目是不可数的从而根本不能S1,S2…的一一列举出来。没错，但通过假设它们可以列举出来，我们发现了一个与可列性无关的悖论。所以这里的对角线方法其实可以说是一种启发式方法。

同样的手法也可以用到证明P(A)（A的所有子集构成的集合，也叫幂集）无法跟A构成一一对应上面。证明就留给聪明的你了:)

希尔伯特第十问题结出的硕果

希尔伯特是在1900年巴黎数学家大会上提出著名的希尔伯特第十问题的，简言之就是是否存在一个算法，能够计算任意丢番图方程是否有整根。要解决这个问题，就得先严格定义“算法”这一概念。为此图灵和丘齐分别提出了图灵机和lambda calculus这两个概念，它们从不同的角度抽象出了“有效（机械）计算”的概念，著名的图灵——丘齐命题就是说所有可以有效计算出来的问题都可以由图灵机计算出来。实际上我们已经看到，丘齐的lambda calculus其实就是数学推理系统的一个形式化。而图灵机则是把这个数学概念物理化了。而也正因为图灵机的概念隐含了实际的物理实现，所以冯·诺依曼才据此提出了奠定现代计算机体系结构的冯·诺依曼体系结构，其遵循的，正是图灵机的概念。而“程序即数据”的理念，这个发端于数学家哥德尔的不完备性定理的证明之中的理念，则早就在黑暗中预示了可编程机器的必然问世。

对角线方法——回顾

我们看到了对角线方法是如何简洁而深刻地揭示出自指或递归结构的。我们看到了著名的不完备性定理、停机问题、Y Combinator、罗素悖论等等等等如何通过这一简洁优美的方法推导出来。这一诞生于康托尔天才的手法如同一条金色的丝线，把位于不同年代的伟大发现串联了起来，并且将一直延续下去… 而本文的目的也就是要揭示出这几个著名的问题或定理背后隐藏的深刻的数学哲理。

一些P.S.

1．lambda calculus里面的“停机问题”

实际上lambda calculus里面也是有“停机问题”的等价版本的。其描述就是：不存在一个算法能够判定任意两个lambda函数是否等价。所谓等价当然是对于所有的n,有f(n)=g(n)了。这个问题的证明更加能够体现对角线方法的运用。仍然留给你吧。

2．负喧琐话（http://blog.csdn.net/g9yuayon）是个非常不错的blog:)g9的文字轻松幽默，而且有很多名人八卦可以养眼，真的灰常…灰常…不错哦。此外g9老兄还是个理论功底非常扎实的牛。所以，anyway，看了他的blog就知道啦！最初想写这篇文章的动机也正是看了上面的一篇关于Y Combinator的铸造过程的介绍，于是想揭示一些更深的东西，经过一个白天黑夜的猛烈敲击于是就有了这篇至今写过的最长的一篇文章:)

3.文章起名《康托尔、哥德尔、图灵——永恒的金色对角线》其实是为了纪念看过的一本好书GEB，即《Godel、Escher、Bach-An Eternal Golden Braid》中文译名《哥德尔、埃舍尔、巴赫——集异璧之大成》——商务印书馆出版。对于一本定价50元居然能够在douban上卖到100元的二手旧书，我想无需多说。另，幸福的是，电子版可以找到:)

4．其实很久前想写的是一篇《从哥德尔到图灵》，但那篇写到1/3不到就搁下了，一是由于事务，二是总觉得少点什么。呵呵，如今把康托尔扯进来，也算是完成当时扔掉的那一篇吧。

5.这恐怕算是写得最曲折的一篇文章了。不仅自己被这些问题搞得有点晕头转向（还好总算走出来），更因为要把这些东西自然而然的串起来，也颇费周章。很多时候是利用吃饭睡觉前或走路的时间思考本质的问题以及如何表达等等，然后到纸上一气呵成。不过同时也锻炼了不拿纸笔思考数学的能力，呵呵。

6.关于图灵的停机问题、Y Combinator、哥德尔的不完备性定理以及其它种种与康托尔的对角线之间的本质联系，几乎查不到完整系统的深入介绍，一些书甚至如《The Emperor’s New Mind》也只是介绍了与图灵停机问题之间的联系（已经非常的难得了），google和baidu的结果也是基本没有头绪。很多地方都是一带而过让人干着急。所以看到很多地方介绍这些定理和构造的时候都是弄得人晕头转向的，绝大部分人在面对如Y Combinator、不完备性定理、停机问题的时候都把注意力放在力图理解它是怎么运作的上面了，却使人看不到其本质上从何而来，于是人们便对这些东东大为惊叹。这使我感到很不痛快，如隔靴搔痒般。于是有了本文。

[1] Douglas R.Hofstadter的著作《Godel, Escher, Bach: An Eternal Golden Braid》（《哥德尔、艾舍尔、巴赫——集异璧之大成》）就是围绕这一思想写出的一本奇书。非常建议一读。

[2] 虽然我觉得那个系徽做得太复杂，要表达这一简洁优美的思想其实还能有更好的方式。

[3] g9的blog（负暄琐话）http://blog.csdn.net/g9yuayon/ 上有一系列介绍lambda calculus的文章（当然，还有其它好文章:)），非常不错，强烈推荐。最近的两篇就是介绍Y combinator的。其中有一篇以javaScript语言描述了迭代式逐步抽象出Y Combinator的过程。

[4] 实际上这只是第一不完备性定理，它还有一个推论，被称为第二不完备性定理，说的是任一个系统T内无法证明这个系统本身的一致性。这个定理的证明核心思想如下：我们前面证明第一不完备性定理的时候用的推断其实就表明 Con/T -> G(g) （自然语言描述就是，由系统T的无矛盾，可以推出G(g)成立），而这个“Con/T -> G(g)”本身又是可以在T内表达且证明出来的（具体怎么表达就不再多说了）——只需要用排中律即可。于是我们立即得到，T里面无法推出Con/T，因为一旦推出Con/T就立即推出G(g)从而推出UnPr(G(g))，这就矛盾了。所以，Con/T无法在T内推出（证明）。

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1336154

分享到：

关于Visual Studio的调试不可用的问题 | 转－康托尔、哥德尔、图灵——永恒的金色对 ...

2008-02-18 17:08
浏览 1301
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论