GEB读书笔记之四——哥德尔不完备性定理

在继续折腾数学之前我们先来看看计算机中的一个类似的问题吧。作为程序猿,提到新的一门语言,大概都是是先学“Hello World”怎么说(相对的,正常人一般会先学“我爱你”怎么说)。一般来说提到Hello World程序那必定就是非常简单的程序了,不过我们想像这样一个程序:这个程序接收输入n,之后寻找方程 \(x^n+y^n=z^n\) 的整数解,如果找到,则打印Hello World,如果没找到,则继续搜索下去并不打印任何东西。那么如果我们有另外一个程序,这个程序可以判定之前那个程序是否能够显示Hello World,如果能显示就输出Yes,不能的话就输出No。这其实就相当于一个费马大定理的验证程序,相似的,我们还可以弄出证明XXXX猜想的程序,数学家们耗费几百年才解决或者至今都没有解决的问题就能被我们计算机工作者轻松加愉快的解决了耶~~~那么这种程序真的可能做出来么? 答案一如既往的悲剧:否。

我们的想要做的程序可以由下面的图来说明,假设我们想要做的程序是H,它可以接收另外一个程序 P 和输入 I 作为输入,其用于断定带输入 I 的程序 P 是否显示Hello World,如果是,则程序H输出Yes,否则输出No。我们将证明这种程序H是不存在的。

Photobucket

运用归谬法,假设这样的程序H存在,我们将其做一些修改,修改后的程序我们称之为\(H_1\),但是其与H没有本质的不同。这样的修改是:当H输出为No的时候,\(H_1\)输出Hello World。

Photobucket

第二步,我们让 P 的输入 I 就是 P 本身,这个可以由编码来实现,类似于上次讲的哥德尔配数,程序也是可以编码的。之后我们就只需要输入 P 而不是 P 和 I 了。此时构造程序\(H_2\),其在\(H_1\)的基础上做如下修改:

  • 读入整个输入P并保存
  • 之后模拟\(H_1\),只是当\(H_1\)读取输入时\(H_2\)就读取上一步保存的副本

最后的示意图可以如下所示:

Photobucket

那么现在就可以证明\(H_2\)是不存在的。因为如果我们把\(H_2\)当做输入 P 喂给它自己,这时就会出现悖论。首先,如果判定程序\(H_2\)输出Yes,则意味着\(H_2\)以自身作为输入显示Hello World,但是刚才我们假设\(H_2\)输出的是Yes而不是Hello World。同样的,如果假设\(H_2\)以自身作为输入输出的是Hello  World,则判定程序\(H_2\)输出一定是Yes。所以无论假设\(H_2\)有什么输出,都能推出其有另一个输出。这就造成了悖论,解决这个悖论的方法就是承认\(H_2\)不存在,所以\(H_1\)也不存在,所以H也不存在。

哥德尔的证明和上面的类似,哥德尔在我们所说的那个足够复杂的系统中构造了一个自指的命题,这个命题为真,并且这个命题在那个系统下不可证,于是两全的企图被打破了,想活在新闻连播中?那么只有自己努力喽。不过在说明哥德尔用了什么命题之前,先来看看自指是什么意思:

在这个视频里,Carl在说My voice is higher than your voice时会同时提高声音,可以说这句话自己提到了自己,这种感觉很奇妙,因为一般来说我们说的一个句子都是在讨论其他东西,而这个句子却在说自己,再举个例子:“这句话有七个字”,告诉了我们一个关于这句话自己的事实:它有七个字。这种句子听上去也许不是很舒服,但却是哥德尔证明中重要的东西。

之后就明说了吧,我们为了证明希尔伯特方案是不可能的,需要构造一个能够推翻它的定理,这个定理满足如下条件:

  • 在那个足够复杂的系统内部可以表示。
  • 这个定理是真的。
  • 这个定理在那个复杂系统中不可证。

能够在复杂系统内部被表示是一个必要条件,否则谈何“在该系统下可证”这个性质(自己都表示不了的东西可不可证无所谓)。那么哥德尔想要构造的命题就是:“本命题不是系统的定理”。但是,直接这么说是不行的,因为这句话是没法表示成系统中的定理的。原因某种程度上是显然的,这句话形容的是系统的一个性质,但是,系统内部的定理是不会形容系统本身的性质的,就像几何学中的定理讲述的是点,线,面等的性质而不是几何的性质。只有有了几何这个整体的概念后我们才会说出几何本身的性质是什么什么。所以直接这么说是不行的,那么就只有来构造一个和这句话等价但是在系统内部可以表示的命题。这就要利用到之前说到的哥德尔配数了。

首先我们要表示不可证这个概念,因为我们已经把系统中各个定理表示成数的形式了,所以每个定理有一个数来表示,并且每个定理的证明过程也能由一串数来表示,就像上次说的4=1+3就可以表示为11110100111,而证明的过程就是把那三步的数连接起来,当然要用一个其他的数分割每个步骤,假设用2吧,则证明过程就可以数字化为11010012111010011211110100111。
于是
(11110100111,11010012111010011211110100111)
就是一个证明对。一对数是否是正确的证明数这个问题是可以在有限的步数内得到证明的,人工的方法无非是将数字翻译回来,在推导中一步一步看下去,看看哪些是公里,哪些不是,对于不是的则可以检查其是否可以从某个规则中推理出来。这样就能证明两个数组成的对是否是一个真的证明对了。这其实就是可证——两个数构成一个证明对,与不可证——两个数无法构成一个证明对的表示。而且由于其可在有限步骤里证明,所以其是可以在系统中表示的。

之后我们要想如何能让定理自己描述定理。书上自创了一个词“摁”,我估摸着作者用这两个字想要表达的意思就是用手把自己融汇并按入到自己里面,所以又是提手旁又是汇又是恩的,这听上去口味有点重啊......撇开口味不谈,摁的前提是有一个至少有一个自由变元的公式,这里的自由变元有点像方程中的未知数,你可以将不同的数代入到那个未知数中。所以在摁的意义下,我们首先计算公式的哥德尔数,之后将这个哥德尔数代入到原来公式的自由变元中,得到的新公式的哥德尔数被称作原哥德尔数的算数摁化。给定两个数,能否在有限步骤中确定一个数是不是一个数的算数摁化?答案是可以,人工做也不难,首先将一个数翻译回原本的公式,之后将其中的自由变元拿刚才的数代替,最后计算出新公式的哥德尔数,将其与另一个数比较,相同则这两个数中一个是另一个的算数摁化,否则则不是。可见这些工作都能在有限步骤中完成,所以算数摁也是可以在系统中表示的。

准备工作就此完成了,我们来构造最后的公式吧:

公式G':不存在 a 和 a' 使得: (1)a 和 a' 是证明对; 并且(2)a' 是 a'' 的算数摁化。

这个公式显然存在一个哥德尔数,我们假设其为 u,随后我们将这公式里的自由变元 a'' (注意 a 和 a' 不是自由变元,它们在公式的开头被提到了)用 u 来代替,则得到

公式G:不存在 a 和 a' 使得: (1)a 和 a' 是证明对; 并且(2)a' 是 u 的算数摁化。

这里,公式G的哥德尔数是什么?G本身是由 G' 摁得到的,G'的哥德尔数是 u,所以由上面的定义,G的哥德尔数就是u的算数摁化

所以,u的算数摁化是存在的,他就是G的哥德尔数,自然,公式G中的(2)是成立的。从字面意义上理解,公式G说得是现象(1)和现象(2)不能同时成立。但是现在现象(2)已经成立了,并且还告诉我们 a' 具体是什么,那么不能成立的事就只可能是(1)了,所以我们可以把公式G重新措辞为:

没有一个数 a 能与 u 的算数摁化形成证明对。

换句话说就是:以 u 的算数摁化为哥德尔数的那个公式找不到一个可以证明其的序列。既然找不到这样一个序列,则以 u 的算数摁化为哥德尔数的那个公式不是系统中的定理。但是回过头来我们想想,“以 u 的算数摁化为哥德尔数的那个公式”是什么?那不就是公式G自己么!所以这句话相当于在说“G不是系统中的定理”,由于G就是它自己,所以这句话等价于:

我不是系统中的定理。

这样,我们就以一个能在系统中表示的公式G,描述了一个我们想要的那个等价的定理。之后的问题就简单了,G是系统中的定理么?如果是,则其是系统中的真理,可是实际上它在说啥?他说自己不是系统中的定理,这样就出现了矛盾。如果不是呢?这倒没有矛盾,但是G的非定理性是由其自己断定的,因而G讲述的是真理,但是G又不是系统的定理,于是我们就找到了一个真理,他能在系统中被表示,但它却不是系统中的定理,完备性的希望就此破灭了。

悲剧啊!

可见任意想到的可以让我们生活的更好的方法最后都被证明了是浮云,世界总是向着混乱不堪飞奔而去,渺小的人类在自然的力量面前是显的得多么的微不足道,就人活动的这点负熵顶屁用啊,QB快来拯救宇宙啊,这泥马越说越悲观了,不过事实也的确坑爹。虽然哥德尔不完备性定理完了,不过这文章应该还有后续,比如说哥德尔第二不完备性定理什么的,还有留给我们的残酷的现实是什么什么的,那么就下次再见吧。

4 thoughts on “GEB读书笔记之四——哥德尔不完备性定理

  1. 看到作者GEB系列的文章,如沐春风,可是到了“摁”之后的证明就完全不懂了,可能是“摁”过程讲的有几分抽象吧。加油

发表评论

电子邮件地址不会被公开。 必填项已用*标注