读后感——《管惟炎口述歷史回憶錄》

回北京的火车上,无聊的我在笔电里乱翻,只想找点东西打发时间。在一个放各种各样我觉得高大上的我看不进去的文档的地方(里面既有 Element of Style, 也有 Gravitation and Cosmology, 等等等等)文件夹中,我发现了一个叫“归档”的子文件夹,创建时间是2010年,我还在上大学的时候。点开看了看才知道这是我不知道什么时候下载的蜗壳中科大的前任校长管惟炎回忆录,他也是方⬤之先生当时的上司,⬤四之后去国,在台湾新竹清华大学教授物理。在火车上因为笔电的电池不够,看的时间比较短,回到北京之后磨磨叽叽又花了几天才看完。因为觉得挺有意思的也算给大家推荐一下这本书吧。

管惟炎先生一身经历极其丰富,出身苏北的一个资产阶级家庭,却又很早跟随共产党参加了抗日活动(毕竟还是抗了三分日的),后来先后在哈工大,清华,北大三所大学念过物理。解放后沦陷后他被选去苏联留学,跟随诺贝尔奖获得者卡皮察(有意思的是,维基说这个人曾经研究过球状闪电,大刘的粉丝应该很容易就能想起那个四米高的白金板吧w)学习低温物理,归国后担任过中科院物理所所长,中国科学技术大学校长。后来因为“不乖”和方励⬤先生一起被免去了职务,六⬤之前的1988年出国访问,⬤四之后也就没有回国,后来被民国政府网罗去,在位于新竹的国立清华大学给学生教授物理。2003年因为车祸去世,享年74岁。

同样是出生于资产阶级家庭,成绩优秀,早年深信共产主义,管惟炎先生却比他的江苏老乡林昭先生幸运了太多。事实上,因为这两人的命运差的太远,导致我花了相当长的时间思考这其中的原因。书中说到,管惟炎先生中学时代作文写的非常好,另一方面,他中学的物理老师也让他对物理产生了浓厚的兴趣。所以在相当长一段时间里,他都在犹豫是学文科还是学理科。权衡之下,他还是选择了物理。这个选择至少在三个方面对他的命运产生了影响:

1. 共产党对于文人的控制和迫害远远超过了科学家和工程师,除了思想控制的需要外,毛泽东本身也是一个重理轻文的人,隔三差五就要找个文人吊上路灯批判一番。而物理所这样的地方则是受到了周恩来不小的保护,文革中受到的冲击也比较小。

2. 因为留学苏联,他错过了反右运动。而林昭就是在这项运动中醒了过来,进而一步步收到迫害。管惟炎觉悟的很晚,或者说他和共产党的割裂也从没有到达过林昭那种程度(大概也是因为他没怎么吃到过苦头吧),在文革中他也就可以说比较少的违心话就能过关。能够在对知识分子摧残最大的两次政治风波中置身事外,幸运女神真的很眷顾他。

3. 在零下271摄氏度的低温下,氦是没有摩擦力的,迷人的物理也让他可以暂时的忘掉人与人之间的摩擦,投入到对低温物理的钻研上去。对他来说,物理学就是一个避风港。去国之后,很多民运人士在异国他乡身无长技,而且在马列主义斗争哲学中浸淫多年,到了自由的土地上不由得“赢得了天空,失去了大地”,过的十分失意。而精于学术的管惟炎先生和⬤励之先生一样,在异国他乡依然可以成为受人尊敬的大学教授,过着体面而充实的生活。在国立清华大学,他还获得过每年由学生推选的杰出教学奖,更是十分不易。

因为在苏联待过很久,管惟炎先生对中苏体制的差异也有比较深刻的见解。就他看来,政治挂帅,政治压倒一切的做法是中国独一份。

李四光的女儿李林有一次到罗马尼亚的一个物理研究所去参观,最后她说,我是党员,你们这应该也有党支部,有党委书记,能不能跟我们交流党的工作经验。他们说,可以。就把她领到一个实验室一位化验员,说他是党委书记。

另外,在苏联,优秀的科学家,艺术家的收入都是相当高的,甚至比斯大林都高。而在大陆,在改革前,占有特权最多,收入最好的显然是那些“外行领导内行”的党委干部们。也难怪苏联被称为苏修,中共简直就是共产党中的共产党。

中科大冬天的暖气,(相对)自由的校风,以及种种让我回想起来就十分舒畅的事物,很大程度上都要感谢这位老校长。事实上管校长在管理学校方面相当有一套,两次科大学生上街游行在他的斡旋之下,都获得了各方面都能接受的(至少安徽省政府和合肥市政府都比较满意,中央的态度从两张撤职令上就能看出来了)结果。中科大在80年代招生上的巨大成功(那时中科大能够招到比北大清华还要多的理科状元)也证明了他出色的管理学校的能力。当然了,你国你党怎么可能因为一个人能力突出就让他平步青云。

最后是一则逸闻:

到台湾的时候有位女记者问管惟炎先生,是不是要争取成为中华民国的公民。他回答说我是比你还要资深的中华民国公民。后来他和马英九提起这件事,马英九回答说,整个中国十二亿人口,都具有中华民国的国籍,只是目前没有台湾的户籍。这件事让管对马的印象很好。(当然了,政治家最会做的就是lip service,众所周知,大陆人想拿台湾户籍那基本是不可能的事情。)

 

GEB读书笔记之六——人工智能

想来想去还是在出国前把这个坑剩下的最后一点填掉吧,自己挖的坑还是要自己填。不过在正式填坑之前我还是要吐槽一下tontyoutoure写的上一篇文章,轻而易举的就成了本Blog评论数最多兼回复/访问比最高的一篇文章了,我才不承认访问这里的都是萝莉控啊可恶,你们都是绅士吗???果然这个世界连打篮球的都全是萝莉了吗???

好吧,下面还是写正文。上次扯完了哥德尔的不完备性定理,这次就开始讲讲逻辑领域最受人关注的一个应用——人工智能。不过人工智能这一块就无法像之前那样能够用严谨的数学推演来得结论了,因为这里并没有什么让人广泛接受的理论,就是最长提到的讨论人工智能能否实现的丘奇-图灵论题都仅仅是一个论题而不是定理,而什么是智能更是七嘴八舌。下棋能够下赢人类机器就算是有智能了么?我前两天心血来潮和简单电脑下了一盘国际象棋还输了呢(可恶,我不是笨蛋啊!),我才不会承认我的电脑智能比我高啊!图灵有一个很出名的图灵测验,大意就是说使用两个分隔开的房间,让测试者用键盘和屏幕与另一边房间的机器交流,如果测试者无法分清对方是机器还是人,那么我们就认为这个机器有智能。当然图灵提出这个测试的时候计算机还啥都不是呢,所以听上去似乎挺有道理的,不过连智力测试机器都能把人干掉的今天也没见到有人承认某个机器拥有智能(多句嘴,你们觉得大萌神算是有智能的机器么?),所以到底什么叫做智能,机器要模拟到什么程度才能实现人类的智能就成了这个地球上最难达成共识的事情之一。

作者在书里写了不少关于智能的层次的问题,并且以DNA和蛋白质作为例子,不过对于满打满算也就是高中学了两年生物的我而言,也就DNA和RNA还算记得,mRNA就只能说是隐约记得,而tRNA则有一种“这是啥?能吃么?”的感觉了。不过作者的意思还算是理解,蛋白质相比于DNA自然是很复杂了,而之上构成的器官已经人本身就更加的说不清道不明了。不过DNA那一套却是出奇的简单,ATGC两两配对,没有什么复杂的不可理解的规则,所以由简单的DNA再往上层层构建的人类能够拥有智能,那么由各种逻辑电路构成的机器为什么就不能拥有智能呢?不过说道这里,就不得不接受这样的质问:“DNA和逻辑电路不是一样的东西!”不过在回答这样的问题前先来听两段音乐吧:

这两首歌一样么?严格来说不是,因为音色很显然不一样,不过我想大多数人会认为这两首歌是一回事。就像我们可以用钢琴来演奏爱情买卖,也可以用Google Doodle来演奏,虽然后者简陋的多,但是没人会否认弹出来的就是爱情买卖。这就是同构,数学里想必这个概念听过不少遍吧。

那么,如果我们肯定了不同的基质是可以达到同样的效果的话,也应该同意机器是可以形成和人一样的智能的。但是这个结论显然不是那么的令人愉快,因为几乎所有人听到这个的第一反应大概都是不爽,并且旋即列出诸多反驳的理由。毕竟机器算是人造出来的,人造的东西和人拥有一样的智能(现就不说有没有可能更强了)总会使人产生“那我算啥”的感觉。

两个最常被人拿出来说的东西就是机器不能有人一样的非理性和创造性。理由很简单,机器是根据程序运行的器件,如果程序没有问题的话机器运行也不会出问题,那么人类偶尔会产生的非理性结论(不小心把2+2算成5)机器是不会出现的。不过,无论是理性也好,非理性也好,这些结论都是我们的大脑得出的,但是如果我们好好考虑一下人类大脑的构造的话,就会发现大脑也是由运行的完美无缺的神经元构成的,神经元的电信号传输也是按照一套规矩运行的,并遵守物理学上的规律,但错误的信念却由这些完美无缺的神经元产生了,这两个东西并不处于同一个层次(如同DNA与蛋白质),正确与错误的确在不同的层次上和平共处了。所以我们并没有理由相信一个完美无缺的计算机硬件不能支持高层次的混乱错误的行为。

至于创造性则要复杂不少,一个人工智能程序想出了一个它的设计者没有想到的一个主意,那么这该归功于谁?程序本身?还是遍程序的人?大部分时候我们认为这不过是编程序的人把这个主意深藏在了程序内部(以至于他自己都没注意到),而计算机只是单纯的使其浮出表面了而已,因为我们在一步一步追踪程序如何得到这个结论的过程中了解了使这个结论产生的原因,并知道这个原因实际上就是编程人员脑内所想的东西,只不过程序把它具现化了。如果什么时候我们没有发现这样的原因,也许我们就能说这个主意是程序自己想出来的了吧。

不过虽然说了些东西,我们还是没法得出一点可令人信服的结论,因为对于人工智能而言,对机器的构造是一方面,对人类自身的理解也是其中必不可少的一部分。而对于后者,哲学家们争论了几千年,结论还是一如既往的不清晰,作者在书里这点也写了不少,但是我想如果要拿来说服人还是不够,很多的东西也只能说是人工智能工作者们所相信的东西,不过不相信的人也不会搞这块了,所以说这些人的说服力有多高也有待商榷。回到自己,小时候曾经想过,要是有个哆啦A梦该多好,后来也有想过,不如我自己造一个吧~虽然现在极度怀疑即使不考虑那些道具的话,哆啦A梦能否在2112年被造出来,但是100年前的人类又如何能想到现在电子计算机的发展呢?所以如果问我机器能实现人类的智能吗?我会说:能。至于如果能的话会不会成终结者那样,就不是我能想像的了。

行了,这个坑就算填完了,我已经不太记得最初是为什么想要挖这么大的一个坑,自己以前也没写过类似的文字,大概行文中的漏洞也一抓一大把吧,如果你发现了,还请不吝指教。我的文笔也不是很有趣,要说作文也是我人生中最最恐怖的噩梦也行,所以,感谢能够坚持看到这里的你,谢谢。

对了,如果你喜欢nyan cat的话,你可以用这个链接来访问这个Blog

GEB读书笔记之五——大萌神与哥德尔第二不完备性定理

Photobucket Pictures, Images and Photos
阿宅们,好好读书啊!

如果你有看过凉宫春日系列的话,应该还记得在《凉宫春日的烦闷》里的 "竹叶狂想曲一章"(话说提到这个我每次的第一反应就是某人在某年七夕很淡定的去校北门拔了一个竹子然后大摇大摆的放回宿舍做许愿竹的事),阿虚受1096的委托和她一起回到了过去,又在老1096的色诱下帮春日在校园里画了一操场的火星文,可惜画完后小1096才发现时光机器不见了以至于回不去了,最后他俩只能去大萌神的家里同床共枕到3年后了(3年间就睡了一次觉,一次睡了3年...不对,可恶啊,阿虚你怎么不去死一万遍啊!)。回来之后的阿虚对时空跳跃的过程感到莫名其妙,就在他在SOS团活动室里胡思乱想这次时空跳跃似乎哪里有问题的时候,大萌神说到:

     相容的系统无法证明自己的无矛盾性

这其实就是哥德尔第二部完备性定理的一种表述,萌神用这句话成功的让阿虚闭了嘴,不过阿虚也不像是真懂了的样子,更像是反正无法理解那就干脆不要理解了的样子。其实这也不能怪阿虚学艺不精,毕竟这玩意也的确不好理解,书上对于证明也是一带而过,只是说和第一不完备性定理思路差不多,并不难证明(好吧,看见“不难证明”这四个字你懂了么?)。我当年上数理逻辑课的时候老师在花了2次课6个课时的时间证明了哥德尔第一不完备性定理后也说由于第二不完备性定理的证明过于复杂所以略去了证明只讲了结论。所以这个定理的证明在这里也只能微讲一下思路了。

哥德尔的证明是在系统的内部构造一个“此系统一致”的句子,之后证明了如果这个句子是系统中的定理,那么同时“此系统不一致”也会是这个系统的定理。然而一旦这两个句子都是系统中的定理,则显然的,系统不相容。这也说明了,除非系统不相容,否则我们没法证明系统是一致的,但是......不一致的系统证明了又有毛用啊,因为在不一致的系统中所有能在系统内表示的句子都是真的,这对我们没有任何用处。就如同虽然你能包含所有的真理,但是也包含了所有的假理,这种东西除了一小撮别有用心的人喜欢拿来骗广大的人民群众外正常人是不会对这种东西感兴趣的。

第二不完备性定理在某些方面看上去有些令人不安,特别是如果你认为一切东西都需要证明才能保证正确性的话。由于哥德尔第二不完备性定理的存在,一个系统的正确性证明只能依赖于另外一个系统,因为自己没办法证明自己。但是这就如同一个一环套一环的锁链,当然可以一步一步的证明下去,不过当证明到这条锁链的一个顶端时我们该如何呢?它的正确性该如何证明?如果不能,我们之前证明的那些又能够算得上可靠么?所以,数学是可靠的么?更进一步,也有人相信这个锁链的最后一环应该是人的理智,所以说,人的理智是可靠的么?

这些论调听上去有些恐怖,毕竟数学无处不在,现代科学又建立在人的理智之上,如果这两样东西都不可信的话那还真的是2012了。不过我倒是觉得大可不必,最好的论据就是我们现在活的很好,几千年都过来了,总体而言没有出什么BUG。数学不可信?我不这么觉的,没有数学怕是我们连可信不可信这个概念都没有,还讨论个屁啊。理智不可信?那我倒想问问不信理智了你信什么?动物的本能?那我们怕是现在还和黑猩猩没有什么区别。所以说真的无法证明?大丈夫萌大奶!几千年的经验告诉我们这些东西还是可以相信的,而且至今为止也没有什么东西看上去比数学更可信,所以大可不必担心啦~你觉得呢?

那么下一篇文章,虽然还有不少东西,但是看上去都已经偏向哲学的范畴了,所以合起来讲吧,颇有些玄妙的东西我也不懂啦......

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快来拯救宇宙啊,这泥马越说越悲观了,不过事实也的确坑爹。虽然哥德尔不完备性定理完了,不过这文章应该还有后续,比如说哥德尔第二不完备性定理什么的,还有留给我们的残酷的现实是什么什么的,那么就下次再见吧。

GEB读书笔记之三——形式系统的完备性和哥德尔配数

上次提到了一个叫pq的形式系统,并且讨论了相容性是什么玩意,那么这次就来讲讲形式系统的另一个重要概念——完备性

还记得我们给pq系统赋予的加法解释么?当时我说这个系统形式化了正整数的加法,那么笼统的说加法行不行?行,但是却不够准确,因为0=0+0这个简单的加法在pq系统里就没有办法表示,更别提非整数的加法了。像这样,如果在某个系统里不能表示我们想表示的所有结论,那么这个系统我们就称其为不完备的。就比如pq系统,其在加法的意义下是不完备的,但是在正整数加法的意义下却是完备的。可见完备与否取也决于我们想让一个形式系统有何等的能力。

那么回到最初的问题,数学家希尔伯特的想法是,弄出一个数学上的形式系统,这个形式系统足够强大,并且是相容的,是完备的,这样我们就可以机械的通过符号上的演算来得出各种定理与结论。由于它足够强大,所以我们可以从中获得非常多的定理。并且由于相容性的保证,我们得出的定理都是真的,又由于完备性的保证,所有我们想要得到的定理我们都可以得到。这大概就是所谓的让所有人的活在新闻联播的世界里的想法。不过希尔伯特提是提出来了,但是据坊间谣传说其本人相比于推导数学更喜欢帮人打官司,特别是遗产官司,这样可以在打完官司后大肆获利一笔。于是他本人并没在这上面花太多心思。不过这种想法听上去还是非常诱人,也吸引了不少人去研究,可惜此等美梦被哥德尔给打破了,哥德尔证明了:当有人活在新闻联播中的时候,必须有另外一群人活在今日说法之中,这就叫一国两制。一个足够强大的系统,不可能同时具有相容性和完备性。也就是说,一个系统如果足够强大,那么要么它能推出所有你想得到的结论,但是随之而来的其必定能推出另外一些你不想得到的——也就是错误的结论。(完备的但是是不相容的)要么其所有的结论都是正确的,但是其却必定不能推出你所有想要得到的所有结论。(相容的但却不是完备的)鱼和熊掌不能兼得。这就像电影社交网络的某个海报上写的那样——You Don't Get To 500 Million Friends Without Making a Few Enemies.

在说哥德尔的证明之前先来问问大家一个问题吧:证明和计算是一回事么?对于我来说,之前一直认为这两件东西不是一回事,就像水和米饭虽然都是吃的但是不是一回事一样。不过哥德尔似乎不这么想,他认为计算和证明差不多,于是就有了哥德尔配数。那么举个例子来说明哥德尔配数是什么东西吧。首先我们来证明 4=1+3是pq系统中的定理:

  1. - - q - p -               公理
  2. - - - q - p - -           推理规则
  3. - - - - q - p - - -   推理规则

这就是4=1+3在pq系统中的证明过程,如果这时我们用0代表q,00代表p,每个横杠用一个1来代表,那么整个证明过程可以写为:

  1. 1101001                     公里
  2. 111010011                 推理规则
  3. 11110100111             推理规则

这个过程可以称之为数字化,而每个字母对应的数字就被称为哥德尔配数。要说明的是,配数的方法是不定的,只要保证一一对应就可以了,也就是说需要每一个数都能够被恢复成原始的字符串。此时我们就可以说证明是由一步步的算数运算得出的了(虽然这个运算的步骤和方法可能看上去莫名其妙)。这样我们就把证明转换为了数字上的计算。

那么在最后进入哥德尔不完备性定理之前,先揪出来一个之前说了无数遍却从没明确过的概念吧:一个足够复杂的系统。这是一个什么样的系统?这里的足够复杂是什么意思?详细的解释会比较麻烦,所以简单点来说就是:当这个系统可以形式化自然数时,这个系统就是一个足够复杂的系统。自然数是一个从小学起我们就开始接触的概念了,想必大家都认为这个很简单。但是即使是这样的系统,也不能做到两全,这听上去还真是可惜。除此之外,我们还要求这个系统里的所有能推出的结论都是一定能在有限步数中能推出的,这个应该好理解,毕竟我们需要这个系统给我们提供结论,如果他提供结论的过程有可能花费无限的时间(无论这个可能性有多低),那么其对我们而言就是没有意义的。另外虽然你可能觉得如果需要1亿年才能提供结论的话,虽说这是有限的,但是也没有意义。话虽如此,我们在这里并不限制推理所用的时间,100亿年也无妨,只要不是无限即可。

那么哥德尔最后就是证明了,下列四点不能同时成立:

  1. 系统足够复杂
  2. 系统相容
  3. 系统完备
  4. 系统的公设集递归

最后一点其实就是说的其推出结论只需要有限步骤,我们在这里用递归来表示有限步骤得结论这个性质。

下一篇就会切入哥德尔定理的证明,通过构造一个自指的命题,来证明希尔伯特的想法是不现实的,那么下次再说吧~