gamecore app logo
本文系用户投稿,不代表机核网观点

一:前言

从下半本书开始,每一个篇章的内容都扩展了很多。之前也有人提过,说内容太过于庞杂,主题繁多看不下去。好吧这只能说是笔者能力有限,没有办法做到让这些内容更加引人入胜。但是书中涉及到的主题恐怕比笔记内提到的还要更多,虽然多却并不是毫无关联的堆砌,而是一个有机的把众多领域联结起来的一个结构。其实这个已经在之前反复提及了,同样的,后半本书的很多主题论述实际上在上半本书里的时候就已经讲过了,后面的内容是进一步的延伸和拓展。
看这本书确实很累,尤其是会前看后忘的情况下,翻这本书就跟翻字典一样了,得返回去看一遍前面的内容,来和当下的内容对上号才行。笔者写笔记的时候也是同样要翻前面的笔记来对照内容,虽然记过笔记稍微有点印象,但还得回去查。
这一篇章的内容感觉有点跳脱,和前面的篇幅内容比,主题突然跳远了。前面两章节还在探讨关于人类大脑和心智的问题,这一篇章却把主题跳跃到了关于数论的内容上面来了。但看似没有关系,实际上却关系紧密。通过前面章节我们对自己的大脑有所了解(了解有限),但我们还是大概看得出来,大脑是一种有限表现无限的形式(其中的关系之错综复杂,前面的笔记已经说了)。这种表现形式可能并不准确和全面,但是确实是可以找到对应的情况——就是数论的证明——你要用一个“有限的”证明去证明出“无限的”自然数性质。
而且关于数论的内容其实早在之前第二章节关于欧几里得的部分的时候就有所提及了——“质数证明”的问题,同样一些内容也在前面的笔记里有所涉略,比如:费马大定理、代数几何、丢番图方程、斐波那契数列等等。
在对话部分,对应的巴赫音乐作品是著名的《哥德堡变奏曲》,然后在阿基里斯和乌龟的探讨中,引入了数论里一个我们耳熟能详的著名“猜想”——“哥德巴赫猜想”(最难的题目终于还是来了)。变奏结合“哥德巴赫猜想”的内容是为了要显示数论当中最困难也是最精妙的一处:“对无穷空间进行探索。”哥德巴赫猜想的困难之处;之前讨论过的欧几里得定理的证明困难之处、包括费马大定理的证明困难之处都已经展示出来了——困难就在于我们如何能够严谨的穷尽“无穷”的证明?
同时,同样一个问题也有很多变体,这是为什么这里要强调“变奏曲”的原因。无穷空间探索要面对的是三种不同的方向:无穷的探索、有穷的探索以及摇摆于两者之间的探索。在对话之后的论述部分,标题给出了的三个词语“BlooP、FlooP、GlooP”是指侯世达教授自己想出来的三种计算机语言。这三种语言正是对应这里说的三种探索证明变奏:BlooP程序只可以进行可预见的有穷搜索、FlooP程序可以进行不可预见的,或甚至是无穷的搜索。GlooP程序则可以进行似有穷、似无穷的搜索。这里的内容像是一个扣子——为后面的内容留下伏笔;可能是图灵停机问题的伏笔(而且好像又能连接到哥德尔不完备性定理上去)。
前两种程序同时还对应两个概念:“原始递归函数”和“一般递归函数”,这两个概念在数论和可计算性理论中非常重要,同时也是哥德尔的证明中的根本性的概念。记得在关于“递归”的那一篇笔记里说过关于“回溯”的问题——递归有两种情况,其一是存在一个“终止”,最终你可以从“梦里”醒来回到“现实”。这就是“原始递归”。另一种情况是,你永远处在梦里,不断地醒来却还是在梦里,这就是“无穷回溯”。“一般递归”就是这样的性质。
而且这两个概念在可计算性理论当中也是非常重要的概念内容,比如“原始递归函数”就会涉及到图灵机计算的内容,而“一般递归函数”则会涉及到图灵完全系统。
当然这会在后面具体地说,还是从对话开始吧。

二:乌龟夜访阿基里斯的“咏叹调及其种种变奏”

阿基里斯这段时间失眠了,似乎被什么问题困扰一直睡不好觉,于是呢,这天乌龟正好找上了门。(夜访)于是阿基里斯就请乌龟陪他解解闷,两位就开始聊天了。阿基里斯说自己试过了世界上最烦人的事情来让自己无聊到睡着,结果压根没有用,于是他打算试试看来讨论数论催眠自己。(感情数论是比世界上最烦的事情还要烦啊23333)
于是乌龟开始和阿基里斯聊起来了,不过他们并不是从数论开始的,而是从一个叫“凯瑟琳”的侯爵的话题开始的。乌龟说:这个侯爵也遇上了和阿基里斯类似的情况,因为某种原因失眠而睡不着觉。于是这位侯爵请来一位音乐家,为自己谱写可以让自己睡着的曲目。于是那位作曲家写作了一首“变奏曲”献给侯爵,这位音乐家自然就是巴赫。而这首“变奏曲”就是大名鼎鼎的《哥德堡变奏曲》,但实际上这首曲子原本叫《咏叹调及其种种变种》。因为当时演奏这个曲子的管风琴乐手叫哥德堡,于是给起了这个名字。
乌龟强调,《哥德堡变奏曲》的种种变调之所以可以保持一致,不是因为旋律相同,而是因为变奏都保持在同一种和声基础之上。在相同基础之上的种种不同变奏,就有了一种内在的“统一性”。然后阿基里斯和乌龟说起《哥德堡变奏曲》一开始人们以为只有三十首“变奏”,但是之后有人发现,在一本特殊的《哥德堡变奏曲》乐谱副本后面,巴赫又留下了一些特殊的“终止之后的终止”,就在乐谱的背面。结果通过这个留下来的“终止”,人们又发现了新的十四首卡农曲。于是《哥德堡变奏曲》就有了四十四首“变奏曲”。
聊到这里乌龟开始把话题引向数论,以《哥德堡变奏曲》为例,最终音乐家们在乐曲结尾之后又发现了原本就保存在“乐曲”当中的新“乐曲”。那么按照普遍性来说,是不是别的乐曲也有类似的情况。你看,我们最后从《哥德堡变奏曲》的结尾发现了整整十四首新的变奏曲,也就是说就算我们知道乐曲是有限的,它一定会结尾,我们也不知道它会在什么地方结尾。(所以也许你可能又找出新的曲子)
这里可以理解为,乌龟把形式系统比喻成了乐曲。而关于乐曲当中找出新旋律,就好像哥德尔不完备性定理下运行的系统一样。即使我们知道形式系统下的定理是有限的,我们也不知道有多少个,所以永远可能需要“打补丁”。而不完备性定理治下的所有“强力”系统,都逃不出这个情况。(注意这里强调“强力”)
阿基里斯:“总数——称之为‘g’吧——肯定是有限的,你同意吧?——可仅仅知道g是有限的并不等于知道g有多大。因此,这一信息无法使我们知道什么时候我们能确定最后一支《哥德堡变奏曲》。
之后阿基里斯问乌龟,巴赫是什么时候写的这首变奏曲,乌龟这里说了一个双关语,它说:“这是1742年的事,那时他在莱比锡当‘康托尔【Czntor】’——就是教堂圣咏班的指挥。”这里强调了“康托尔”,我们知道数学当中的“集合论”就是由一位叫康托尔的俄国数学家和德国数学家理查·戴德金一起发明的。(他们发明的叫朴素集合论,这在第二篇笔记里提到过,因为这里的内容和第二次数学危机有关)
紧接着这个回答,阿基里斯和乌龟就围绕年份这个数字展开了。乌龟告诉阿基里斯:1742这个数字恰好是两个奇素数1723与19之和。阿基里斯一上来被乌龟这么一说,以为这个数字和这个巧合有什么特殊意义。然后他列了一张小表格,然后发现这种所谓的“巧合”,放眼偶数内,这种性质遍地都是,一点都不特殊。阿基里斯表示奇怪,问这其中能有什么显而易见的规律吗?
乌龟说也许找找就能有。(这里已经开始进入关于“哥德巴赫猜想”的内容了)果然乌龟开始顺着数字“1742”接着展开了。这里阿基里斯稍微插了一句,他说他发现1742恰好是两个奇素数的差:1747与5。这里已经暗示了,偶数具有某种性质:既可以被表现为两个奇素数的差(特定范围),也可以表现为两个奇素数的和(也是特定范围)。
然后乌龟接着讲了下去:“……我刚才说到,1742年,有个业余数学家——他的名字我一下子记不起来了——寄了封信给欧拉。欧拉那时正在波茨坦腓德烈大帝的宫廷里……在信里,这位业余的数论爱好者向伟大的欧拉提出了一个为证明的猜想:‘每个偶数都能表示成两个奇素数之和。’这家伙的名字指什么来着?……啊,对了!是‘哥德巴赫’!这家伙是哥德巴赫!”
随后阿基里斯开始听乌龟介绍哥德巴赫猜想的证明历史(很简略的介绍):“已经有了一些值得注意的很接近的结果。比如,1931年俄国数论专家施尼勒曼证明了:任何一个数——偶的或奇的——都能表示成不多于300000个素数之和。
阿基里斯问:“这结果真怪。它有什么用处呢?
乌龟回答说:“这就把问题限制在了有穷领域,在施尼勒曼给出证明之前,有可能当你取越来越大的偶数时,就需要越来越多的素数来表示。没准有什么偶数需要一万亿个素数来表示!现在我们知道了不会有这种事——300000个素数(或更少些)的和就足够了。”(有没有人联想到之前关于“费马大定理”的证明过程?是不是有很类似的地方?都是逐步缩小范围,最后不断地逼近然后终于得到了证明。)
乌龟接着说了下去:“后来,1937年,一个名叫维诺格拉多夫的狡猾家伙——也是个俄国人——设法建立了一个与期望目标接近得多的结果,就是:每个足够大的奇数都可以表示成不多于三个奇素数之和。例如,1937=641+643+653.我们可以把能表示成三个奇素数之和的奇数称为具有‘维诺格拉多夫性质’的数。这样,所有足够大的奇数都具有维诺格拉多夫性质。
阿基里斯问道:“很好——可‘足够大’是什么意思?
乌龟回答:“意思是说,有数量有限的某些奇数也许不具有维诺格拉多夫性质,但会有一个数——称之为‘v’吧——大于它的所有奇数都是具有维诺格拉多夫性质的,不过维诺格拉多夫无法确定v有多大。所以某种意义上说,v就像g,那个有限的、但不知道多大的哥德堡变奏曲数目。仅仅知道v是有限的并不等于知道v有多大。因此,这一信息无法使我们得知什么时候我们能确定最后那个需要由多余三个奇素数来表示的奇数。
这里就是涉及到数论的很深的内容了,当然说是说“深”,其实也就是一个说法。数论的本质就是对于“数”的研究,“数”的关系和性质,用算术的方式来表示。很多人对于数论都很难提起兴趣,与其说是太难了,不如说是太无聊了——找不到实际的意义。当然学这方面的人肯定有不同的看法,但至少对于没有入门提起兴趣的人来说,要看“数论”确实是需要极大耐心的。
这里笔者可以给出一个自己的看法,数论中表现的关于“数”的种种性质,互相之间的关系。就好像是我们生命中很多“巧合”,有说命该如此、或是单纯的巧合、或是上帝掷色子……但不管怎么说我们都会赋予其“意义”,去试图解释这些“巧合”——因为存在既是合理。我们如果用同样的看法来看待数论,也许可以让我们发现其中的那些乐趣。(不知道多少人看过金·凯瑞的《灵数23》)那我们继续来看看阿基里斯和乌龟诉说的,关于哥德巴赫猜想的证明过程。
阿基里斯总结:“我明白了。于是任何足够大的偶数2N都能表示成四个素数之和,因为可以先把2N-3表示成三个素数之和,然后再添上素数3。
乌龟:“正是如此。另一个角度的研究得出了一个很接近的结果,它是这样一个定理:‘任何一个偶数都可以表示成一个素数和另外一个数的和,后者是至多两个素数的积’。
乌龟和阿基里斯聊的这些内容实际上就是哥德巴赫猜想的种种变奏版本,不看两个素数之和,那么来看看两个素数之差。阿基里斯列了一个偶数表示成两个奇素数之差的列表,结果发现这个列表是无限的,而且紊乱无序,至少表面上看不出什么规律来。
乌龟:“你是不是认为每个偶数都能以某种方式表示成两个奇素数之差?
阿基里斯:“从我的表来看,回答当然是肯定的。不过我仍然可以假定回答也可能是否定的。这并没有真的使我们走得太远,是吧?
乌龟:“这里有很多值得注意的方面,我说的是在这个问题上会有更深入的洞见。
阿基里斯:“真奇怪,这个问题和哥德巴赫原来的那个问题这么想像。也许该称之为‘哥德巴赫变奏’。
乌龟:“……我们假设:如果一个偶数是两个奇素数之和,就是具有‘哥德巴赫性质;而如果它是两个奇素数之差,则具有‘乌龟性质’……如果一个数不具有乌龟性质,则我们就说它具有‘阿基里斯性质’。”(这里阿基里斯建议乌龟把“哥德巴赫性质”换成“阿基里斯性质”,因为是自己先提出来的,可能是为了便于读者区分这个问题——当然估计很多人到这里就已经被绕晕了)
乌龟:“现在想一想,比如说,一万亿是否具有哥德巴赫性质,或具有乌龟性质?当然,它也可能两者兼备……假如我是问你其中一个问题,前一个或者后一个,你会选择哪个问题去考虑?
阿基里斯:“我想我会扔一枚硬币。我没看出两者有什么差别。
乌龟:“这可有天壤之别啊!如果你选了哥德巴赫性质,说的是素数之和,那么就仅限于使用那些介于2和一万亿之间的素数。对吧……因此,你为一万亿找一个两个素数之和表示这一过程是注定会终止的。
阿基里斯:“啊!我知道关键所在了。要是我选择把一万亿表示成两个素数之差,涉及到的素数就会没有个头,有可能大到要花一万亿年才能找到它们……如果它们不存在,那么搜索过程就会永远进行下去,永远不作肯定答复,也不作否定答复。然而尽管如此,其答案是否定的。
在这里笔者收缩了一下乌龟和阿基里斯的对话,感觉内容更加集中一点,而到这里我们似乎可以回溯之前的两个形式系统游戏了:WJU形式系统和pq形式系统。所以关于“有穷搜索”和“无穷搜索”的内容其实早就在开篇就已经做了铺垫了。
乌龟:“所以,如果你有了某个数,想测试一下它是否具有哥德巴赫性质或乌龟性质,两种测试的差别就在于,前者涉及的搜寻过程是注定会终止的,而后者则有可能是无穷尽的——没有任何保证。它会无休无止、没完没了,永远给不出一个回答。然而另一方面,在某种情形下,它或许会在第一步时就停住了。
……那两个相似的问题就是关于这两个极为不同的性质的。哥德巴赫猜想如成立,则所有偶数具有哥德巴赫性质;哥德巴赫变奏如成立,则所有偶数具有乌龟性质。两个问题都还有解决,但有趣的是,虽然它们看起来很相像,它们涉及到的确实有关全体整数的极为不同的性质。
阿基里斯:“我明白你的意思。哥德巴赫性质对于任何一个偶数来说是可检测的,或者说是可识别的性质,因为我知道怎样测试它是否存在——进行搜索就是了。这个过程必定会到达一个终点,并给出肯定的或否定的回答。而乌龟性质则难对付多了,因为盲目的搜索可能会永远给不出回答。
数论最让人感到没有耐心的地方(可能主要对于没有接受过专业训练的人来说),在于其对于逻辑严谨的要求,当然其他理科领域也有一样的要求(这种严谨是数学的基本,而数学又是其他科学的重要基础,这就不言而喻了)。逻辑要严谨,则要求在公理基础之上进行的每一个推理的步骤都必须要严格遵循规则来,这在介绍形式系统的时候就说过了。而困难的地方就在于,严格遵守推理规则的证明步骤往往会和巨大的甚至于“无限”的工作量有关系。这也是我们的思维很容易对这类工作产生疲劳的原因,我们的思维往往会凭借直觉直接跨过步骤。
所以反过来说,数论的证明工作要保持如此严谨的逻辑证明的前提下,还要面对可能是“无限”的验证步骤。最重要的就是首先划分范围(概念上):不论是“哥德巴赫猜想”,还是前面关于“费马大定理”的证明。我们都看到了,我们首先要做的就是把这个问题的性质证明出来——“是否可以有穷证明”,然后再逐步的缩小范围。以前面费马大定理的证明来看也是差不多情况:先证明其在一些特定情况下是否成立,然后在此基础上不断扩大范围,最后在过程中获得了启发,通过另一种可以”有限证明“的方式,验证了这个定理。(关于哥德巴赫猜想的内容则在后面会详细说说)。
乌龟和阿基里斯在这里讨论的就是类似的情况,对于”猜想“本身我们一时间可能束手无策,那么就先找找类似问题的解法来给自己寻找启发。(这是比较通俗的说法)
那么上面这个说的例子是对于”肯定“答案的情况,”否定“的答案如何证明呢?(无法证明,则可以证伪,反之也如此,而只要结果出来之前,就不下定论)
乌龟:”也许对于乌龟性质会有一些更聪明的搜索办法,按照其中的一个办法做下去总能到达一个终点,并给出回答。
阿基里斯:”难道这一搜索不是仅仅在答案是肯定时才会终止吗?
乌龟:”那倒不一定。没准儿会有什么办法证明:一旦搜索的时间超过某一限度,回答就必定是否定的。甚至也可能会有某种其他的搜索素数的办法——而不是这种盲目的方法——能在该性质存在时发现它,而若是不存在,也能给出回答。任何一种情形下否定的回答都只需有限的搜索。可我不知道这种事情是否能被证明。在无穷的空间里进行搜索总是很难驾驭的,这你也知道。“(这里其实已经可以涉及到图灵的”停机问题“了,后面的章节会专门涉及这个内容,因为图灵的”可计算理论“是计算机科学里非常重要的一块内容)
阿基里斯:“所以就目前来看,你知道对乌龟性质来说还没有注定会终止的测试——然而没准儿还是会有这样一种搜索。
乌龟:“对。我可以设想某人从事对这种搜索的搜索,但我同样不能保证这个‘元搜索’会终止。
阿基里斯:“这种怪异的情况给我的印象太深了,某个偶数——比如说一万亿——没能具有乌龟性质,竟是由无穷多支离破碎的信息所导致的。想想也挺有趣,把这些信息都卷在一起打成捆,称之为——就如你仗义的龟兄所说的——一万亿的‘阿基里斯性质’。它事实上是作为整体的数论系统的一个性质,而不只是属于一万亿这个数的。
阿基里斯这里提到的思路,可以联想到之前的“组块化”,不是以低层次的个体来进行证明(工作量太大以至于无法完成)。而是以高层次的概念——“通用性质”来进行证明。(比如不是一个一个数字列出来,而是假设:N是奇素数,则2N是偶数……那我们需要证明的就不是每一个奇素数或偶数,而是只需要证明N和2N的性质就足够了。)
乌龟:“这是个很有意思的见解,阿基,不过我还要补充一点,把这一事实与一万亿这个数联系在一起是很有意义的。为了能说明这一点,我建议你考虑一个简单的陈述:‘29是一个素数’。好,事实上这个陈述确实就意味着2乘以2不等于29,5乘以6不等于29,如此下去,对吧!
但是你把这些事实搜集起来,打成捆,并与29这个数联系起来,仅仅说上一句,‘29是素数’?
阿基里斯:“是的……
乌龟这里似乎突然顾左右而言它,阿基里斯表现得也有点懵,但随后乌龟就点名了自己想说的意思:“……但是你想想:两个大于29的数的乘积不可能等于29这一事实涉及了全体整数系统结构。在这种意义下,那事实本身就概括了无穷多的事实。你不能逃避这一事实,阿基,当你说‘29是素数’时,你实际上表述了无穷多的事情。
阿基里斯:“也许是吧,可我觉得它像是单单一个事实。
乌龟:“那是因为有无穷多的事实已经包括在你预先拥有的知识里了——它们隐含地嵌在你看待事物的方式中。你没有看到明显的无穷,是因为它已在你把握的图像中被隐含地捕获了。
对于一些我们常识中不言而喻的事情,我们往往不会去深想。然而类似数论这类的深度学科恰恰需要反其道而行之,这也是为什么外行人接触这类领域会被阻挡在门外。而且以乌龟所说的为例,我们似乎可以发现,几乎所有的事物都有着:“一即全,全即一”的性质(一个个例包含着无穷个引申事实,哪怕关系上没有那么近,但它们却是在逻辑上被联系着)。
乌龟:“也许看起来怪点儿,可这也是看待事物一种相当便利的办法。现在我们还回到你那个假设性的想法。如果像你所说的,一万亿这个数具有阿基里斯性质,那么不论你把它加上什么样的素数,你都不会得到另一个素数。这种状况会由无穷多个别的数学‘事件’所导致。那么所有这些‘事件’是否必须都是出自同意来源?它们是否必须有共同的缘起?因为若不是这样,那些事实就是由某种‘无穷巧合’造成的,而非背后的规律性。
阿基里斯当然不同意乌龟的说法,他认为数论当中是不存在什么“无穷的巧合”的,没有任何事情不是出自于背后的某种规律。随后阿基里斯找了一个范围比较小的例子试图说明他的看法,不过被乌龟给质疑了一下。严格来说阿基里斯不是错误的,但是却也不完善。
阿基里斯:“难道还有人不同意这个观点吗?那么这种人就必然要相信‘无穷巧合’了,他们必然相信在人类创造物种最完美、最和谐、最漂亮的部分——自然数系统——当中,也有紊乱。
乌龟:“也许他们就是这样,可你是否想过,这种紊乱或许是美与和谐的不可分割的组成部分?
阿基里斯:“紊乱,完美的一部分?秩序与紊乱构成了悦人的整体?真是异端邪说!
乌龟:“据说你最喜欢的艺术家埃舍尔就在一幅画里暗示了这种异端观点……说起紊乱这事,我相信你会有兴趣听听两类不同的搜索,两种搜索都保证会终止。
阿基里斯当然有兴趣,于是乌龟接着说了下去。
第一类搜索——非紊乱型的搜索——可以用一个关于哥德巴赫性质的测试来说明。你只需看那些小于2N的素数,如果某一对素数加起来得到2N,那么2N就具有哥德巴赫性质,否则就不具有。这种测试不仅注定会终止,而且你还能预先知道什么时候终止。
阿基里斯:“那么这是个可预知其终止的测试喽。你是不是要告诉我检验某些数论性质时,要用到那种虽然保证会终止,但预先无法知道会过多久才终止的测试?
乌龟:“你预见的太对了,阿基,这种测试的存在就说明自然数系统从某种意义上说带有固有的紊乱。
阿基里斯:“这种情况下,我只好说人们还不够了解那个测试。如果他们多做些研究,他们会弄清在终止前那个测试至多要花多少时间。无论如何,整数中的模式必定是有来由的,不可能只是一些无法预知的紊乱模式。
乌龟:“我可以理解你这种直觉信念,阿基。不过,这一点并非总能得到证实。当然,很多情况下你是绝对正确的——仅仅因为某人不知道某事,不能得出结论说那件事不可知。可是有那么一些整数的性质,可以证明检验它们的有终测试是存在的,同时还能证明没有办法预先知道那些测试要花多少时间。
这里在重点强调的一个部分就是:证明当中的“不可知”部分。虽然这个所谓的“不可知”,只不过是我们不知道证明多久才能结束——也就是说我们并不知道证明一直到结束当中存在着“多少”步骤。这和前面反复强调的我们不知道多少“中间层次”多多少少可能是有一些对应的。但是要注意,这里的不可知仅仅是我们没有“全局结构”的了解,我们虽然不知道有多少“中间层”,但是每一个单独层次我们还是能明白的;同理,这样的证明里面,随便一个单独的证明步骤我们是很清楚的。
乌龟:“……我来跟你说一个很容易定义的性质,然而却还没有一个检验它的有终止测试。我没说永远不会发现这样一个测试,这一点请你注意——只是现在还没有。我们从一个数开始吧——你来选一个数。
阿基里斯:“15怎么样?
乌龟:“很好。我们从你这个数开始。如果它是奇数,我把它乘以3,再加1。如果它是偶数,就取其一半。然后重复这个过程。如果一个数经过这样的一些操作得到1,就称之为‘妙极’的数,否则就称之为‘非妙极’的。
这里我们并不是在通过所谓的“测试”来了解一个数学规则,恰恰相反,这里我们是借由数学规则来感受一下这个“证明步骤”,值得注意的是重点何在,重点不在于我们说的内容,而是这个“证明”形式本身,这是非常重要的,否则这段内容看起来就会不知所云。
书里这段证明如下:(有十六个步骤,就不打出来,直接上图吧,这样也跟直观一些)
乌龟:“你注意了没有,再这么简单定义的运算下,那些数是怎样上下摆动的?
阿基里斯:“注意了。特别让我吃惊的是,经过十三次运算后,我得到16,仅比我起步时的15大1.在某种意义上说我几乎回到了出发点——而在另一种意义上,我已远离了出发点。另外还有一点使我诧异的是为了解决问题,我不得不动用大到160那样的一个数。我真想知道这都是为什么。
乌龟:“是的,有个无穷的‘天空’供你飞,而且事先很难知道你会被抛到这天空里多高的地方。而且很可能你会只是不断地往高飞,越来越高,再也不下来了。
重点在于,当我们讨论一个问题的时候,它是关于“形式”的问题还是关于“性质”的问题?如果是后者,它的麻烦程度恐怕就要超出想象了。因为抽象的问题从来都不受“形式”的规范,而当我们平时一般在思考这类问题的时候,之所以能够有“终止”是因为我们在自己没有意识到的部分(常识部分)已经给出了形式限定。
所以当中这些“步骤”其实已经被我们的大脑跳过了,这样类似的情况其实早在最早的WJU形式系统游戏里就已经提到过了——U方式(总结归纳,然后跳过一些步骤直接走向“搜索终止”)。而现在当我们在做这个当下的讨论的时候,我们思考我们自己的“思考”方式,这就呈现出来这种我们觉得完全无序,又觉得背后有点什么的朦胧感觉中了。(自指状态下,到处都是这种感觉,就像我们为什么会觉得“悖论”还是有意义的)。
阿基里斯:“我想你是对的。这个‘妙极’问题真是奇妙至极了,就看那些数的摆动方式吧——一会儿增大,一会儿减小。模式应该是有规则的,可是表面上却显得相当紊乱。所以我完全能想象为什么至今还没有一个检验妙极性质的有终止测试。
乌龟:“说起有终止过程和无终止过程,还有那些介于两者之间玩意儿,我想起了我的一个朋友。他是个作家,正在写一本书。”(乌龟这里说的朋友,其实指的就是侯世达自己,不过在对话里用了一种幽默的方式来自指自己这本书——《金、银、铜——聚宝藏之精华》……);注意这里给出了一个“自指”(在这GEB本书的内容里讨论GEB这本书本身)。
阿基里斯:“……可我们的讨论怎么会让你想起他的那本书了?
乌龟:“啊,是这样。那本书里有篇对话,在其中他想让读者去搜索终了,从而甩掉读者。
阿基里斯:“竟会有这种愿望,够奇怪的。这怎么做到呢?
乌龟:“你无疑会注意到,一些作者在他的故事结束前的几页里如何费尽心机地建立起巨大的紧张状态——可是那个把书捧在手上的读者能感觉出故事就要结束了。所以,有某种额外的信息以一定的方式预先提醒了读者。书的物理性质多少有点破坏了那种紧张。如果,比如说,在小说的终了处有许多废话,那就会好多了。
记得前面提到的哥德堡变奏曲关于那个“终止式”的讨论吗,之后人们发现老版本哥德堡变奏曲的终止之后还能找到未尽的变化,并且通过“终止式”进一步演变出来了好几个变奏(漫画《风云》里剑圣的剑二十二衍化出剑二十三?)乌龟这里说的就是这个了——而对应到他们在讨论的是否有终止的搜索上来看,这样的情况就对应了前面提到的“摇摆于有终止和无终止之间的搜索”。
乌龟:“对。我的意思是,有许多多余的书页,不是故事的真正组成部分,但能用来藏住终了,使得草率浏览或只凭对书的物理感觉都无法确切地得知终了在哪里。”(也许有时候作者故事写完了,读者读完却总是觉得意犹未尽,希望故事还能继续——DLC、番外篇。当然这个其实和乌龟说的没什么关系了,只是一点额外的联想。)
阿基里斯:“我明白了。这样的话,故事的真正终了可能会出现在,比如说,书的物理终了前五十页或一百也了?……如果这能广为实践,会是很有效的。可是有个问题:假如这些废话非常明显——比如有许多空白,或者有充满句号或满篇杂乱无章的字词的书页,那还不如没有……可是一般来说即使草率地浏览正常的一页书也足以把一个故事同另一个故事区分开来。所以你必须把那些废话弄得与真正的故事非常相似。
乌龟:“没错。我的设想是这样;把故事讲完后不中断,继续讲下去,讲一些看上去是该故事的继续,而实际上只是些废话,与真正的主题毫无关系的事。某种意义上说,这些废话是种‘终了后的终了’,带有与原主题几乎无关的多余的文学意象。
阿基里斯:“真够狡猾的!可这就有个问题;你无法弄清真正的终了到底在哪儿,都混在废话里了……哎,我有个建议。可以把从真正的故事到废话部分的转折做成这样:一个有智能的阅读者对正文充分专注仔细地审查之后,能查明什么地方是前者的结束、后者的开始。也许这会使他花费相当的时间。也许没有办法预先知道到底要花多长时间……但出版者能够保证对真正终了的一个充分专注仔细的搜索一定会终止,即使他无法在其终止前说出到底要花多少时间。
这里一段阿基里斯在和乌龟探讨关于故事的终止,前面已经提醒了,这个“终止后的终止”在前面提到的哥德堡变奏曲的时候就已经提到了。但这里如果仅仅是做形式上的对应的话就毫无意义,这里使用的写作方式和前面使用地图比喻大脑的写法是一个样子——就是一个比喻,阿基里斯和乌龟讨论的股市的写作,这个故事就是比喻“搜索”:有明确结局的故事就是“有终止的搜索”、没有明确结局的故事就是“没有终止的搜索”而阿基里斯他们说的这种结尾之后意犹未尽的故事就是“介于终止和无终止之间的搜索”
对话到这里主题看起来就结束了,但是实际上并没有。很明显侯世达想在形式上和内容上完全对应起来。原本乌龟和阿基里斯聊到这个关于“搜索”的“故事”比喻之后就打算结束对话了,但后面还是多写了一段多余的内容——“终止后的终止”。
乌龟打着哈欠准备回去了——他们原本是因为阿基里斯失眠,才开始聊关于“数论”的各种搜索的复杂问题为了打发时间的。阿基里斯为了像乌龟表示感谢,感谢它给自己陪聊,打算送给乌龟一个礼物。那个礼物是一个包包,阿基里斯说是一个珍贵的用“变造革”(不是人造革)做的包包。(这里还隐射了一下康托尔的对角线方法的内容)。
结果乌龟刚收下,警察就冲进来了,说是博物馆失窃了一个“变造革”做的包包,一路找到了这里来。结果乌龟就倒霉的被逮起来了,阿基里斯乘机甩锅——感情他这段时间失眠是因为做贼心虚啊……

1·变奏曲
变奏曲是一种乐曲的结构形式,在一个乐曲的主题之后,紧接着将主题进行变化,而变化之后依然可以让人认出原来的主题。这种变化可以产生在和声、旋律、对位、节奏上,也可以由不同的配器方法在音色上求变化。这种变化就是主题变形,或叫“变奏”。变奏的次数不固定,可以变奏任意多次。曲式发展如:A(主题)+A1+A2+A3+A4……
变奏曲是一种古老的经典作曲方式,在一个主题上连续写一系列器乐变奏的做法,最早出现于16世纪的西班牙琉特琴曲。16世纪晚期和17世纪初期的英国作曲家写维吉那琴曲也用类似的方式作曲,当时所选的主题大多为流行歌曲。从那时起,“主题与变奏”一直是一种标准的曲式。到了后来,主题的选用除了当时的流行歌曲之外,也还会借用其他作曲家的“主题”——名称上会标出。
变奏即可用于奏鸣曲和交响乐其中的一部分,后来也可以作为独立的器乐曲作品。17世纪有人写变奏组曲,其中几个舞曲乐章有主题上的联系,实际上也就是建立在一个基本旋律上的一段段变奏。18世纪后期以来,变奏曲常用作奏鸣曲、交响曲一类作品的一个完整的乐章。从广义来说,变奏是一切交响乐写作不可或缺的要素。一个或几个主题的展开便是将素材本身固有的各种可能性付诸实现,这本身就是一种变奏。
变奏曲中可以找到这样一些基本要素:旋律变奏、音型或织体变奏、节奏变奏、调性变奏(如小调换大调或者反之)以及和声变奏。同一段变奏中又可将几种要素或全部要素结合起来。但是,变奏的艺术比仅仅利用这些基本类型要复杂得多,更重要的是把主题作为灵感的源泉,从中引申出各种初看似乎与主题关系不大的联想。如何由此及彼,不应着眼于表面,而应该发自作曲家的想像。
巴洛克音乐时代比较著名的变奏曲有巴赫的《哥德堡变奏曲》,亨德尔的《和谐的铁匠》系列。
在古典音乐时期,莫扎特写了大量的变奏曲,莫扎特习惯在变奏曲的倒数第二乐章时让节奏变慢,然后在最后一个乐章突然加快,并常用华彩即兴演奏的形式;其中最有名的即为小星星变奏曲。海顿喜欢用双变奏的形式,即用两个相关的主题,一般一个是大调式另一个是小调式,互相进行变奏。
贝多芬一生也写过不少变奏曲,有的在他的大型乐曲中应用,如《第三交响曲》的最后部分,《第十二钢琴奏鸣曲》的开始部分,他最后一部《第32号钢琴奏鸣曲》的第二部分等
舒伯特写过5部变奏曲,最著名的是《死神与少女》弦乐四重奏,他的著名作品《鳟鱼》钢琴五重奏也包括对他自己创作的歌曲《鳟鱼》的变奏。
浪漫主义音乐时期变奏曲形式更为重要,但一般作曲家不再单独写变奏曲,但勃拉姆斯的《亨德尔变奏曲》表现了他对古典主义音乐的偏爱。
20世纪又流行单独的变奏曲,韦伯、布里顿、保罗·欣德米特等人都写过独立的变奏曲套曲。
有经验的音乐家经常可以即兴演奏变奏曲,在巴洛克音乐时期非常普遍,尤其是慢节奏的主题,可以使演奏者不断地在变奏过程中完善主题。古典主义音乐时期也回即兴演奏变奏曲,贝多芬的作品第77号《G小调幻想曲》几乎就是一个小主题在他即兴演奏后记下的乐谱。莫扎特的许多作品也是即兴演奏后完善的。 即兴演奏完善变奏也是爵士乐的主要创作方法。
变奏的一大要素是加工雕琢,因此为独奏乐器写的变奏曲(为室内乐重奏和乐队写的也一样)必然要求精湛的演奏技巧。一些作曲家为发挥演奏技巧而热衷于创作变奏曲。贝多芬探索以更加难以捉摸的方式赋予主题以新面貌。门德尔松的《严肃变奏曲》实际上是为了抗议,19世纪初像许多作曲家运用这一形式写作内容空洞的音乐。到了后来的作曲家,如勃拉姆斯和埃尔加的变奏曲已远非炫技之作,里面包含了更多的内涵。

2·关于数论

数论在前面已经提到过了(不止一次,而且还有一些具体的例子),但是为了后面的内容这里还是多嘴再说一句,这里就直接引用维基百科的内容吧:
数论是纯粹数学的分支之一,主要研究整数的性质。被誉为“最纯”的数学领域。
正整数按乘法性质划分,可以分成质数,合数,1,质数产生了很多一般人能理解却又悬而未解的问题,如哥德巴赫猜想,孪生质数猜想等。即,很多问题虽然形式上十分初等,事实上却要用到许多艰深的数学知识。这一领域的研究从某种意义上推动了数学的发展,催生了大量的新思想和新方法。数论除了研究整数及质数外,也研究一些由整数衍生的数(如有理数)或是一些广义的整数(如代数整数)。
整数可以是方程式的解(丢番图方程)。有些解析函数(像黎曼ζ函数)中包括了一些整数、质数的性质,透过这些函数也可以了解一些数论的问题。透过数论也可以建立实数和有理数之间的关系,并且用有理数来逼近实数(丢番图逼近)。
数论早期称为算术。到20世纪初,才开始使用数论的名称,而算术一词则表示“基本运算”,不过在20世纪的后半,有部分数学家仍会用“算术”一词来表示数论。1952年时数学家Harold Davenport仍用“高等算术”一词来表示数论,戈弗雷·哈罗德·哈代和爱德华·梅特兰·赖特在1938年写《数论介绍》简介时曾提到“我们曾考虑过将书名改为《算术介绍》,某方面而言是更合适的书名,但也容易让读者误会其中的内容”。
卡尔·弗里德里希·高斯曾说:“数学是科学的皇后,数论是数学的皇后。”
数论初期的铺垫工作有三大内容
欧几里得证明素数无穷多个。
寻找素数的埃拉托斯特尼筛法;欧几里得求最大公约数的辗转相除法。
公元420至589年(中国南北朝时期)的孙子定理。
以上工作成为现代数论的基本框架。
数论中期工作
在中世纪时,除了1175年至1200年住在北非和君士坦丁堡的斐波那契有关等差数列的研究外,西欧在数论上没有什么进展。
数论中期主要指15-16世纪到19世纪,是由费马、梅森、欧拉、高斯、勒让德、黎曼、希尔伯特等人发展的。最早的发展是在文艺复兴的末期,对于古希腊著作的重新研究。主要的成因是因为丢番图的《算术》(Arithmetica)一书的校正及翻译为拉丁文,早在1575年Xylander曾试图翻译,但不成功,后来才由Bachet在1621年翻译完成。
早期的现代数论
费马:皮埃尔·德·费马(1601–1665)没有著作出版,他在数论上的贡献几乎都在他写给其他数学家的信上,以及书旁的空白处。费马的贡献几乎没有数论上的证明,不过费马重复的使用数学归纳法,并引入无穷递降法。
费马最早的兴趣是在完全数及相亲数,因此开始研究整数因数,这也开始1636年之后的数学研究,也接触到当时的数学社群。他已在1643年研读过巴歇版本的丢番图著作,他的兴趣开始转向丢番图方程和平方数的和。
初等数论
意指使用不超过高中程度的初等代数处理的数论问题,最主要的工具包括整数的整除性与同余。重要的结论包括中国余数定理、费马小定理、二次互反律等等。
解析数论
借助微积分及复分析的技术来研究关于整数的问题,主要又可以分为积性数论与加性数论两类。积性数论借由研究积性生成函数的性质来探讨质数分布的问题,其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。加性数论则是研究整数的加法分解之可能性与表示的问题,华林问题是该领域最著名的课题。此外例如筛法、圆法等等都是属于这个范畴的重要议题。
代数数论
引申代数数的话题,关于代数整数的研究,主要的研究目标是为了更一般地解决不定方程的问题,而为了达到此目的,这个领域与代数几何之间有相当关联,比如类域论(class field theory)就是此间的颠峰之作。
算术代数几何
研究有理系数多变数方程组的有理点,其结构(主要是个数)和该方程组对应的代数簇的几何性质之间的关系,有名的费马最后定理、莫德尔猜想(法尔廷斯定理)、Weil猜想,和千禧年大奖难题中的贝赫和斯维讷通-戴尔猜想都属此类。
几何数论
主要在于透过几何观点研究整数(在此即格子点)的分布情形。最著名的定理为闵可夫斯基定理。
计算数论
借助电脑的算法帮助数论的问题,例如素数测试和因数分解等和密码学息息相关的话题。
超越数论
研究数的超越性,其中对于欧拉常数与特定的黎曼ζ函数值之研究尤其令人感到兴趣。
组合数论
利用组合和几率的技巧,非构造性地证明某些无法用初等方式处理的复杂结论。这是由保罗·埃尔德什开创的思路。
模形式
数学上一个满足一些泛函方程与增长条件、在上半平面上的(复)解析函数。
——摘自维基百科‘数论’词条。”

3·康托尔的对角线论证

康托尔的名字早在第二篇笔记的时候就出现过了,他是数学历史上地位举足轻重的人,因为就是他发明了“朴素集合论”为当今数学体系开创了基础。当然作为奠基者,遭遇挫折也是必然的,康托尔的集合论遭遇了“悖论”,所以后面才有了进一步的发展,更加严谨的现代集合论在试图解决一些问题,当然有些问题到今天还没有完全解决完。
这里提到康托尔不是完全没有道理的,对角论证法是乔治·康托尔于1891年提出的用于说明实数集合是不可数集的证明方法。这样一来我们直接就明白了为什么这里要提康托尔的对角线论证了,就像我们在面对的论题一样——“对于无限空间的探索”。
对角线法并非康托尔关于“实数不可数”的第一个证明,他的第一个证明既未用到十进制展开也未用到任何其它数系。最早的原始证明发表于 1874年,这个证明使用了较为复杂的归纳反证法。1891年他用对角线法重新证明了这个定理。
康托尔提出了通过一一对应的方法对无限集合的大小进行比较,并将能够彼此建立一一对应的集合称为等势,即可以被认为是“一样大”的。他引入了可数无穷的概念,用来指与自然数集合等势的集合,并证明了有理数集合是可数无穷,而实数集合不是可数无穷,这表明无穷集合的确存在着不同的大小,他称与实数等势(从而不是可数无穷)的集合为不可数无穷。
这里涉及到一些集合论的概念,必须要先了解一下,才能明白康托尔的对角线论证是在干什么。首先是“可数集”这个概念(先明白“可数集”才能明白康托尔证明的“不可数集”):在数学上,可数集,或称可列集,是与自然数集的某个子集具有相同基数(等势)的集合。在这个意义下,可数集由有限可数集和可数无穷集组成。不是可数集的无穷集称为不可数集。这个术语是康托尔创造的。可数集的元素,正如其名,是“可以计数”的:尽管计数有可能永远无法终止,集合中每一个特定的元素都将对应一个自然数。
等势在数学领域中,是指如果两个集合A和B是等势的,那么这两个集合之间存在一个双射——这个双射简单来说就是两个集合之间的元素存在唯一对应的情况:也就是集合A映射至集合B,则每一个集合A内的元素a,存在唯一一个在集合B内的元素b与其对应。值得一提的是:在抽象代数中,保持结构的双射关系可以叫——“同构”。)
可数集”这个术语有时也指代可数无穷集,即仅代表能和自然数集本身一一对应的集合。两个定义的差别在于有限集合在前者中算作可数集,而在后者中不算作可数集。为了避免歧义,前一种意义上的可数有时称为至多可数,后一种可数集则称为无限可数集。
可数无穷,是指集合中的元素可以与自然数一一对应,也就是说可以用自然数来"数"它的数量,从而其数量为可数无穷。
比如说:整数的全体可以和自然数一一对应;偶数的全体可以和自然数一一对应;奇数的全体可以和自然数一一对应;同样,有理数也可以和自然数一一对应。
采用如下法则对上述例子验证,从而更好地理解"可数+无穷"的概念:
1.验证整数可以和自然数一一对应:让n表示任意自然数(不为0),则整数的全体为{-n,n,0}.让0对应自然数中的1;让1对应自然数中的3,让2对应自然数中的5,即让正整数n对应自然树2n+1;同时,同理,让-n对应2n.你可以验证,通过这个对应法则,自然数与整数一一对应。
2.让0对应1;让2对应3,让4对应5,让6对应7,即让非负偶数2n对应自然数2n+1;同理,让负偶数-2n对应自然数2n.你可以验证,这也是一个一一对应关系。
那么“可数集”是如此,那么“不可数集”的概念也就能明白了。不可数集是无穷集合中的一种。一个无穷集合和自然数之间要是不存在一个对应关系(双射),那么它就是一个不可数集。集合的不可数性与它的基数密切相关:如果一个集合的基数大于自然数的基数,那么它就是不可数的。
百度百科上有一个很详细的证明步骤(和维基百科的一模一样,毕竟这是已经进了教科书的内容,所以这里就直接引用了):
对角论证法证明实数集合为不可数集
康托的原始证明表明区间[0,1]中的点数不是可数无穷大。该证明是用反证法完成的,步骤如下:
1·假设(从原题中得出)区间[0,1]中的点数是可数无穷大的
2·于是乎我们可以把所有在这区间内的数字排成数列, (r1,r2,r3,...),已知每一个这类的数字都能以小数形式表达。我们把这些数字排成数列(这些数字不需按序排列; 事实上,有些可数集, 例如有理数也不能按照数字的大小把他们全数排序,但单只是成数列就没有问题的)在部份有多种表达形式的数字上,例如0.499 = 0.500, 我们选择前者.
3·如果该数列小数形式表现如下:
r1 = 0 . 5 1 0 5 1 1 0
r2 = 0 . 4 1 3 2 0 4 3
r3 = 0 . 8 2 4 5 0 2 6
r4 = 0 . 2 3 3 0 1 2 6
r5 = 0 . 4 1 0 7 2 4 6
r6 = 0 . 9 9 3 7 8 3 8
r7 = 0 . 0 1 0 5 1 3 5...
4.考虑rk小数点后的第k个位,为了方便起见, 我们底间并粗体这些数字,从下图你应明白为什么这个证明被称为对角论证法
r1 = 0 . 5 1 0 5 1 1 0
r2 = 0 . 4 1 3 2 0 4 3
r3 = 0 . 8 2 4 5 0 2 6
r4 = 0 . 2 3 3 0 1 2 6
r5 = 0 . 4 1 0 7 2 4 6
r6 = 0 . 9 9 3 7 8 3 8
r7 = 0 . 0 1 0 5 1 3 5...
5.我们设一实数x, 其中x是以以下的方式定义的
如果rk的第k个小数位等于5,那么x的第k个小数位是4
如果rk的第k个小数位不等于5,那么x的第k个小数位是5
6.明显地x是一个在区间[0,1]内的实数,以之前的数为例, 则相对应的x应为 0 . 4 5.5 5 5 5 4
7.由于我们假设(r1,r2,r3,...)包括了所有区间[0, 1]内的实数,所以一定有一个rn = x
8.但由于x的特殊的定义,这使得x和rn的第n个小数位是不同的,所以x不属于(r1,r2,r3,... )
9.所以(r1,r2,r3,...)并不能罗列所有区间[0, 1]内的实数,这发生了矛盾。
10.所以在第一点内所提出的假设"区间[0,1]中的点数是可数无穷大的"是不成立的。——证明完毕
康托尔的“对角线方法”精巧、令人赞叹。这个证明方法同时也为后面一些列的概念和系统提供了基础——甚至是悖论。毕竟康托尔的集合论被发明出来之后,他自己就发现了集合悖论,最后还引发了第三次数学危机。(所以数学领域之间的各个分支其实又是环环相扣的,很多概念和内容当中互相都有关联)
“对角线证法"是康托尔在无穷集合的研究中得出的。1873年康托尔在他与戴德金的一次通信中提出实数集是否能和自然数集构成一一对应的问题。康托尔于1874年的文章给出了一个复杂的证明之后,他又给出了一个不依赖于无理数的技术性的证明,这就是熟知的优美而深刻的“对角线证法"。
这是用完全直观的无穷阶方阵的“对角线”构造了一个不包含在某个假设为已知的集合的元素,也就是在一个特定的系统中构造一个“自我否定”,这正是这一方法的实质。在悖论各种证明中,“对角线证法’’得到了离开直观的发挥和推广。“对角线证法”不断地反复出现在递归函数论、计算机科学中。还出现在哥德尔第一不完全性定理的证明和A.塔斯基关于真理的论证中。
英国逻辑学家汤姆逊在1962年发表的论文《论一些悖论》,对一些悖论的构成方法进行了分析。指出罗素悖论、理发师悖论、格雷林悖论、理查德悖论都是建立在康托对角线证法之上。现代一些逻辑学家几乎把所有逻辑悖论(集合论的和语义学方面的)都叫做“对角线悖论”,包括著名的哥德尔不完全性定理。
“康托尔对角线”恰恰是一种以“有穷”探索“无穷空间”的方式,这就是为什么在这里要反复暗示康托尔的名字的原因。另外一个方面来说,这部分也是现代数学很多理论构建的入口。因为“集合论”对于如今数学重要性已经不言而喻了。而且还不仅仅如此——上述的“同构”也起着重要作用,恰恰是“同构”让数学中行之有效的方式可以延伸到其他方面:物理、化学、计算机……乃至一起可以和数学“同构”(挂上钩)的学科领域。

4·哥德巴赫猜想

哥德巴赫猜想(Goldbach's conjecture)是数论中存在最久的未解问题之一。这个猜想最早出现在1742年普鲁士人克里斯蒂安·哥德巴赫与瑞士数学家莱昂哈德·欧拉的通信中。用现代的数学语言,哥德巴赫猜想可以陈述为:任一大于2的偶数,都可表示成两个素数之和
这个猜想与当时欧洲数论学家讨论的整数分拆问题有一定联系。整数分拆问题是一类讨论“是否能将整数分拆为某些拥有特定性质的数的和”的问题(注意,这是“一类”问题,哥德巴赫猜想只是其中一种,这就是为什么在上文对话里说它存在种种“变奏的原因”),比如能否将所有整数都分拆为若干个完全平方数之和,或者若干个完全立方数的和等
将一个给定的偶数分拆成两个素数之和,则被称之为此数的哥德巴赫分拆。比如:“4 = 2 + 2、6 = 3 + 3、8 = 3 + 5、10 = 3 + 7 = 5 + 5、12 = 5 + 7、14 = 3 + 11 = 7 + 7……”
简而言之,哥德巴赫猜想主张每个大于等于4的偶数都是哥德巴赫数——可表示成两个素数之和的数。哥德巴赫猜想也是二十世纪初希尔伯特第八问题中的一个子问题。
其实,也有一部分奇数可以用两个素数的和表示,大多数的奇数无法用两个素数的和表示,例如:15=2+13 ,而 23、35等数则无法用两素数的和表示。
哥德巴赫猜想存在另一个较弱的版本(也称为弱哥德巴赫猜想)是声称大于:“5的奇数都可以表示成三个素数之和。”(对话里乌龟提到了类似的情况,是“变奏”之一)这个猜想可以从哥德巴赫猜想推出。1937年,苏联数学家伊万·维诺格拉多夫证明了每个充分大的奇数,都可以表示成三个素数之和,基本证明了弱哥德巴赫猜想。
哥德巴赫猜想在提出后的很长一段时间内毫无进展,直到二十世纪二十年代,数学家从组合数学与解析数论两方面分别提出了解决的思路,并在其后的半个世纪里取得了一系列突破。目前最好的结果是中国数学家陈景润在1973年发表的“陈氏定理”(也被称为“1+2”)。
哥德巴赫猜想在中国可以说是耳熟能详,这主要是归因于中国当代作家徐迟发表于《人民文学》杂志1978年第1期的报告文学作品,题目就叫《哥德巴赫猜想》。这篇文章详细描写了陈景润的身世和在文化大革命期间的困难条件下证明“陈氏定理”的过程。
这篇报告文学作品影响力巨大,在徐迟的报告文学影响下,哥德巴赫猜想成为了中国民间科学爱好者热衷研究的数学问题之一。不少民间科学爱好者对哥德巴赫猜想产生兴趣,许多人自称在此问题上取得了进展,甚至自称证明了哥德巴赫猜想。中国科学院每年都收到“几麻袋”的讨论或声称证明了哥德巴赫猜想的来信来稿。不少报章也刊登过哥德巴赫猜想被民间科学爱好者证明的消息。但这些证明基本都是错误的,缺乏足够专业训练的人很多甚至都没有办法正确理解这个内容。但之所以会让很多人陷入迷雾当中,产生这个问题自己也可以解决的“假象”是因为哥德巴赫猜想本身表述的内容确实非常“浅显易懂”。(实际上大多数“数论”问题也都是这样)。目前中国科学院已声明不会审理来自科学共同体之外的任何自称证明了哥德巴赫猜想的文章。
我们不妨来看看哥德巴赫猜想的历史:
1742年6月7日,普鲁士数学家克里斯蒂安·哥德巴赫在写给瑞士数学家莱昂哈德·欧拉的通信中,提出了以下的猜想:“任一大于2的整数都可以写成三个质数之和。”
上述与现今的陈述有所出入,原因是当时的哥德巴赫遵照的是“1也是素数”的定义。(关于1是不是“素数”的争论在之前的笔记里提过一句,关于这个问题一直有争议,而且影响非常巨大,因为这会影响整个“素数”的定义)现今数学界已经不使用这个定义了。哥德巴赫原初猜想于是就变成了:任一大于5的整数都可写成三个质数之和
欧拉在6月30日的回信中注明此一猜想可以有另一个等价的版本:任一大于2的偶数都可写成两个质数之和。
欧拉将此一猜想视为一定理,但他却无法证明。今日常见的“猜想”陈述实际上是欧拉的版本,也被称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。
从关于偶数的哥德巴赫猜想,可推出:任一大于5的奇数都可写成三个素数之和
后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的,则关于奇数的哥德巴赫猜想也会是对的。1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇素数都能写成三个素数的和,也称为“哥德巴赫-维诺格拉多夫定理”或“三素数定理”。2013年,秘鲁数学家哈洛德·贺欧夫各特等人将维诺格拉多夫的结论进一步加强,并验证了较小的奇素数的情况,宣称完全证明了弱哥德巴赫猜想。
哥德巴赫猜想相当困难。直至今日,数学家对于哥德巴赫猜想的完整证明没有任何头绪。事实上,从1742年这个猜想正式出现,到二十世纪初期,在超过160年的时间里,尽管许多数学家对这个猜想进行了研究,但没有取得任何实质性的进展,也没有获得任何有效的研究方法。二十世纪以前对哥德巴赫猜想的研究,仅限于做一些数值上的验证工作,提出一些等价的关系式,或对之做一些进一步的猜测。1900年,希尔伯特在第二届国际数学家大会上提出的著名的二十三个希尔伯特问题之中的第八个问题,就包括了哥德巴赫猜想和与它类似的孪生素数猜想。希尔伯特的问题引发了数学家的极大兴趣,但对于哥德巴赫猜想的研究仍旧毫无进展。1912年第五届国际数际数学家大会上,德国数论专家爱德蒙·朗道曾经说过,即使要证明每个偶数能够表示成K个素数的和,不管K是多少,都是数学家力所不及的。1921年,英国数学家戈弗雷·哈罗德·哈代曾经在哥本哈根数学会议的一次演讲中声称:“哥德巴赫猜想的困难程度可以与任何一个已知的数学难题相比”。
一直到2013年,弱哥德巴赫猜想已经获得了完全的证明。而这么多年来,对于哥德巴赫猜想的研究工作始终没有停止过。由于问题本身的艰难,于是为了找寻突破,数学家们纷纷寻找这个问题的拓展版本,然后逐渐向主题靠拢(农村包围城市……)
无论是哈代和利特尔伍德等人使用的“圆法”证明、布朗使用“筛法”的证明,都为后续的工作打下了基础。(埃拉托斯特尼筛法在之前关于“素数”的内容里提过,简单来说就是这个方法可以筛选一定范围内的“素数”)。
这两种思路都在二十世纪中得到了极大的发展。1933年,苏联数学家列夫·杰里科维奇·史尼尔曼同样基于筛法证明了:存在某个整数K,使得每个偶数能够表示成K个素数的和,弥补了朗道的遗憾。史尼尔曼给出的K的上限是800000,不久后罗曼诺夫证明了这个K不会超过2208。
1936年,朗道和彼得·希尔克把结果改进到71,一年后意大利数学家吉奥凡尼·里奇又将结果改良为67。
1938年,华罗庚证明了弱哥德巴赫猜想的一个推广:任意给定一个整数k,每个充分大的奇数都可以表示p1 + p2 + p3^k的形式。当k = 1的时候,就是弱哥德巴赫猜想。
1956年,Sharpio证明了K不超过20,
1956年尹文霖证明了K不超过18。
1976年,英国数学家罗伯特·查尔斯·沃恩证明了K小于等于6。
弱哥德巴赫猜想已经基本得到解决(2013年已经获得完全的证明),对于偶数的哥德巴赫猜想,数学家们则主要将希望放在布朗的“筛法”上。
使用布朗方法的最好结果是陈景润得到的。他在1973年发表了“1+2”的证明,其中对筛法作出了重大的改进,提出了一种新的加权筛法。因此“1+2”也被称作是陈氏定理。现今数学家们普遍认为,陈景润使用的方法已经将筛法发挥到了极致,以筛法来证明最终的“1+1”的可能性已经很低了。布朗方法似乎在最后的一步上停止了下来。如今数学界的主流意见认为:证明关于偶数的哥德巴赫猜想,还需要新的思路或者新的数学工具,或者在现有的方法上进行重大的改进,也有认为仅仅基于现有的方法上的改进是无法证明偶数哥德巴赫猜想。
回想到之前笔记里讲述过关于“费马大定理”的证明过程,有没有发现数论的证明工作似乎都有些相似的地方?确实是,而且这也就是这一章想要讲述的重要主题:有穷步骤探索无穷。(这已经说了好几遍了:重要的事情说三遍2333)这就是困难所在。
这个问题对于人工智能的意义所在,相信说到这里有的人已经能明白了。如果把我们自身的“思维”对应到数论当中,就好比那个“无穷“的“数”。而我们的大脑硬件就好比是”有穷“的”证明“一样。找出这之间的对应的”抽象“关系也许能成为了解”智能“的关键,同时也别忘了并不只有这一个、一种、一类……它还存在多个变奏版本。

三:三种搜索:BlooP、FlooP、GlooP

BlooP、FlooP和GlooP不是神话中的巨人,不是唐老鸭的小侄子们,也不是船沉时发出的冒泡声——它们是三种计算机语言,其中每种都有特殊的用途。这些语言是专门为本书的这一章发明的。它们将被用来解释‘递归’这个词的某些新意义——特别是‘原始递归’和‘一般递归’这两个概念。事实将证明,这些语言有助于阐明TNT中自我相关的机制。
在计算机科学中这里提到的“原始递归”和“一般递归”涉及到可计算性理论的概念。可计算理论在数理逻辑范畴内也可以叫做递归论,是数理逻辑的一个分支。它起源于对可计算函数和图灵度的研究。它的领域包括一般性的可计算性和可定义性的研究。递归论所考虑的基本问题是:“给定一个从自然数到自然数的函数f,f是否是可以被计算的”。
“可以被计算”,我们先将它当作一个直观的概念。根据直觉,我们一般会认为,一个函数可以被计算是存在一个给定的运算过程,接受一个自然数n后,该过程进行一定的操作并给出f(n)作为输出。将计算这一直观的概念上升到数学层面的形式化定义(计算—推导规则),这工作是递归论的根本,并由哥德尔、邱奇、图灵、克莱尼和Emil Post等人在1930年代奠定。他们将图灵可计算性作为有效计算的形式化。(这里为后面涉及邱奇-图灵论题的概念已经做下铺垫了,后面会有专门一个章节来讲述这个题目的)
在了解了递归论的基本概念之后,一方面人们将这个概念应用于数学中,从而证明了一系列自然的问题,如字问题,以及希尔伯特第十问题等问题是“不可计算”的。另一方面,理论家们进一步拓展,开始了相对可计算性,图灵度等问题的研究。数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。如今,递归论仍是数理逻辑中活跃的领域。
相对而言计算机科学家他们则研究次递归层次,可行的计算和公用于可计算性理论研究的形式语言。在这两个领域(计算机科学和数理逻辑)之间有着相当大的知识和方法上的重叠,而没有明显的界限。
这里还可以涉及到计算理论,计算理论的“计算”并非指纯粹的算术运算(Calculation),而是指从已知的输入透过算法来获取一个问题的答案(Computation),因此,计算理论同时属于计算机科学和数学这两个范畴。
其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题:
1·采用什么计算模型(即形式语言、自动机)
2·解决哪些是能计算的、哪些是不能计算的(即可计算性理论及算法)
3·要用多少时间、要用多少存储(即计算复杂性理论)
这三方面的问题可以用一个问题来总括:“计算机的基础能力及限制到什么程度?
那么在计算机科学中,可计算性理论(Computability theory)作为计算理论的一个分支,就是研究在不同的计算模型下哪些算法问题能够被解决。相对应的,计算理论的另一块主要内容,计算复杂性理论考虑一个问题怎样才能被有效的解决。
我们似乎很突然地从大脑和心智跳到了数学和计算机科学中的技术。虽然这个跳跃从某些方面来看有点突然,但它还是有意义的。我们已经看到,某种自我意识似乎是意识的关键所在。现在我们要在更形式化的背景下进一步分析‘自我意识’,例如在TNT的背景下。在TNT和心智之间还有很大一段距离,但一些想法将会是富有启发性的,或许会以隐喻的方式被传回到我们关于意识的思考之中。

1·足够“复杂”?——再看哥德尔不完备性定理

在前面已经说过了,当我们面对一个特别艰深的问题的时候,如果我们没有办法直接解决它,我们可以选择先“绕路”:先解决这个问题的“变奏”(简化)版本,然后以此为思路逐渐接近最后的问题解决。数论当中那些艰深的问题无一不是这么解决的:“费马猜想”、“哥德巴赫猜想”、“希尔伯特问题”……无一不是如此。
说到人工智能上来,这其中最深奥的问题就在“自我意识”这一块了。关于这个问题的讨论多如繁星,但要想确实的解决这个问题,还是应该先做点什么,为后面的来者铺路。人工智能的“自我意识”我们无法直接获得,那么我们不妨看一看这个问题的一个非常简单的“变奏版本”——“机械自动化”。这在前面也有提到过:——形式推理自动化(记不记得关于欧几里得证明素数的那个证明“推广”?)
关于TNT的自我意识,令人惊奇的一点就是它密切的联系于自然数中的有序与无序问题。特别是我们将会看到,一个充分复杂以至能反映自身的有序系统不可能是完全有序的——它必定包括某种奇怪的无序特征。对于那些具有某种阿基里斯式想法的读者来说,这将是很难接受的。但是,存在一种‘魔术式的’补偿——存在某种关于无序的有序,这本身已经形成了一个研究领域,成为‘递归函数论’。遗憾的是,我们所能做到的,只是略微展示一下这个课题的魅力。
“递归函数”暂且先放到后面,这里其实还在继续一个之前就讨论过的内容——依旧是哥德尔不完备性定理。话题又回到了之前的“龟蟹之战”——也就是关于“完备唱片机”的那次争论上,不知道还有没有人记得这个内容,简而言之,就是用唱片机播放唱片来比喻哥德尔不完备性定理在形式系统当中的运行情况——“每一个唱机都会有一个唱片,刚好可以播放出产生共振效果的音波,从而导致唱片机自毁。”
像‘足够复杂’或‘足够强有力’及类似的说法,在前面已经多次出现了。但这些说法是什么意思呢?让我们回到龟蟹之战,并问这样一个问题:‘是什么使某个东西有资格称为一台唱机的?’螃蟹可能会声称它的冰箱是一台‘完备的’唱机。然后为了证明这一点,它可能会随便拿个唱片放在冰箱顶上,说:‘你看——它在播放唱片了。’而乌龟,如果想要反驳这个禅宗式的行动。就必须说:‘不——你的冰箱保真度太低,已经不能算是唱机了:它根本不能重现唱片上记录的声音(更不必说那种让它自我破坏的声音了)’。”这里要注意了,不完备性定理本身针对的是“足够强力”的系统,也就是说不能随便乱套用——这里要跳脱自然语言的自由语义,而严格遵守“专门的定义”。
再回过头来看一遍哥德尔的两个不完备性定理:
1·任何兼容的形式系统,只要蕴涵皮亚诺算术公理,就可以在其中构造在体系中不能被证明的真命题,因此通过推演不能得到所有真命题(即体系是不完备的)。
2·任何逻辑自洽的形式系统,只要蕴涵皮亚诺算术公理,它就不能用于证明它本身的兼容性。
所以书中经常出现的:“足够复杂的”、“足够强的”、“足够保真度的”……在这里应该就是指“蕴含皮亚诺算术公理”的意思。这个算术公理在之前就介绍过了,皮亚诺五大算术公理可以建立起一个“一阶逻辑”:一阶逻辑是使用于数学、哲学、语言学及计算机科学中的一种形式系统。一阶逻辑出现过许多种名称,包括:一阶断言演算、低级断言演算、量化理论或谓词逻辑。一个一阶逻辑,若具有由一系列量化变量、一个以上有意义的断言字母及包含了有意义的断言字母的纯公理所组成的特定论域,即是一个一阶理论。
通俗点的说法:“能讲明白,定义一些讲法概念。”如同形式系统当中的:“公理”。它是构建起系统的基础,比如欧几里得几何里的“四大公设”之类。公理本身就是自可证——对应到唱机比喻里,放唱片能放出声音来的才叫“唱机”。
实际上是存在完备的情况的,这在之前就说过,但问题在于,完备的系统“强度有限”——哥德尔完备性定理:在一阶谓词演算中所有逻辑上有效的公式都是可以证明的。
上述词语“可证明的”指的是有着这个公式的形式演绎。这种形式演绎是步骤的有限列表,其中每个步骤要么涉及公理要么通过基本推理规则从前面的步骤获得。给定这样一种演绎,它的每个步骤的正确性可以在算法上检验(比如通过计算机或手工)。
所以哥德尔定理是一阶逻辑的定理,故最终只能在这个有限框架内理解。在形式逻辑中,数学命题及其证明皆以一种符号语言描述,只要检查每一个证明的有效性,便可从一组公理开始无可辩驳地证明一条定理。理论上,这样的证明可以在计算机上检查,事实上这样的有效性检查程序也已经有了。
为了这个证明过程得以进行,必须要确定手头有什么样的公理。可以从一组有限的公理集合开始,例如欧几里得几何的公设。或者更一般地,由一个可以允许无穷的公理列表开始,只要能机械地判断给定的命题是否是一条公理就行。在计算机科学里面,这被称为公理的递归集。(公理看作定理的前提,定理变成公理,就继续能推出定理,于是它就又变成了后一个定理的前提……)尽管无穷的公理列表听起来有些奇怪,实际上自然数的通常理论中(皮亚诺算术公理)就是如此。
“……说TNT是一个形式化的N(数论),其原因是TNT的符号以正确的方式活动:这也就是指它的定理不像并相似的一声不响——它们确实说出了N中的真理……那么,这些N中的‘核心真理’是什么?它们是‘原始递归真理’,这就是说,它们仅仅涉及到‘可预测其终止’的计算。这些核心真理在N中的作用就像欧几里得的前四个公设在几何学中的作用一样:它们使你可以在比赛开始前就能淘汰掉某些‘力量不够强’的选手。从此以后,‘全部原始递归真理的可体现性’将作为我们称一个系统为‘足够强有力’的判别标准。
哥德尔的第一条不完备定理表明任何一个允许定义自然数的体系必定是不完备的:它包含了不能在此体系内以一阶谓词逻辑形式证明的命题,并且该命题的否命题也不能在该体系内以一阶谓词逻辑的形式证明。
存在不完备的体系这一事实本身并不使人感到特别惊讶。例如,在欧几里得几何中,如果把平行公设去掉,就得到一个不完备的体系。不完备的体系可能只意味着尚未找出所有必须的公理而已。(所以一阶逻辑虽然“完备”但是“强度有限”,从后面这个强度的概念来理解,它还是不完备的——并不能推导出所有“定理”。)
哥德尔不完备性定理揭示的是在多数情况下,例如在数论或者实分析中,永远不能找出公理的完整集合。换句话说,每一次将一个命题作为公理加入,将总有另一个命题出现在所能形式证明的范围之外。
如果你有数论的一个足够强有力的形式化体现,那么哥德尔定理就是可应用的,结果你的系统即是不完备的。另一方面,如果你的系统不是足够强有力的(即不是所有原始递归真理都是定理),那么你的系统由于有这个缺陷,也是不完备的。……另一点需要注意的是,这完全平行于《对位藏头诗》中的‘高低保真度之别’。

2·无序中的有序

实际上,人们发现很弱的系统依然是会受到哥德尔方法攻击的。‘所有原始递归真理都需要体现成定理’,这个标准过于严格了……
现在,在我们进入对原始递归函数的谓词的详细讨论之前,我想把这一章的主题和前几章的主题联系起来,一提供一个更好的背景。
实际上我相信一直在看笔记的读者可能已经注意到了,前面的内容经常被反复提起。这是很重要的,有些时候不提前面的内容,当下的内容几乎就看不不懂。之前出现过的三个形式系统,基本上已经非常形式化的展现了后面要说的诸多理论。当然这些例子对于专业的人士来说可能先得非常浅显易懂,而对于非专业的读者来说基本上就是不知所云了——主要差距就在于脑子里有这么多概念,或者没有这么多概念、还有一个就是一个思维方式的问题:专用语言区别于自然语言的意义
我们很早就已经看到,形式系统可能是难以驾驭的,因为它们有加长和缩短符号串的规则,这可能会导致在大量符号串中进行无终止的搜索。哥德尔配数法发现,显示了任何对一个具有特殊的符号性质的串的搜索都有一个算术中的表兄弟:对一个具有相应的特殊算术性质的整数的同构搜索。”(联系到前面提过的,集合论当中的概念术语:“等势”、“双射”。)
在本章前面的对话中,我可能过分强调了和整数有关的问题中显示出的无序现象。事实上,和‘妙极性’问题相比,人们已经驯服了一些更复杂的无序现象,发现它们不过是些很温顺的家伙。
来对比一下下列的两个数列:
7、8、5、3、9、8、7、6、3、3、9、7、4、4、8、3、0、9、6、7、5、6、6、0、8……
另一个是:
1、-1/3、+1/5、-1/7、+1/9、-1/11、+1/13、-1/15……
先来看第一个数列,能找出规律来说出省略号后面下一位数吗?似乎不行,看起来第一个数列是随机的。那么第二个序列呢?省略号后面一个数该是什么?估计有人看出来了:+1/17那么这有什么关系呢?实际上上下两个数列直接的构成规律是有关联的。简而言之,第一个数列只不过是第二个数列的和的十进制小数部分(展开式)的开始几位,这个数列的和是:π/4
所以说第一个数列并不是随机的,只是表面上看似随机,而背后实际上是有更抽象的规律。(用了好几个数学技巧拐弯抹角的构筑)
自然规律恰恰是以这种方式被发现的。自然只是提供给我们大量的现象,它们表面上杂乱无章,知道我们选择了某些有意义的事件,而且把它们从特定的,关系不大的环境中抽象出来,使它们成为理想化的时候为止。只有那时它们才会展现出光彩夺目的真实结构。
上面这一段是GEB当中引用的文献,文献名叫《量子是实在的吗?》。这段内容可以让人联想到两个领域:混沌理论和概率论,当然这里的衍生就先到此为止,否则就变成“无穷回溯”了,那就没完了。
从哲学中退出来,我们仍然考虑表面上的随机序列中深藏的规律性。第五章中的函数Q(n)是否也具有一个简单的非递归解释?是不是每个问题都像《一首无的奉献》中提到的那片果树林一样,从某个特定的角度看进去,其中的秘密就一览无余了?还是说在数论中存在着一些不论从哪个角度看都是神秘的问题?
有了这段开场白,我觉得现在应该继续前进,去定义所谓‘长度可预测的搜索’的精确意义了。这将用BlooP语言来完成。

3·BlooP搜索语言——有限搜索

BlooP语言的基本步骤:我们的议题是搜寻具有各种性质的自然数。为了讨论任意搜索的‘长度’,我们必须定义一些基本‘步骤’,任何搜索都由它们组成。这样,搜索长度就可以根据其中的步骤数来度量。被我们当作基本面步骤的有:两个自然数相加;两个自然数相乘;确定两个数是否相等;确定两个数的相对大小。”这里要提醒一下,和前面给出过的形式系统一样,这里是用“字符串”来表示各种自然数的,所以会有长度“增减”。这个转换概念必须一直记得,否则后面说的内容就会看不懂。(比较典型的例子就是前面TNT系统表示一个“20”,用了一长串“字符”)
搜索语言:可以理解为构建了一个“测试”,它会对输入的特定信息进行判断,最后给出结果,或者不给出结果。
如果我们想用这些步骤严格地构造一个测试,例如测试一个数是否是素数,我们很快就会发现必须在其中包含一个‘控制结构’——即对操作次序的描述:和是需要回过头来重新尝试某些东西,何时跳过一些步骤,何时停止,以及诸如此类的事情。”(参照之前提过的“递归迁移网”:调用、存储这些都是程序运行过程中发生的事)
在典型的情况下,任何‘算法’——即对任务完成过程的明确描述——都由下列成分组成:(1)需完成的特定运算,(2)控制语句。因此,当我们为表示长度可预测的计算开发我们的语言时,我们必须同时包括基本控制结构。
在BlooP中,基本上唯一的控制结构就是‘有界循环’(即‘bounded loop’,这也正是‘BlooP’的来历)
那么BlooP搜索语言的特点就在于它的控制结构——“控制结构集”是有限的,严格遵循步骤顺序不能够任意转移或者无限制的循环某个步骤:重复执行一组指令,但重复次数不得超过一个确定的最大值,一旦超过就停止运行。这个最大值被叫做“上界”或“顶”。
在一个程序中,并不要求程序员准确地给出所有上界的数值——事实上它们是无法预知的。但是,每个上界都可以在进入该循环之前通过计算来确定。
值得一提的是在BlooP搜索当中,也是用到了“组块化”的概念。注意前面提到,程序可以执行有限次的循环,然后前一个循环的结果是下一个循环的开始,而组块化就是把前面“几次的循环”获得的结果看成“一次循环”得到的结果——你也可以给程序不同的“初始值”。直白来说就是:程序操作的每一个步骤只能做一次简单处理,但是通过“循环操作”和“组块化”,我们是能得到“复杂的”结果的。
……一旦一个过程已经被‘定义’了,它就可以在后面的过程定义中被‘调用’。其效果是一旦某个操作在一个过程中被定义了,它就会被认为和基本步骤一样简单。这样,BlooP就具有了自动组块的特点。你可以把这和一个溜冰好手学习新花样的过程相比:他不是把新动作看作长长的基本肌肉活动序列,而是看作以前学过的一些动作的组合,而那些动作自身又是用更早所学的动作所组成,如此等等——这种嵌套或组块可以上溯许多层次,直至遇到基本肌肉活动为止。这样,BlooP程序的能力就和溜冰者的技能一样,可以突飞猛进地增长了。
在这样的“搜索”语言中,是存在很多限制的。一些一开始的初始设定是不能更改的。比如书里BlooP语句如果进行数学运算的操作的话,它只能做加法——后一个结果是前面结果的不断叠加一直达到想要的结果为止。那么问题来了,如果我们需要减法怎么办?把整个算法推导重来?并不是,记不记得pq形式系统那个关于筛选“素数”的例子。直白来说,减法是加法的反向操作。
假设我们需要“M-N”这个减法运算在这里进行,那么很简单,BlooP当中的循环操作会把N一直进进行加法运算,直到得出一个与N的和等于M的数为止。那么如果M小于N怎么办?由于BlooP的搜索结果仅限于自然数域(自然数一般是指正整数,所以是没有负数的。),那么可以设置一旦这样的情况出现,BlooP获得的结果就是0那么操作循环终止,我们得到结果。
我们通过BlooP程序所能做的事情可以看出来,它实际上可以做两件事,既可以是“搜索”(或者可以叫“函数”)也可以做“测试”。也就是说BlooP除了可以给出我们想要的“自然数”之外,也可以只给出“YES”或“NO”。因为我们知道BlooP只能进行有限次的操作,所以它的终止只有两个结果:获得我们想要的结果“搜索”结束。或者一直没有得到想要的结果,到达“上界”则“搜索”结束。前者可以把输出结果替换成“YES”,后者则是输出“NO”。(书中给出了具体算法的例子)
简而言之BlooP程序的运算过程可以看作是一条“过程定义链”(其中每个过程仅仅调用前面定义的过程),这样我们再回过头来看,就明白为什么把BlooP来计算的函数叫做“原始递归函数”了(“递归”的概念在第五篇笔记已经做了非常详细的解释了)。
可以用BlooP测试来验证的性质的标准名称是’原始递归谓词‘。这样,函数2^3^n就是个原始递归函数,而命题’n是个素数‘则是个原始递归谓词。
凭直觉就能看出哥德巴赫性质是原始递归的。
(警告:哥德巴赫性质是原始递归的,但这一事实并没有使’是否所有的数都具有哥德巴赫性质?‘成为一个简单的问题——远非如此!)
到这里我们可以直接搬出“原始递归函数”的定义了:在可计算性理论中,原始递归函数对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义,并且是递归函数的严格的子集,它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。
通常在数论中研究的很多函数,近似于实数值函数,比如加法、除法、阶乘、指数,找到第 n 个素数等等是原始递归的。实际上,很难设计不是原始递归的函数,尽管某些函数是已知的(比如阿克曼函数)。所以,通过研究它们,我们能发现有广泛影响的结论的那些性质。
原始递归函数可以用总是停机的图灵机计算,而递归函数需要图灵完全系统。
原始递归函数的集合在计算复杂性理论中叫做PR。
在继续讨论一些关于BlooP及其’亲戚‘FlooP的问题之前,让我们先回顾一下当初引进BlooP的原因,并把它和TNT联系起来。我在前面说过,一旦全部原始递归的概念对一个形式系统来说都是可体现的,那么这个系统就达到了使用哥德尔方法所需的’临界质量‘。
在数论领域当中,用词真的是一个非常重要的事,这在前面就已经强调过了。自然语言为了交流便利而模糊了一些用法和定义,而数论语言则完全反之:一就是一,二就是二,不存在模糊、大概的解释。
我们必须区别这样两个概念:可表示性和可体现性。’表示‘一个谓词只不过是一个从自然语言到严格的形式化表述的翻译问题。这和该谓词是不是定理没有关系。而要’体现‘一个谓词,这颗就是个强得多的概念了。这意味着:
(1)该谓词的全部为真的例均为定理;
(2)全部为假的例均为非定理。
’例‘在这里是指用数值取代谓词中所有自由变量后所得到的串。
……TNT的优点是能够表示数论中的任何谓词。例如,很容易写一个TNT串来表示谓词’b具有乌龟性质‘。因此,根据表示能力来看,TNT满足我们的全部要求。
但是,问’在TNT中哪些性质是可体现的?‘,这恰恰就是在问’TNT作为一个公理系统有多强?‘。是不是所有可能的性质在TNT中都是可体现的?若是如此,那么TNT就能回答数论中的任何问题,它就是完全的。”但实际上我们很清楚“完全的”是不可能的事,不过TNT系统依然可以涵盖整个“原始递归谓词”。
如果能为自然数的某个性质写出一个BlooP测试,那么这个性质在TNT中是可体现的。”那么这个问题反过来问,是否数的每一种性质都能被某个适当的BlooP程序所检查?“这个问题实质上是’是否总能给出运算长度的上界——还是说在自然数系统中存在一种内在的混乱,致使有时无法事先预测运算的长度?‘令人震惊的是,恰好是后一种情况出现了,其原因我们不久就会看到……在我们的论证中,将使用享有盛名的’对角线法‘,这是由集合论的奠基人康托尔发现的。
现在知道为什么要在对话里反复暗示康托尔的存在了,而且这里的论证某种程度上来说,就是康托尔“对角线法”的一个“变奏版本”。这里直接就给出结论了,根据“对角线法”得出的结论,恐怕确实存在一些不能在BlooP中编程序的函数,这些函数不是“原始递归的”。
值得一提的是,通过这个例子,我们又绕回到了第三次数学危机的内容上面来了。康托尔实际上比罗素更早发现集合论当中存在的悖论,而这个悖论很有可能是通过“对角线方法”发现的:
在数学中,康托尔悖论是集合论的一个定理,即没有最大的基数,所以“无限大小”的搜集自身是无限的。进一步的,从这个事实得出这个搜集不是集合而是真类;在冯·诺伊曼-博内斯-哥德尔集合论中从这个事实得出大小限制公理,即这个真类和所有集合的集合之间存在双射。所以,不只是有无限多个无限,而是这个无限大于无限的任何枚举。
这个悖论以德国数学家格奥尔格·康托尔命名,他在1899年(或在1895年到1897年之间)首先提出了它。像多数数学悖论一样,它实际上不是矛盾,而是在关于无限本质和集合概念的情况下错误直觉的体现。换个方式说,它在朴素集合论中的确是悖论,从而证实了这个理论对数学发展的需要是不充足的。在其后的各个公理化集合论中,这个悖论已经被解决。
尽管通常认定康托尔是第一个提出基数集合的这个性质的人,有些数学家认为这个贡献是伯兰特·罗素做出的,他在1899年或1901年定义了类似的定理。——维基百科:’康托尔悖论‘词条”
上述的说法太过于抽象,那么类似用理发师悖论来比喻罗素悖论一样,这里也换一个简单通俗点的说法:即“对角线论证”最后得出了完备实数列表之外还有实数。通过这个我们也明白了,哥德尔不完备性定理的工作也是基于了“对角线论证”的方法——前面的内容全串上了(包括《对位藏头诗》那一篇的全部内容)。

4·FlooP搜索语言————无限搜索

至此,我们已经用以BlooP语言写的程序为工具,定义了自然数上的原始递归函数和原始递归谓词所组成的类。我们也表明了BlooP不能囊括全部可用词语定义的自然数上的函数。我们甚至还用康托尔的对角线法构造了一个‘非BlooP可编程的’函数,即‘蓝对角’[N]。为什么在BlooP中不能表示‘蓝对角’呢?是否能改进一下BlooP,以使得‘蓝对角’成为可表示的呢?
BlooP的根本特征就是其中循环的有界性。如果我们抛掉对循环的这种要求,发明另一种语言,称其为FlooP(英文Free有‘自由’的意思,我们借此表明FlooP的循环是自由的),会出现什么情况呢?FlooP除掉一点之外与BlooP完全相同:在FlooP中我们既可以用无顶的的循环,也可以用有顶的循环(虽然在FlooP中写循环语句时注明其顶的唯一理由是为了好看)。这些新的循环将被称为MU-LOOP(μ循环)。这是为了遵守数理逻辑中的约定:在其中‘自由’搜索(无界搜索)通常备注上一个叫‘μ算子’的符号。
这个μ算子(英语:μ operator)也可以被叫做极小化算子(minimization operator)或者无界查找算子(unbounded search operator)在可计算性理论中,被用来查找给定性质下的最小自然数。这个概念还涉及到可计算理论、图灵度等等概念,有相当多的涉及这个概念的专业术语目前甚至还没有中文翻译(μ是第十二个希腊字母,大写是M,音译:姆/缪)。暂时只能说这么多,但是从这里可以联系到另一个前面提到的概念:“递归函数”。
在数理逻辑和计算机科学领域中中,递归函数或μ-递归函数是一类从自然数到自然数的函数概念。从直觉上讲递归函数是"可计算的"。而且在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关,而且递归函数的归纳定义创建在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。换言之,如果把递归函数看作是一个集合(所有递归函数的集合叫做R)的话,则原始递归函数相当于R的子集。递归函数还存在其他等价的函数类:λ-递归函数和马尔可夫算法可计算的函数。
……我们可以用FlooP为妙极性及乌龟性质这样的性质写测试程序——而这样的测试程序我们用BlooP是无法写的,因为其中的搜索或许会无穷无尽……在这个测试中要实现下列功能:
(1)如果输入N是妙极的,则程序结束,给出答案YES
(2)若N是非妙极的,而且导致一个不同于1-4-2-1-4-2-1……的封闭循环,则程序停止,给出答案NO。
(3)若N是非妙极的,而且导致一个‘无穷上升过程’,程序将不会结束。以这种方式,FlooP的不回答就是回答。FlooP的不回答就像用赵州的‘无’来‘废问’一样。
在第3中情况下,具有讽刺意味的是:输出变量OUTPUT的值一直NO但我们又一直无法得到它,因为程序仍在不停的运转。这个讨厌的第三种可能性是我们写自由循环时所必须付出的代价。在所有包含了MU-LOOP的FlooP程序中,无终止总是一种理论上的可能性。当然,有许多FlooP程序实际上相对于其所有可能的输入值都是能终止的。
所以FlooP某种程度上来说是BlooP的拓展升级版,我们通过上面的描述看出来,这个搜索语言理论上存在着“有终止”(一般递归)和“无终止”(部分递归)两种情况。而实际上无论如何,程序还是需要有一个终止操作,否则的话就会使得程序完全没有反应——因为没有终止,所以当你输入之后,程序就不理你了;它一直在运算但是没结果。
那有没有办法避免这种问题呢?记得BlooP程序的两个能力吗?它可以进行判断。但是问题在于,BlooP程序能输入语言,怎么能把FlooP这个“程序”塞进去呢?其实是可以的,用数字对FlooP程序进行编码就可以了,这个编码方式我们之前接触过,就是哥德尔配数——之前在讲命题演算和TNT系统的时候提到过。
现在我们的计划是写一个名为‘TERMINATOR?’的BlooP测试,其功能是:如果被其输入数字所编码的那个FlooP程序是有终止的,则回答YES,否则回答NO。用这个办法就可以把这个任务交给机器去完成。如果走运,就能把有终止和无终止过程分开了。但是,阿兰·图灵给出的一个精巧的论证表明,任何BlooP程序都不能一贯正确地完成这种区分工作。图灵所用的技巧实际上和哥德尔的技巧基本相同,因此也密切联系于康托尔的对角线技巧。
这个证明和前面的情况类似:因为之所以不能一贯的正确区分是因为有无终止的“终止测试器”实际上是不可能存在的。这个证明和上面用对角线方法证明BlooP程序是类似的,而得出的结果也类似——存在一个良定义的单变量可计算函数,但这个可计算函数不在FlooP的搜索目录之内。值得注意的是,如果这个证明里没有使用“终止测试器”的话,则对于FlooP不能使用对角线论证,因为程序会无休止计算,而对角线论证要求对角线上的函数为所有可能的输入算出输出值。
之前对于强力TNT系统的证明也存在和这个相类似的情况——系统升级强化,依然不能摆脱不完备性定理。

5·GlooP搜索语言——神话?

这里直接引用原文了:“如果说FlooP是去掉限制的BlooP,那么GlooP一定是去掉限制的FlooP。但一个限制怎么可能去掉两次呢?你怎么能构造一个比FlooP更强有力的语言呢?在‘红对角’中,我们已经发现了一个函数,我们人知道如何去求它的值——求值方法已经明确的用自然语言描述出来了——但似乎不能用FlooP语言编出程序来完成这项工作。这是一个尖锐的二律背反,因为还没有人曾经发现过比FlooP更强有力的计算机语言。
有人曾经详尽地研究过计算机语言的能力,我们不必自己再去做这项工作,只需报告这样一项结果:有一大批计算机语言可以被证明是与FlooP具有完全相同的描述能力的,这就是说:任何一个可以用其中某种语言编程序完成的计算过程,必然能用所有这些语言中的任何一个来编程序完成。奇怪的是,几乎任何设计计算机语言的合理企图,都以构造出这个类中的一个成员而告终——也就是说,造出了一种能力等价于FlooP的语言。当然通过某种努力也可以构造出一种比这一类语言要弱一些的合理并有趣的计算机语言。陷入,BlooP就是弱语言的一个例子,但这是一种例外,而不是规律。关键在于存在许多很自然的方式可以用来发明算法语言,而不同的人,循着不同的途径,往往最终创造出等价的语言。它们只有形式上差别,能力是一样的。
事实上,绝大多数人都相信不会再有描述计算的能力强于FlooP及其等价物的语言了。这个假说在30年代被两个人互相独立地表述出来:阿兰·图灵——关于他,后面还会进一步介绍——和阿朗佐·丘奇,本世纪杰出的逻辑学家之一。他们的结果被称为‘丘奇·图灵论题’。如果我们接受这个论题,我们就必须下结论说‘GlooP’是个神话——在FlooP中已经没有限制可以取消,无法通过‘解放’来增强它的能力,像我们对BlooP做过的那样。
这把我们置于一种尴尬的境地,即断言人可以为N的任意值计算‘红对角’,但无法编出程序让计算机来完成这项任务。因为,如果这项任务可以得到完成,那它一定是用FlooP语言来完成的。而根据任务的构造方式,它又不可能用FlooP来完成。这个结论实在太奇特了,致使我们得非常仔细地研究它赖以建立的基础。而在这当中,你会想起来,就有我们那个不牢靠的假设,即存在一个可以区别有终止和无终止的FlooP程序的判定过程。这个判定过程的想法本来就有点可疑,因为我们已经看到它的存在将导致数论中的所有问题以一种统一的方式被解决。现在我们有了双重的理由相信任何终止测试都是一种神话——根本就无法把FlooP程序装到一台‘甩干机’里,把有终止程序和无终止程序分离开来。
怀疑论者可能会坚持说这不像对此类终止测试的不存在性的一个严格证明。这种反对意见是合理的。但是,图灵的方案更为严格地论证了这一点:用一个和FlooP同类的语言,不可能写出计算机程序,来对所有FlooP程序进行终止测试。”(通俗来说:一旦问题陷入自指,那这个问题就没完了,而自我超越——这更像个神话。)

四:关于哥德尔配数以及邱奇-图灵论题

1·哥德尔配数
在形式数论中,哥德尔配数是对某些形式语言的每个符号和公式对应一个叫做哥德尔数(GN)的唯一的自然数的函数。这个概念是哥德尔为证明他的哥德尔不完备性定理而引入的。可计算函数集合的配数有时叫做哥德尔配数或有效配数。哥德尔配数可以被解释为一个编程语言,带有指派哥德尔数到每个可计算函数作为在这种编程语言中计算这个函数的值的程序。哥德尔使用基于素数因数分解的哥德尔配数系统。他首先把唯一的自然数对应到在他所处理的算术的形式语言中的每个基本符号。
为了让配数成为符号序列的整个公式,哥德尔使用了如下系统。给出正整数的序列:x1、 x2、x3 . . . xn ,哥德尔对这个序列的编码是第n个素数自乘这个序列中对应值的次数:
 e n c ( x 1 x 2 x 3 . . . x n ) = 2^ x 1 ⋅ 3^ x 2 ⋅ 5^ x 3 ⋅ . . . ⋅ p n ^x n
依据算术基本定理(又称为正整数的唯一分解定理,即:每个大于1的自然数,要么本身就是质数,要么可以写为2个或以上的质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。),用这种方式获得的任何数都可以唯一的因数分解到素因子,所以可以有效的从其哥德尔数恢复到最初的序列。
哥德尔特别的在两个部分使用这个方案: 首先配数表示公式的序列,其次配数表示证明的序列。这允许他证明在关于自然数的命题和关于自然数的定理的可证明性的命题之间的对应。
哥德尔配数问题在于,它不是唯一的。一般性的想法是把公式映射到自然数上。假设有K个基本符号。可替代的哥德尔配数可以通过把每个基本符号映射到基数为K的记数系统的一个数字来构造,这样由 n 个符号的字母串构成的公式 :
s 1 s 2 s 3 … s n
将被映射成哥德尔数:
h ( s 1 ) × K ( n − 1 ) + h ( s 2 ) × K ( n − 2 ) + ⋯ + h ( s n − 1 ) × K 1 + h ( s n ) × K 0
换句话说,借由将K个基本符号以某种固定顺序摆放,那么每个方程就会产生唯一对应的哥德尔数。但是如果将K个基本符号以另一种固定顺序摆放,则会产生另一种哥德尔编号。也就是说还能有其它的方式来构造序列的哥德尔数。哥德尔配数是参照命题演算和形式算术的符号而构造的.每个符号都被指派了一个自然数。实际上在之前讲述TNT系统的时候,已经给出过具体配数的例子了。
2·邱奇-图灵论题
让我们简略地回顾一下丘奇-图灵论题。我们将在第十七章中相当详细的讨论它——以及它的变种,而现在只需要叙述它的几种形式,把关于其价值和意义的讨论推迟到后面去完成。这里是三种相互联系的叙述此论题的方式:
(1)人所能计算的也就是机器所能计算的。
(2)机器所能计算的也就是FlooP所能计算的。
(3)人所能计算的也就是FlooP所能计算的(即一般递归或部分递归)。
邱奇-图灵论题(Church–Turing thesis,又称邱奇-图灵猜想,邱奇论题,邱奇猜想,图灵论题)是一个关于可计算性理论的假设。该假设论述了关于函数特性的,可有效计算的函数值(用更现代的表述来说--在算法上可计算的)。简单来说,邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。
20世纪上半叶,有很多人尝试对可计算性进行公式化表示:美国数学家阿隆佐·邱奇创建了称为λ演算的方法来定义函数。英国数学家阿兰·图灵创建了可对输入进行运算的理论机器模型,现在被称为通用图灵机。邱奇以及数学家斯蒂芬·科尔·克莱尼和逻辑学家J·巴克勒·罗斯一起定义了一类函数,这种函数的值可使用递归方法计算。
这三个理论在直觉上似乎是等价的-——它们都定义了同一类函数。这导致数学家和计算机科学家相信可计算性的概念可由上述三种等价的计算过程描述。简单来讲,邱奇-图灵论题认为如果某种方法(算法)可进行运算,那么该运算也可被图灵机执行(也可被递归定义的函数或λ函数执行)。
由于邱奇-图灵论题是对计算特性进行描述的一种陈述,故而不能被严格证明。虽然上面提到的三种计算过程可被证明为等价的,但是邱奇-图灵论题最根本的前提--声称一个函数是“可有效计算的”究竟意味着什么--在某种意义上是不甚明确的直觉结果。所以,该论题依然是一个假想。
在20世纪初期,数学家们经常使用一种非正式的说法即可有效计算,所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用“图灵可计算”(或简写为可计算)这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去,所以如何定义它的问题已经不是那么重要了。
之后用于描述有效计算的许多其他机制也被提了出来,比如寄存器机、埃米尔·波斯特(Emill Post)的波斯特系统,组合子逻辑以及马尔可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能力;类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果,所以现在普遍认为邱奇-图灵论题是正确的。
但是实际上该论题不具有数学定理一般的地位,也无法被证明;说是定理不如说是个将可计算性等同于图灵机的提议。如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许,则该论题也是可以被驳斥的。

五:后记

之前说是月更但是这么晚才完成,这里道个歉。笔者几乎是忍着头晕写完了这一篇笔记,因为本身数学水平很低(高中数学都没上完……)。看数学逻辑是真的非常累的一件事的,难就难在对于数学语言的理解上。开篇就提到过,数学语言的使用不同于自然语言。即使用词一模一样,但是在意思上就不是一回事了。就如同前面反复提醒的:“抽象概念与现实本身不可混淆。
这就是为什么在哥德巴赫猜想部分说过的,没有经过专业训练的也与数学或逻辑学爱好者,是没有办法解答这种高深的数论问题的原因。他们提出的理论被驳斥的主要部分,往往就是他们混淆了“数学专用名词”和“普通名词”的意思。这确实是一件不容易的事情,因为我们的自然语言靠着降低表达精准性而提高了交流效率——很多时候话只需要说一半,甚至“指鹿为马”我们都能听明白;所以词不达意没关系,一切尽在不言中。但是在数学逻辑领域,这样的情况是不允许的:一是一二是二,泾渭分明。
计算机科学领域为什么要探讨那么深奥的数学论题?很简单,在学术领域之间存在着名为“同构”的通道,数学理论上可获得方法进行计算的,那么我们就能同构到现实中实现它——计算机中所有的可操作(不论是系统运行还是图形界面),全都首先来自于数学中的计算方法实现(函数计算、代数几何等等)。
这一篇笔记的字数接近最长的那一篇,而且不得不承认,相对来说枯燥很多:这里还省略了很多书里给出的构造程序语言的列表和练习题……对于能看到这里的读者,表示衷心的感谢,谢谢支持!后面预计还有八篇笔记的内容(之前估计错误了,并且之后的笔记长度不敢保证,这几乎是一本百科全书)。
I
丑客
丑客

818 人关注

有感而发
有感而发

2158 人关注