2014/09/18

计算的极限(五):有限的障壁

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/85861

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬

难料的世事

美国普林斯顿大学,1936年9月底。

离乡别井,总是一种冒险。即使是一衣带水的英国与美国,文化与传统上的微妙差异,不知制造了多少惶惑。而图灵这时来到普林斯顿,可以说是双重冒险。他刚申请了普林斯顿的奖学金,但却受不了漫长的等待:精英荟萃的普林斯顿实在太诱人了。虽然图灵当时已是剑桥国王学院的研究员,每年有一笔比上不足比下有余的薪金,但人在他乡,经济上需要更多余裕。多申请一笔普林斯顿的奖学金,自然也合乎常理。

但图灵没有拿到这笔奖学金。

在现在看来,这是件不可思议的事:即使是可计算性理论的奠基人,在这笔奖学金上竟然都得不到普林斯顿的青睐。但从当时的情况来看,图灵的遭遇又很合情合理。当时他只是一名小研究员,在学术上名气不大,论文也不多。即使关于图灵机的论文是可计算性理论的奠基石,但脱胎于逻辑的这个领域仍需时间洗练。没有人能参透未来,所以普林斯顿只能从现实角度考虑,而这个考虑的结果,就是拒绝图灵的申请。

但即使没有奖学金,普林斯顿对图灵来说,依然有着相当的吸引力。当时普林斯顿大学数学系与高等研究院共用一幢大楼,可谓人才济济。单在数理逻辑,丘奇自不用提,丘奇的学生克林(Kleene)和罗瑟(Rosser)也是一等一的好手,就连前文反复提到的哥德尔,在一年前访问过普林斯顿,而且计划再次访问。当时在普林斯顿的学者常常开这样的玩笑:如果希望瞻仰数学界的某位领头羊,只要呆在普林斯顿就好,他们总会过来的。人才与人才是相互吸引的,图灵选择冒险,自然有他的理由。

可惜人算不如天算。克林与罗瑟刚刚拿到博士学位,在外校取得了一席教职,已经离开了普林斯顿。哥德尔下一次访问要等到1939年。当时普林斯顿在可计算性理论上能拿得出手的,大概就只有丘奇。丘奇的λ演算在日后同样枝繁叶茂,但那将是本系列的另一个故事。

然而,丘奇的研究方式与图灵格格不入,他追求一切概念的严谨与形式化,甚至到达了难以容忍任何模糊描述的地步。从丘奇和图灵各自提出的可计算性的模型,也能看出二人研究风格的差异。丘奇的λ演算从模型本身的描述开始就充满了一种严谨精确、不可更改的气度,如同数学王国中又一块晶莹璀璨的宝石,可望而不可即;而图灵的图灵机则更为灵动直观,似乎在机械工房中就能找到它的身影,每个人都能明白它的原理。

可以想象这两种迥异的研究风格相遇时必然产生的矛盾。当年二人如何合作研究,在今天剩下的文件中只能窥见一鳞半爪,细节已然遗失于历史的尘埃之中。但从图灵的信件可以推测,他们一开始的合作并不顺利。尽管丘奇为人友善,尽管图灵勤勤恳恳,尽管二人都可以说是数理逻辑领域中的佼佼者,但他们首次合作并没有产生什么成果。当然,数学研究就是这样,失败才是正常情况,甚至可以说,数学研究就是在不断的失败上前进的。

幸而,图灵在数学上的兴趣不仅限于数理逻辑。从冯·诺依曼听来的一个有关群论的问题引起了图灵的兴趣,他很快就解决了这个问题,令冯·诺依曼对他大加青眼。也幸亏有了这个群论问题,图灵在普林斯顿的第一年不算颗粒无收。

但图灵最希望做的,还是有关数理逻辑的问题,他希望继续留在普林斯顿,跟随丘奇继续研究,虽然剑桥也有着强烈的吸引力。在再三的劝说后,他又申请了第二年的奖学金。这次,因为有冯·诺依曼的保荐,结果毫无悬念。

值得玩味的是,冯·诺依曼的信中只字未提图灵在数理逻辑方面的成就。但以后见之明看来,图灵在可计算性理论上的工作,远远比他在群论上的工作意义重大而深远。此中对比,意味深长。然而我们不能说奖学金的管理者做错了什么,只能说他们错失了一段佳话。

图灵在普林斯顿的生活踏入第二年。作为博士导师的丘奇,向图灵提出了一个新的题目:探求超越哥德尔不完备性定理的方法。

图灵再次抓住了这个机遇。

一致的扩充

哥德尔的不完备性定理(参见希尔伯特之梦,以及梦的破灭以及计算的极限(零)),其实描述的就是数学本身的界限。在此之前,数学家认为真理必可达到,而希尔伯特的那句“我们必须知道,我们必将知道”,正是这项信念奏出的最强音。但哥德尔打破了这种幻想,他证明了,对于强得足以包含算术而又不自相矛盾的数学系统而言,“真”与“可证明”是两个彻底不同的概念。在这些系统中,存在着无法证明的真理。

哥德尔的不完备性定理有两条。

第一,一个“合适的”包含了算术系统的数学系统不可能同时是一致和完备的,也就是说,如果它没有自相矛盾,那么必定存在这样的命题,它们是真的,但无法证明。

第二,在这样的系统中,我们可以将“系统本身没有自相矛盾”表述为系统中的一个命题,而这个命题正是一个无法被证明的真命题。假设我们有一个包含算术系统,但又没有自相矛盾的数学系统T,我们将表达“T没有自相矛盾”的命题记作Cons(T),那么,哥德尔的第二不完备性定理说的就是Cons(T)在T中无法被证明。

你可能会有这样的疑问:如果把Cons(T)当作一条公理加进T中,那么得到的新系统不就能证明T没有自相矛盾了吗?这是否与哥德尔的定理矛盾?

但如果将Cons(T)作为新的公理,我们研究的公理系统就不再是T,而是另一个系统T_1 = T \cup \{Cons(T)\} 。虽然在新的系统T_1中的确能证明Cons(T),但它只表达了原有系统T没有自相矛盾,而对于新系统T_1,它不能表达这一点。结合了新的公理之后,表达系统本身没有自相矛盾的命题同样会产生变化。这就像一场猫捉老鼠的游戏,我们自以为封死了一切退路,把猎物逼进了墙角,但事实却是按下葫芦浮起瓢,在我们不知道的地方又出现了新的漏洞,狡猾的猎物得以全身而退。

值得一提的是,这种对公理系统的扩充方法有其独特之处:虽然新的系统比原来多了一条公理,阐述了原有体系的一致性,的确使公理系统变得更强大,但在某种意义上,这又是最保守的扩充方法。它仅仅假定了原有系统的一致性,看似没有引入什么新的知识,而得出的新系统的一致性也与原来的系统相同:如果原有系统是一致无矛盾的,阐述这一点的新公理自然不会引发矛盾;而如果原有系统本身就存在矛盾,那么它能证明一切命题,无论是真是假,那么加入新的公理也不会改变这一点。

这可能不是最有趣的扩充方法,但却是最稳妥的。如果随便添加公理,我们得到的更有可能得到的是一个自相矛盾的无用系统。与其矛盾,不如稳健。

但要用这种方法在系统内部证明自身的一致性,实际上并不可行。的确,我们可以多次重复添加公理的过程,得到从T_1T_2开始的一系列理论系统,但它们的一致性是相同的,都依赖于起始的数学系统T,而且这一点是可以证明的。既然在起始的系统中不能证明自身的一致性,那么之后的一系列系统,无论重复多少次,都不可能证明自身的一致性。

那么,如果我们重复无限次,添加无限条公理呢?这样的话,无论使用了多少条公理,总有比它们更大的一条公理将会断言前面公理的一致性,一环扣一环,直至无穷,整个系统岂不是无懈可击?

系统的证明

从某个理论T_0 = T 开始,逐次添加关于新理论一致性的公理Cons(T_i) ,不断得到T_1 = T_0 + Cons(T_0), T_2 = T_1 + Cons(T_1), T_3, \ldots ,一直到最后包含无穷条公理的T_\infty ,其中每一条公理都有更大的公理来断言它的一致性。似乎我们就得到了一个超越哥德尔不完备性定理的数学系统。

但事情当然不会那么顺利。

首先,在包含无穷条公理的数学系统中,如何在系统内部谈论它的一致性,这并非顺理成章。的确,从理论上来说,包含任意的无穷条公理的数学系统是存在的。但如果要在这种系统内思考,很快就会遇到困境。先不说在系统中进行推理,就算是阅读一个证明,也并非显然。要理解这一点,需要对“形式证明”有更具体的理解。

一个数学系统内的形式证明,实际上是一串有限的命题组合,其中的命题要么是系统内的公理,要么是此前命题明白无误的简单逻辑推论,而最后出现的命题就是这个形式证明要得出的结论,也就是要证明的定理。这种一环套一环的组合方式,恰好保证了最后结论的正确性。而我们在阅读一个形式证明时,也只需要顺次检查这些命题,看看每一个命题是否本身就是公理或者此前命题的推论,就能验证这个证明的正确性。

而如果要在系统内部用命题表达系统本身的一致性,就要用到哥德尔在证明他的不完备性定理时用到的技术。简单来说,我们需要“阅读证明”的这个过程能够完全机械化,即使将人脑换成图灵机,也可以完成类似的验证。但如果数学系统本身包含无穷条公理的话,这个机械的阅读过程可能甚至连第一步都无法开始:如果有无穷条公理,那么面对一个命题,又如何知道它是否一个公理呢?

打个比方,数学系统好比是座仓库,里边装的都是公理。现在有人给我们一件东西,比如说一本书,我们的任务则是查看仓库里是否有一模一样的存货。如果仓库里只有有限样东西,一个个清点总能完成任务;但如果仓库容纳了无数物件,即使仓库的确有相应的存货,如果清点的次序不当,也有可能永远也碰不上我们的目标。

同样,要判断某个命题是否给定的数学系统中的公理,如果公理只有有限条,那么一个一个比较,总能在有限时间内判断出来。但对于无穷条公理的情况,这种方法有着严重的缺陷。如果检查的命题的确是公理,那么有朝一日总会停止;但反过来,如果我们检查了很久,仍然没有找到它是公理的证据的话,因为我们没有清点公理的一般方法,所以同样无法断言是否有遗漏。

所以一般而言,在一个包含无穷条公理的数学系统中,我们甚至无法在有限时间内机械地判断一个证明是否正确。尽管形式上仍然可以对形式证明进行定义,但我们几乎无法有效地考察这样的定义。同样,在这类系统中,有关形式证明的概念,尤其是系统本身的一致性,也如同处于矛盾中的说谎者,根本无法被表达。在这些系统中,难以谈及有关证明论的问题。

然而,在数学家们平常使用的数学系统中,不乏包含无穷条公理的例子。其中包括策梅洛-弗兰克公理系统,它被认为是现代数学的公认基础;还有皮亚诺算术的一阶逻辑版本,这个版本在数理逻辑的研究中经常出现。虽然这些系统同样包含无穷条公理,但数学家们在使用这些系统进行证明时没有一丝的踌躇,似乎其中形式证明的意义理所当然,与我们之前的结论背道而驰,这又是为什么呢?

答案很简单:这些数学系统拥有特殊的性质,虽然包括无穷条公理,却能在有限的时间内判断某个命题是否其中的公理。在数理逻辑中,这些系统被称为可有效生成的公理系统。

“可有效生成的公理系统”,顾名思义,这种系统里的公理都是可以“有效生成”的,也就是说,存在一台图灵机,可以“生成”所有的公理,将它们一一打印到纸带上,而打印出来的命题则必定是系统中的公理。可以说,这样的公理系统可以约化为一台图灵机。

回到仓库的比喻的话,一个可有效生成的数学系统同样是公理的仓库,但其中有着某种规律。比如一个包揽全世界所有书的仓库(它的别名叫图书馆),要判断某样物品是否有存货就太简单了:只要是书,那就有存货;如果不是书,那就没有。无需费力找到具体的对应,但同样可以确定仓库中是否存在相同的存货。

如果一个数学系统是可有效生成的,那么可以构造一个图灵机来判断某个证明是否正确。它能仅仅承认那些系统内正确的证明,对于错误的证明则一律拒绝。那么,即使有无穷条公理,我们仍然能通过这台图灵机考察关于形式证明的性质,从而可以谈论所有有关证明论的问题,包括我们关心的系统一致性。

而我们希望讨论的扩充系统,也就是通过无穷次扩充得到的数学系统,的确是一个可有效生成的系统。所以,我们对它一致性的讨论是有意义的。

对于读者来说,可能会感觉这些围绕着无穷条公理的讨论仅仅是一种吹毛求疵。但对于数学,特别是数理逻辑而言,精确性无比重要。在日常生活中,我们使用的语言太模糊太杂乱,人们的本意常常迷失在语言当中,有时连人本身都不理解口中的言说。但在数理逻辑中,一切含糊都被符号明晰,没有歧义,没有矛盾,对就是对,错就是错。这种确定性,正是数学真理性的所在。

有限的障壁

无限扩充得到的公理系统T_\infty ,虽然能在其中表达系统本身的一致性,但它的一致性却不像我们想象中的那么显然。虽然对于其中的每一条新公理Cons(T_k) ,都有比它更强大的另一条公理Cons(T_{k+1}) 保证它的一致性,但这真的能证明包含无数条新公理的系统是一致无矛盾的吗?

我们重温一下一致性的定义:一个公理系统是一致无矛盾的,当且仅当系统中不存在对于假命题的证明。也就是说,无论系统有多大有多复杂,只要系统本身不能证明任意一个假命题,比如说“1=2”,那么这个系统就是一致的。

我们现在尝试考虑无限扩充得到的公理系统T_\infty 。要超越哥德尔不完备性定理,就需要在系统内部证明有关系统本身一致性的命题Cons(T_\infty) 。假设系统中存在一个这样的形式证明P ,这意味着什么呢?

我们知道,形式证明的长度是有限的,毕竟无论是人类还是计算机,都无法完整阅读无限长的证明。所以,证明P 用到的公理也只有有限条。既然有限,那么其中形如Cons(T_k) 的公理也有限,对应的k 必然有一个最大值,不妨设为N 。那么,证明P 中的所有公理,在更小的系统T_{N+1} 中早已存在,所以证明P T_{N+1} 中同样有效。也就是说,仅仅在T_{N+1} 中就可以证明T_{\infty} 的一致性,它也蕴含了更小的系统T_{N+1} 的一致性。

也就是说,因为形式证明的长度是有限的,如果无限扩充后的系统T_\infty 能超越不完备性定理,证明它自身的一致性,那么在之前有限次扩充中,必然已经存在一个系统,它能证明自身的一致性。根据之前的论述,这也表示一开始的出发点——也就是系统T ——也能证明自身的一致性,而这是不可能的。

尽管我们尝试用无限来突破不完备性定理,但名为“有限”的障壁挡住了我们的去路。

在某种意义上,我们能够处理的,只有“有限”,而无法处理真正的“无限”。那些我们看似能抓住的“无限”,实际上也只是通过某种“有限”的手段确立的。而在“无限”的海洋中,我们无法辨别的,远多于我们能认识到的。

我们无法认识一切,相对地,我们永远有着等待探索的世界。

既然从一致性的方向无法突破,那么从另一个方向呢?哥德尔不完备性定理断言,对于合适的数学系统而言,一致性与完备性是两立的,那么,是否可以不停地扩充系统,在保证一致性的前提下,使它能证明越来越多的命题呢?最后又是否能得到一个完备的系统,在其中可以证明所有真命题呢?

为了回答这个问题,图灵将眼光投向了无穷的彼岸。

2013/11/03

计算的极限(四):机械计算的圭臬

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/85861

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界

殊途同归

大洋彼岸寄来的论文,对于图灵来说,并不是什么好消息。在看到丘奇的论文后,图灵有过何等反应,至今恐怕已不可考。面对着一位在数理逻辑方面已然小有名气的职业数学家,与自己一起独立发现了相同的突破性结果。往好处想,这说明图灵自己的水平已经达到了当时数理逻辑研究的前沿;往坏处想,重复了别人的结果,哪怕是独立发现的,似乎都有些不对味儿。

然而,在下定论之前,图灵还有一件事情要搞清楚。他和丘奇对“可计算性”的定义,分别建筑在图灵机与λ演算之上。那么,在不同的基础上定义的两种“可计算性”,是貌合神离还是本为一体?

图灵机与λ演算,两者似乎都在平平无奇中暗藏玄机。作为计算模型,它们有很多相似之处,比如自我指涉的能力。但它们看起来又是如此不同,图灵机是一台在工程上能建造的机器,而λ演算则是一个彻头彻尾的数学模型。看起来,要回答这个问题,并非易事。

Lambda演算

图灵机模型

图灵知道,丘奇也知道,他们已经踏入了一个新领域。昔日希尔伯特在他的二十三个问题中,一语带过的那个“机械化的运算”,即将被赋予精确的数学含义。但正因如此,踏出的第一步必须慎之又慎,尤其对于“可计算性”这个最基础的定义,必须做到毫不含糊。为此,为了消除模棱两可之处,图灵机与λ演算是否能力相当,这是个必须回答的问题。

知己知彼,百战不殆。为了解答这个问题,图灵开始钻研λ演算,试图弄清到底λ演算能计算什么。终于,他证明了,所有λ演算能计算的函数,他的图灵机也能计算,反之亦然。也就是说,λ演算与图灵机的计算能力是等价的,两种模型定义的“可计算性”实际上殊途同归。他将这个结果作为附录补充到了他的论文。

对于图灵来说,这既是个坏消息,也是个好消息。坏消息是,他的结果与丘奇的重复了,对于发表文章来说,这不是什么好事情。好消息是,他的结果与丘奇的重复了,但他对可计算性的定义与丘奇的截然不同,而且两种看似毫无关系的定义,在实质上是相同的,这说明,他们对可计算性的定义,这最初的一步踏出的方向是正确的。一个人提出的定义很可能忽视某个方面,但现在两个截然不同的定义引向相同的结果,在交叉印证下,几无出错之虞。

可以说,图灵的工作面世之日,正是可计算性理论呱呱坠地之时。

也难怪纽曼教授一开始不相信图灵的工作。仅仅二十出头,刚刚踏入科学界的年轻人,就解决了如此重要的问题,而且为一个全新的领域立下了奠基石,这种人,即使在剑桥这个英国顶尖学府,也可谓难得一见。倒不如说,一开始不相信,这才是正常的反应。

但即便不相信,数学证明就是证明。即使纽曼教授并不专精于数理逻辑,还是能看出图灵论文的过人之处。他决定为图灵争取发表的机会。

这并非易事。因为从结论上说,图灵重复了丘奇的结果,所以最初联系的几个期刊的编辑都婉拒了纽曼的要求:他们只看到了论文的结论,没看到论文的精髓。最后,纽曼找到了当时伦敦皇家学会学报的编辑,经过三催四劝,终于说服编辑发表图灵的文章。

《论可计算数,及其在可判定性问题上的应用》,图灵的这篇文章,后来被认为是伦敦皇家学会学报发表过的最重要的文章之一。

伦敦皇家学会学报

万变之宗

乘着远洋货轮,图灵的论文很快传到了大洋彼岸,在普林斯顿掀起了一阵旋风。

在普林斯顿高等研究院的哥德尔,与丘奇有过不少碰面的机会。他读过丘奇的论文,大概也听过丘奇本人介绍他的λ演算。但哥德尔对λ演算一直颇有微词。实际上,作为一种计算模型,λ演算从未得到他的认可。它与人们日常接触到的“计算”毫无相似之处,更像是符号的堆砌和推演。虽然其中的计算的确可以机械性地完成,但要证明这一点绝非易事。事实上,这是一个远非显然的定理,证明也相当复杂。总而言之,λ演算并不像机械的计算,更像智慧的推理。

实际上,哥德尔自己也有一套“机械计算”的模型,那正是他在证明哥德尔不完备性定理时发展出来的递归函数体系。这套体系将“机械计算”定义为递归函数能计算的内容,而递归函数,顾名思义,就是可以用某些递归方式定义的整数函数。但哥德尔对他自己的模型同样不满意,原因同样是他的模型似乎需要太多的聪明才智,不像一台机器。

但图灵的论文瞬间就令哥德尔为之折服。

任何人,只要看一眼图灵机的定义,都会认同图灵机的计算完全是机械演算,完全可以造出一台可以运作的实际的图灵机。而更重要的是,图灵机抓住了“机械计算”的神韵。

机械计算是什么?是机器可以做出的计算。但机器可以千奇百怪,要用三言两语抓住本质,似乎不太可能。那么,何不反其道而行之?与其想像这些机器共有的特性,不如寻找它们共有的限制。

这正是图灵在论文中的做法。他总结了以下几个机器计算的限制:

第一:一台机器只有有限个可以分辨的状态;一台机器能分辨的表示数据的符号只有有限种。

开关或开或合,电路或通或断,中间的变化是跳跃式的。即使是连续的电信号,由于不可避免的热噪声影响,通过测量能分辨出的状态同样只有有限个。虽然现代的计算机看似有无限可能,但这只是幻觉。CPU和内存中的电路,数量虽然庞大无比,但总归是有限的,它们的通断形成的不同状态亦是如此。同理,虽然符号、信号在细节上可以有无数种变化,但由于精度等问题,即使是人,也无法事无巨细将所有细节一一分辨出来,更何况机器。

第二:机器的每一步操作需要的时间有一个下限,而每次操作最多只能读入与改写外部有限个符号。在某次操作读写某处的符号后,下一步机器读写的符号与之前符号的距离应该是有界的。

由于物理的限制,不存在速度无限的物体。无论任何机器,都不能在有限的时间内作出无限次操作,当然也不可能有无限次读入与改写。同样,读写头移动的速度是有限的,所以两次操作读写符号的距离当然也有限制。

第三:在某步操作中,机器的行动完全取决于它当时的内部状态以及读取到的符号。

机器就是机器,它应该做的,就是按照预先规划的图纸一步一步执行。没有异想天开,没有灵光一现,只有照章办事,只有步步为营。

这几个限制看起来相当合理,甚至显得理所当然。但就从如此平平无奇的限制出发,图灵用缜密的逻辑说明了,一台服从这些限制的机器能计算的问题,必定可以用一台特定的图灵机解决。也就是说,任何一台服从这些限制的机器,无论设计如何精巧,构成如何复杂,它的计算能力都不可能超越图灵机,无一例外。

我们甚至可以说,图灵机的设计本身,正是这些限制的一种体现。图灵很可能一开始就意识到了这些限制,再由此出发,去定义他的图灵机。哥德尔之所以对图灵机击节叹赏,大概也正因蕴含在它定义中的,图灵对“机械计算”的深刻洞察。相比之下,虽然与之等价的λ演算也尚算精致,但对于“机械计算”只得其形未得其神,显然逊色不少。

现在,希尔伯特在他的问题中那模糊的“机械计算”,终于有了一个精确的定义:机械计算,就是图灵机能做的计算。这又被称为图灵-丘奇论题,正是可计算性理论的奠基石。

除了λ演算与递归函数以外,还有许多计算系统与图灵机等价。波斯特对应问题,计数器机,马尔可夫算法,甚至元胞自动机,这些计算模型都与图灵机等价。但以我们的后见之明来看,图灵机仍然是机械计算最自然最有用的模型之一。

最小的通用图灵机

也正因这篇论文,图灵得到了到普林斯顿读博深造的机会,在丘奇的指导下,得以继续探索可计算性的无限可能。在大洋彼岸等待图灵的,又是可计算性理论的一篇新章。

(如非说明,图片均来自维基百科)

2013/08/31

从玩具陀螺到终极理论

本文已于《艺术世界》杂志发表,禁止转载。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/82139

二十年前的小朋友很好哄,一个陀螺就能打发一下午的时间。大江南北,似乎都有这种转啊转的玩具。记得曾在书上读到,东北小朋友在冰上玩的陀螺要用鞭子抽。身处南国的笔者,冰面与鞭子都未曾见过,而见过的陀螺也都是塑料的,用手一拧,在桌上就滴溜溜地转起来,颜色混合而又慢慢分离,变幻摄人眼球。

还记得有一种会倒立的陀螺,一开始大头朝下转着,慢慢地整个陀螺就会翻过来,变成大头朝上。在科普大师马丁·加德纳的书中,也有提到到这种会倒立的陀螺。玩意虽小,也给世界各地的人带来过乐趣。

那么,陀螺为何转而不倒?也许你会回答,角动量守恒。

通俗来说,角动量守恒就是旋转中的物体倾向于绕着相同的旋转轴,以相同方向继续旋转。如果没有外力作用,旋转永不休止。也就是说,旋转本身也有一种惯性。轻轻推一下旋转中的陀螺,它也只会开始摇摇晃晃,而不会立刻倒下来。

地球本身是个更宏观的例子。数十亿年来,地球围绕着太阳公转,围绕着地轴自转,未有一刻歇息。公转而有春夏秋冬,自转而有昼夜晨昏,日常熟悉的这一切变化并非理所当然,它们来自太阳系形成时,星云旋转的角动量。

但在人力所及之处,要归纳出这个看似简单的定理,竟也花了不少时间。究其原因,我们的世界是如此不完美,摩擦力无处不在,不断消磨着各种运动,以至于大贤亚里士多德竟会认为力是维持物体运动的必要条件,并且整个西方世界这样一错就是一千年。

人们第一次窥视到角动量的一鳞半爪,还是在星空中,那里星体的运动没有摩擦力的阻碍。发现者则是一位眼睛不好的天文学家——开普勒。他自己做不了观测,但他的老师第谷留下了需要的所有资料。天行有常,而在纸堆中,他发现了行星的“常”,也就是后人口中的开普勒三定律,阐述了行星围绕太阳旋转的规律。而其中的第二条——无论在轨道何处,行星与太阳的连线在相同时间内扫过的面积相同——实际上就是角动量守恒的体现。

之后的牛顿更是将开普勒的工作发扬光大。他的力学三定律以及万有引力,用可以计算的公式诠释了开普勒的发现。而在牛顿力学中,人类终于完全抓住了旋转的规律,可以随意计算有关旋转的一切,而角动量守恒也成为了理所当然的推论。

对于客观规律,感性认识只是不甚可靠的第一步,可以量化并计算的理论却有着实实在在的用处。发电机和电动机利用旋转的力量,转化着不同形式的能量,构成了现代文明的基石。而在设计中,对旋转的计算直接关系到机械的安全和性能。

陀螺仪则是对于角动量守恒最为直接的应用。强有力的转动使它指向固定的方向,无论是大风大浪还是火箭发射,都不能使它的指向偏离一分半毫。也唯有如此,它才能指引船只、飞机甚至宇宙探测器沿着指定的方向航行,到达最终的目的地。

角动量守恒是如此自然,人们理所当然地接受了它。

但有一位数学家并不接受这种理所当然,她叫埃米·诺特。

Noether

作为一个女数学家,生于19世纪末的德国并不算件好事情。直到20世纪初,男女同校仍被视作会“颠覆学界秩序”的举动,而大学教授仍是男性的专利。对诺特而言,即使她的父亲就是数学教授,即使她才华横溢,求学也并非理所当然。她只能旁听,而且还要取得教授的许可。

即使获得了博士学位,即使指导者是当时有着“不变量之王”美称的大数学家戈尔丹,即使工作受到了广泛的肯定,在毕业后最初的七年,诺特的收入仅仅来自家人的接济。她工作的机构,埃朗根数学研究所,从未向她支付过工资。

一分钱都没有。

在1915年,事情似乎有了转机:两位数学巨擎,希尔伯特与克莱因,邀请诺特到当时数学界的中心——哥廷根大学——工作,研究广义相对论的数学。当时爱因斯坦还在摆弄他的场方程,苦恼于其中的一些异常之处,而希尔伯特也在摆弄相似的场方程。他们希望诺特在不变量理论方面的造诣,能帮助厘清广义相对论中的数学。

这无疑是对诺特才华的肯定。

但当时的哥廷根更关注诺特的性别。希尔伯特希望为诺特谋得一个私人讲师的职位,但哥廷根的教授们显然不希望有女人进入他们“神圣”的大学。他们的借口之一是“不希望我们的士兵回归大学后,发现竟要向女性求学”。向来沉稳的希尔伯特也不禁大动肝火,并说出了那句著名台词:“我不明白候选人性别与私人讲师资格有何相干,毕竟这里是大学,不是澡堂!”但要改变那帮老顽固,一年半载是不可能的。诺特的课程只能挂上希尔伯特的名义才能开讲。她仍然没有职位,仍然没有收入,仍然需要家人接济。

然而希尔伯特毕竟是伯乐,诺特甫一开始在哥廷根的工作,就在数学物理方面崭露头角。

黑洞模拟图

粗略地说,广义相对论的新思想在于“时空会随着物质弯曲”的概念,但要将这些抽象的概念转化为实实在在的数学方程,是件异常困难的事:需要新的数学工具,需要新的数学想法,而且还要排除时不时冒出来的那些物理上不可能的性质。希尔伯特发现他的场方程中,正出现了看似不可能的毛病。在经典物理中理所当然的守恒量,比如能量、角动量,在他的场方程中似乎不再守恒。到底这是致命的缺陷,还是新定律的喻示?希尔伯特期望诺特解决的,就是这样的问题。

也许这种问题正适合诺特来回答。毕竟,她仅仅是踏在科研路上这个事实,就已经冲击了当时多少人心中那陈腐的“理所当然”。

而诺特的回答优美得令人震惊。她发现,守恒量的存在并非理所当然,而是宇宙规律对称性的体现。无论任何物理理论,只要符合某种对称性,那么这个理论中一定有一个对应的守恒量,这个量不会随着时间而变化。如果物理定律在时间长河中的每一个时刻都相同,它就有着所谓的“时间平移不变性”,对应着的守恒量就是能量。如果指向茫茫宇宙任何一个方向,物理定律仍然不变,那么它就有着“旋转不变性”,对应着的守恒量就是旋转的角动量。

无论什么宇宙,无论什么规律,有一个对称性,就有一个守恒量。而角动量,不过是旋转不变性所对应守恒量的名字而已。这就是诺特定理。

希尔伯特的场方程,仍然保有经典物理的对称性,但因为方程本身已改头换面,对称性所对应的守恒量也变得面目全非。经典物理中的守恒量不再守恒,这仅仅因为我们有新的守恒量,而并不构成新物理的障碍。

这就是诺特的答案,一个连爱因斯坦也大加溢美之辞的答案。

诺特定理为现代物理学打开了一扇新的大门。有了诺特定理,物理学家开始学会通过宇宙本身的对称性推测物理定律的性质。人们认识到,对称性是探究物理的指路明灯。

来自http://fafnir.phyast.pitt.edu/particles/conuni6.html

来自http://fafnir.phyast.pitt.edu/particles/conuni6.html

除了时空本身宏观的对称性以外,物理学家还开始探索各种局部的对称性。在量子场论中,人们发现除了时间和空间以外,物理定律在局部还依赖额外的量,有着额外的对称性。这些被称为“规范对称”的对称性,实际上可以看作更为抽象的数学空间中的旋转对称性,而它们也有着相应的守恒量。基于这些新的对称性,人们建立了一整套物理理论,被称为“规范场论”。

这套依赖对称性的物理方法,获得了前所未有的成功。四种基本力中的三种,都能用规范场论来解释,合起来就是目前最为成功的粒子物理理论——标准模型。正因为规范场论如此成功,一些物理学家认为能描述一切的终极理论应该也是一个规范场论,一个比标准模型有着更高对称性、更多对称美的规范场论模型。

没有人知道终极理论会是什么,但每个人都认为它一定拥有高度的对称美。而陀螺转而不倒,只是这种美的一个小小体现而已。

【如非特别说明,图片来自维基百科】

2013/06/23

素数并不孤独

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/82114

数学是科学的女王,数论是数学的女王。

——高斯

数论,是研究数字的一门数学分支。如同大海,它清澈透明而又深不见底。它的基础概念,自然数、加法、乘法,每个小学生都清楚;但关于自然数的定理,却可以让人穷尽一生而不得其解。而这篇文章要介绍的,只是这个广阔海洋中一个小小的海域。即便如此,我们仍未知道此处海深几何,尽管最近张益唐的突破性工作,使我们比以往更接近真理,但这远远不够。

尽管笔者才疏学浅,有恐贻笑方家。但如能为读者勾勒出一点点数学之美,也不枉费一番心思。



素数何时成双对



可以说,素数是数论中最基础而最重要的概念。如果一个大于二的正整数,除了1和它本身之外,不是任何数的倍数,那么它就是一个素数。比如说,6不是一个素数,除了1和它本身以外,它还是2和3的倍数;而5则是一个素数。

在古希腊,人们已经有了素数的概念,对素数的研究也略有所得。在欧几里德的《原本》中,第七、八、九篇讲述的是“关于整数及其比值的性质”,实际上也就是数论。在这几卷中,欧几里德指出了今天所说的“算术基本定理”:将自然数分解成素数乘积的方法是唯一的。也就是说,如果用乘法的眼光来看自然数,那么素数就是自然数的最小组成单元。它们不能被分解成更小的数的乘积,而所有自然数都可以分解成它们的乘积。

那么,我们自然要问:素数作为自然数的组成单元,它们有多少个?

有无限个,欧几里德不仅回答了这个问题,还给出了一个经典的证明。

不妨反设只有有限个素数,考虑它们的积N ,它是一个有限的自然数。所以,N+1 也是一个自然数,它也应该是一些素数的积。但根据假设,每一个素数都不整除N+1 ,这不可能!所以,素数必定有无限个。

这个精巧的证明,是人类探寻素数奥秘的第一步。

2、3、5、7、11、13……最初的几个素数,要找出来并不困难,但随着数字增大,如果一个一个数字按照定义去筛选是否素数,工作量会很快变得十分庞大。同为古希腊数学家的埃拉托色尼,给出了一个比较省力的算法,后人称之为埃拉托色尼筛法。

首先,列出从2开始的数。然后,将2记在素数列表上,再划去所有2的倍数。根据定义,剩下的最小的数——在这里是3——必定是素数。将这个数记在素数列表上,再划去所有它的倍数,这样又会剩下一些数,取其中最小的,如此反复操作。最后剩下的都是素数。

埃拉托色尼筛法

当古希腊人用这种方法计算出长长的素数列表时,他们也许也曾惊异于素数分布的秩序缺失。这些自然数的组成单元,在自然数中的排列却毫无规律,时而靠近,时而疏远。用类似欧几里德证明中的构造,我们知道,两个相邻素数之间的距离可以要多大有多大。而随着数目越来越大,相邻素数之间的距离似乎也越拉越长。

在无限延伸的自然数集中,向无穷的地平线望去,虽然仍有无穷的素数,但它们似乎也愈变孤独。

这种孤独甚至是可以度量的。在十八世纪的尾巴,年仅15岁的高斯独立提出了一个猜想:在n附近素数的密度大约是n的对数。也就是说,相邻素数之间的平均距离大概与它们的对数成正比,虽然增长很慢,但却义无反顾奔向无穷。但即使是高斯,也无法严格地证明他的猜想,要等两个世纪后的阿达玛(J. Hadamard)和德拉瓦莱普森(C. J. de la Vallée-Poussin),才能将这个猜想变成现在的“素数定理”。

虽然如此,偶尔也会有成对出现的素数,它们之间只相差2。像这样成对出现的素数,在那些孤独的同伴看来,无疑是异类。

它们被称为孪生素数。



漫天星河难理清



一个自然的问题是,孪生素数有多少?

孪生素数猜想断言,有无限对这样的孪生素数。但还没有人能严格地证明这一点。在1849年,数学家A. de Polignac甚至猜想,对于任意的偶数2k ,都有无数对相邻的素数,它们的差恰好是2k

这不是一个容易的问题。素数是乘法的产物,而孪生素数的定义则涉及到加法。即使只是加上2,也需要同时用到自然数的加法和乘法的性质。而在数论中的很多看似简单但无比困难的问题,比如哥德巴赫猜想和华林问题,核心也在于加法和乘法的交织。这种相互作用给数论学者们带来了无穷的头痛,以及对咖啡的无尽渴求。

与此同时,行外人的评价却似乎异常中肯:“为什么素数要相加呢?素数是用来相乘而不是相加的”。

当然,如果只将素数用在只与乘法有关的问题上,事情当然简单得多。但如果我们想要更多地了解自然数的玄机,那必然涉及到加法和乘法的相互作用。缩在“容易”的圈子里从来无补于事。如同探险家一般,数学家也有着征服难题的渴望,因为在那困难的山巅上,有着无尽的风光。为了难题产生的新方法、新思想,可能会开辟出意想不到的新天地。

素数在二维平面的一种表达

孪生素数的难点在于,它是一个关于素数的具体分布的问题,而我们对素数的具体分布知之甚少。素数定理只告诉我们素数的大体分布,而对于具体一个个素数的位置却无能为力。如同繁星,素数点缀着自然数的夜空,放眼望去,它们朝向无限的地平线愈见稀薄。但要想分清这无限繁星中的每一颗,即使用上最好的望远镜,也无可奈何。

所以,在很长一段时间里,对于孪生素数猜想,人们仍然停留在揣测和估计的层面。

首先尝试直接猜测的,是英国数学家哈代(G. H. Hardy)和李特尔伍德(J. E. Littlewood),他们在1923年开始了一系列的猜测。

G. H. Hardy

素数定理告诉我们,对于足够大的自然数N,在N附近随机抽取一个自然数n,它是素数的概率大概就是(\ln N)^{-1} 。那么,在同样的区间,随机独立选取的两个数都是素数的概率就是之前概率的平方,也就是(\ln N)^{-2}

那么,在N附近随机抽取一个自然数n,n和n+2是一对孪生素数的概率是否就是大概(\ln N)^{-2} 呢?很遗憾,并非如此,因为n和n+2并非完全独立的,所以不能直接应用之前的结果。不过这个估计虽不中亦不远,只要乘上一个修正系数,借此表达两个数相差2的性质,就能得到对孪生素数密度的估计:2 C_2 (\ln N)^{-2} 。在这里,修正系数C_2 是一个关于所有质数的无穷乘积。如果密度确实如此,那么显然有无限对孪生素数,孪生素数猜想应该是正确的。

实际上,这是所谓“第一哈代-李特尔伍德猜想”的一个特殊情况,难度甚至远高于孪生素数猜想:它不仅隐含了孪生素数猜想,而且对具体的分布作出了精细的估计。虽然上面的论证看上去很诱人,但它并不是一个严谨的证明,因为它的大前提——素数是随机分布的——本来就不成立。素数的分布有着深刻的规律,远远不是一句“随机分布”所能概括的。

但哈代和李特尔伍德并非等闲之辈,作为当时英国的学科带头人,既然提出这个猜想,当然经过了深思熟虑。现在看来,依据之一是,望向无限,素数的分布的确看似随机:对于那些“简单”的操作(比如说加上2)来说,数值越大,越靠近无限的地平线,看上去也越“随机”。所以,在考虑各种素数形式的分布时,假定素数按照素数定理的密度随机分布,不失为一个估计的好办法。更为重要的是,数值计算的结果也与哈代和李特尔伍德的猜测所差无几。这更增添了我们对这个估计的信心。

然而,猜测只是猜测,不是严谨的证明。无论用数值计算验证到什么高度,有多符合,对于无限而言,都是沧海一粟。李特尔伍德本人就曾证明过一个类似的结论。

人们此前猜测,小于某一个数N的素数个数\pi(N) 必定小于所谓的“对数积分”函数\mathrm{li}(N) ,而根据素数表,这个规律直到10的14次方都成立。但李特尔伍德在1914年证明了一个惊人的结论:对于足够大的N ,不仅\pi(N) 可以大于\mathrm{li}(N) ,而且它们的大小关系会无穷次地逆转!但直到今天,对于第一次打破这个规律的N,我们仍然不知道它的具体数值,只知道它大概是个有三百多位的数。

这个例子足以说明素数可以多么深不可测而又出人意料,同时提醒我们,面对无限,不能掉以轻心。无论有多少计算的证据,都不能轻易下定论。征服无限的工具,只有严谨的数学证明。



狂沙淘尽始得金



既然难以知道孪生素数具体有多少,那么不妨换个思路:孪生素数最多能有多少呢?

这就是数学家的思路,如果正面久攻不下,那么就从侧面包围。当难以直接得到某个量时,数学家的“本能”会指引他们,尝试从上方和下方去逼近,证明这个量不可能小于某个下界,或者不可能大于某个上界。如此慢慢缩小包围圈,就有希望到达最终的目标。

而在1919年,挪威数学家布伦(V. Brun)走的就是这么一条路:他证明了,孪生素数的密度不可能超过O(\frac{N(\ln\ln N)^2}{(\ln N)^2}) 。籍此,他证明了所有孪生素数倒数的和是有限的。要知道,所有素数倒数的和是无穷大,可见孪生素数在素数中有多么稀少。人们将所有孪生素数的倒数和称为布伦常数,它的具体数值大约是0.87059…。

关于布伦常数,还有个有趣的小插曲。1994年,美国一位教授在计算布伦常数时,无意中发现当时英特尔公司的奔腾处理器在计算浮点除法时,在极稀有的情况下,会产生错误的结果。虽然英特尔声明这种错误对于日常使用来说不足为患,但对于消费者来说,这种托辞实在难以接受。最后,英特尔不得不承诺免费更换有问题的处理器。帮助发现硬件问题,这可算是数论在现实中的一个小小应用。

有FDIV问题的芯片

但布伦的证明意义远不止于此。他的这个证明,正是现代筛法的开端。

布伦所用的筛法,根源可以追溯到古希腊的埃拉托色尼筛法。还记得我们怎么用埃拉托色尼筛法列出素数表吗?每次获得一个新的素数,我们都要划去所有新素数的倍数,然后剩下最小的数又是一个新的素数。用类似的方法,我们可以估计在某个区间中,比如说在N 2N 之间,大约有多少素数。

首先,我们假设手头上已有足够大的素数表(大概到\sqrt{2N} 的所有素数)。用这个素数表,我们打算把从N 2N 的所有合数都划去一遍,剩下的就是素数。对于每个素数p ,我们将所有p 的倍数划去一遍。在N 2N 之间,对于每个素数p ,大约有N/p 个这样的倍数。当然,如果N 不是p 的倍数,这样的估计会有误差,但在数学家看来,只要能把握误差的大小,最终仍然可以得到正确的结论。

这样,剩下的数的个数就是N 减去所有N/p 的和,是这样吗?并不尽然,因为有些数可能被划去了几次。比如说1000,它能被2整除,也能被5整除,于是在处理2和5的倍数时,它分别被划去了两遍。对于每一对素数p_1, p_2 ,每个p_1 p_2 的倍数在之前都被划去了两遍,而我们只希望将它们划去一遍。为了得到正确结果,我们需要对这些数作出补偿:将这些数加回去,一共是N/p_1 p_2 个,加上一点点误差。

但这就是尽头吗?如果考虑三个素数的倍数,我们发现补偿得又太多了,需要重新划去;继续考虑四个素数的倍数,划去得又太多了,需要重新补偿……如此一正一反,损有余,补不足,一项一项估计下去,才能从自然数的海洋中,精确筛选出所有我们想要计算的那些素数。

但我们是否需要做到如此精细呢?在整个计算中,虽然每一项看似简单,但简单的代价是误差。虽然每一项的误差很小,但因为数目巨大,累土而成九层之台,累计误差可以比需要估计的量还要多。所以,在现代的筛法中,过于精细反而是一种累赘。况且,我们的目的是获得上界或者下界,所以结果无需完美,只需误差可控。一般而言,由于越到后面的项贡献越小,往往忽略它们的计算,直接将其计入误差。这样可以有效减少需要计算的项的数目,同时也能间接减少误差。当然,如果忽略的项太多,它们引起的误差又会太大,也会导致不够精确的结果。

布伦相对于前人的改进,正在于此。如果盲目计算所有的项,必然深陷误差的泥沼。而布伦则大胆截去那些贡献很小却占绝大多数的项,而对于剩下的项也果断采用更粗放的近似来简化计算。虽然看似不依章法,但通过仔细调校,布伦得以有效控制总误差,从而获得他想要的结果。

布伦的这个思路,开启了解析数论之中一大类方法的大门。我们不知道怎么数素数,是因为它们的分布实在难以捉摸。而现在,布伦的筛法指出了一条用简单的集合来逼近素数集合的道路,这自然令数学家如获至宝。

在更精细的筛选与更微小的误差之中寻找那一线的平衡,这大概是筛法的醍醐。但这样的平衡,显然依赖于我们如何估计每一项的具体数值。可以每项分开估计,但合起来也无伤大雅。无论做法如何,估计的误差越小,筛选可以越深入,结果也越逼近真实。即使估计方法不变,如果有更好的方法决定每一项的取舍,取贡献大而误差小之项,而舍贡献小而误差大之项,当然也能得到更好的结果。

但为何拘泥于每一项?对于每一项,为什么要么取要么不取,不能站在中间立场吗?只要能控制误差,将每一项拆解开来,根据贡献和误差来赋予不同的权值,再求和,这样的结果岂不是更精细?再者,有时不拘泥于素数,放松限制去筛选那些“殆素数”,也就是那些只有少数几个素因子的数,在某些情况下也能得到更好的结果。在严谨的前提下,只要能做出更好的结果,数学家对于突破原有思路毫不犹豫。

这就像一场对素数的围捕战。数学家们拿着筛法这个工具,不断打磨它、改装它,不断练习,正着用,反着用,与别的领域的工具配合着用,绞尽脑汁发明新的用法,殚精竭力用它来围捕那些调皮的素数。欲擒故纵,反客为主,无中生有,李代桃僵,数学家们在对各种各样素数的围捕中,借着筛法,将一套兵法使得淋漓尽致,精彩之处,三国亦为之失色。

在筛法的力量下,孪生素数终于露出了一鳞半爪:

在1920年,同样是布伦,证明了有无穷对9-殆素数,它们之间只相差2。所谓9-殆素数,或者更一般的k -殆素数,就是那些至多有k 个素数因子的自然数(包括重数)。而1-殆素数就是素数。模仿哥德巴赫猜想的记号,布伦证明的就是(9 – 9)。

在1947年,匈牙利数学家雷尼(A. Rényi)证明了,存在一个常数k ,使得有无穷对自然数m, p ,其中p 是素数,m 是一个k -殆素数,而两者之间只相差2。也就是说,他证明了(k – 1)。

在1950年,挪威数学家塞尔伯格(A. Selberg)证明了,有无穷对整数n n+2 ,它们的素因子一共至多有5个。而孪生素数定理相当于素因子至多有2个的情况。

在1966年,意大利数学家E. Bombieri与英国数学家H. Davenport证明了,孪生素数的密度至多是8 C_2 (\ln N)^{-2} 。也就是说,孪生素数的数量至多是哈代与李特尔伍德所估计的4倍。

陈景润

在1978年,在证明了哥德巴赫猜想的(1 + 2)后,陈景润用相同的筛法改进了雷尼的结果:他证明了,有无穷对自然数m, p ,其中p 是素数,m 是一个2 -殆素数,而两者之间只相差2。也就是说,他证明了(2 – 1)。

而最新的结果则是D. Goldston、J. Pintz和C. Yildirim在2009年发表的。他们证明了,两个素数之间的差距,相比起平均值而言可以非常小。在假定某个强有力的猜想后,他们还证明了,存在无限对素数,它们之间相差不过16,与目标的2只有八倍的差距。但问题在于,即便16这个数目相当诱人,但他们的假定过于强大,强大得不像是对的,也使人们对他们结果的信心打了个折扣。

在整个过程中,数学家们动用了解析数论中的大量工具:L函数、西格尔零点的估计、多种版本的筛法、克鲁斯特曼和的估计、自守形式,如此等等,不一而足。每样工具,都是心血的结晶。但即便如此,我们离孪生素数猜想还很遥远。尽管Goldston、Pintz和Yildirim的结果非常强大,但也不能在无假定的情况下,推出有无穷对素数,它们相差恰好是一个有限的确定值。

虽然只差那么一点点。只要关于所谓“素数分布水平”的引理稍微强一点点,就能得到有无穷对相差不远的素数的结论。但就在这个关口,人们却处处碰壁。希望就在伸手可及之处,却似乎总是差那么一点点。“此路不通”的想法开始弥漫开来。

在众人束手无策之际,当时默默无闻的张益唐向《数学年刊》提交了一份论文。



梅花香自苦寒来



一份三十公分的意大利面包,纵向剖开,抹上金枪鱼泥,放上四片奶酪,放到烤炉烤一分钟,撒上生菜,铺上酸黄瓜和番茄,包起来,切成两半,就是又一个三明治。

这也是张益唐曾经蹉跎的岁月。

张益唐

在博士毕业后,因为种种原因,虽有真才实学,但张益唐未能在学术界找到一份工作。为了生活,他不得不打工维持生计。即使在他的同学帮助他,找到新罕布什尔大学的一份代课讲师工作后,即使在转正成为一名大受学生好评的讲师后,正式而言他仍不是一名研究人员。

时运不齐,命途多舛;冯唐易老,李广难封。

但数学无需官方认可,研究也不需要正式的职位。张益唐受过正式的数学研究训练,有扎实的功底,有充分的能力,知道怎么去做研究,心里也时刻揣着数学。即使没有正式的职位,他骨子里仍然是一位研究数学的学者。

而他心里装着的,正是素数的分布问题,特别是孪生素数。即使没有正式的研究职位,他仍然做着一名研究者会做的事。他紧跟当前解析数论学界的发展,阅读了J. Friedlander和H. Iwaniec在筛法上的突破性工作,阅读了Goldston,Pintz和Yildirim关于素数间隔的工作,还有很多不同的新工作。他思考着新的方法,尝试沿着前人的路径走下去,相信能用新的技巧,把道路走通,证明有无穷对相差不远的素数。

但这谈何容易!即使从Goldston等人强有力的方法出发,要得到想要的结果,也难倒了众多学者。张益唐花了三年时间,不断尝试新的方法,屡战屡败,屡败屡战。数学研究,莫不如是。

终于,在2012年6月,他到朋友家作客时,灵光一闪,找到了开启关键的钥匙。

要说起来,张益唐的方法并非那种横空出世的新构想,而是利用现有的工具,用新的策略将它们组合起来,再加上一点点新的思想。Goldston等人所用的筛法相对精细,但却稍欠回旋余地,而张益唐稍稍放松了这个筛法,虽然能作出的估计稍欠精细,却换来了更大的游刃之余,得以对筛法中误差与精细的天平作出更精巧的调整,结合一些新的结果,特别是Iwaniec等人的工作,反而能获得更好的估计。箇中精彩之处,恕笔者学识浅薄,难以一一尽述。

用他的新筛法,张益唐证明了,有无穷对素数,它们相差不过七千万。他将他的新方法与新结论,用简洁明了的语言,写成了一篇论文,投稿到数学界的顶级期刊《数学年刊》。

这篇论文名为Bounded gaps between primes(《素数间的有界间隔》)。

收到这篇论文的编辑想必十分意外。在一所不起眼的大学做着讲师的工作,在数学的研究共同体中也不活跃,之前一篇论文还是十多年前发表的,这样的一位默默无闻的数学家,突然声称自己解决了一个困扰众多学者几十年的问题,引起的第一反应自然是怀疑。但毕竟,数学证明就是他学识的证明,他的论文写得如此清楚明白,而所用的方法又是如此合情合理,这冲破了原有的一点点怀疑。编辑认为,张益唐的结论很可能是对的,而他的方法对于解析数论而言,也可能是个重要的进步。

因为很多数学证明都相当艰深晦涩,即使是同一个领域的专家,有时也要花上一大段时间来咀嚼揣摩,才能断定证明是否无误。所以,数学论文的审稿时间通常不短,少则数月,多则数年,期间匿名审稿人通常需要通过编辑与作者多次通信,才能决定一篇论文的命运。而张益唐的论文是如此激动人心,编辑认为他们等不起如此漫长的时间,于是对他的论文进行了“特殊对待”。他们请了筛法方面的大家Iwaniec教授与另一位匿名审稿人(可能是Goldston)来审核这篇论文,很快就有了回音。

两位审稿人都认为这篇文章没有明显的错误。实际上,评审报告中写着这样的评价:“论文的主要结果是第一流的”,“在素数分布领域的一个标志性的定理”。从论文寄出到审稿结束,仅仅花了三个星期的时间。

自此,消息不胫而走。在哈佛大学的丘成桐教授,知悉这个消息之后,很快邀请了张益唐来哈佛做关于他的工作的学术报告。消息很快在数学界与新闻界传开,张益唐几乎是一夜之间,从默默无闻变成举世知名。据说,他的妻子听说有记者要采访时,跟张益唐讲的第一件事,就是把发型整理一下。

作为励志故事,这个结尾再好不过了。



路漫漫其修远兮



当然,故事仍未结束。

在数学界中,对于久攻不下的问题,一旦有人打破一个缺口,其他人很快就会跟进,把缺口弄得更大。张益唐的结果也不例外。

在张益唐的论文中,他给出的结果是,存在无数对相邻素数,它们的差相差不过7000万。但这只是一个估计,并非张益唐的方法能得到的最好结果。在论文出炉后,一些数学家吃透了新方法,开始试着改进这个常数。

张益唐的论文在5月14号面世,两个星期后的5月28号,这个常数下降到了6000万。

仅仅过了两天的5月31号,下降到了4200万。

又过了三天的6月2号,则是1300万。

次日,500万。

6月5号,40万,连原来的百分之一都不到。

在笔者写下这行的今天,剩下的只有区区的25万。

(注:截至6月23号的今天,常数已下降到12000,大约是原来的五千分之一

这些结果,可以说是互联网的结晶。这样快的改进速度,对于仅仅依靠一年发行数次的期刊做研究的时代,完全是不可想象的。而在今天,数学家们在网上,你一言我一语,不停发布最新的思考和计算,以最高的速度,汇聚所有人的智慧,才能创造出如此奇观。

张益唐带来的影响不止于此。利用他的新方法,可以解决更多的问题。Pintz指出,从张益唐的工具出发,可以得知存在一个常数C ,使得对于每C 个连续偶数,都存在无穷对相邻的素数,它们的差是这些偶数之一。也就是说,Polignac的猜想,起码对于1/C 的偶数来说是正确的。所以,不仅素数本身难以捉摸,它们之间的差更是剧烈起伏不定。

实际上,大数学家Erdős在1955年就猜测,相邻两对素数差的比值,可以要多大有多大,要多小有多小。而同样借助张益唐的工具,Pintz不仅证明了这个猜想,而且证明了比值之差以不低的速度趋向于两极分化。用他本人的话来说:在刚刚过去的几个月里,一系列十年前会被认为是科幻小说的定理都被证明了。

但孪生素数猜想本身又如何呢?我们知道,如果将张益唐论文中的常数从七千万改进到2,就相当于证明孪生素数猜想。既然现在数学家们将常数改进得如此的快,那么我们是否已经很接近最终的目标呢?

很遗憾,实际上还差很远。

张益唐的方法,本质上还是筛法,而筛法的一大问题,是所谓的“奇偶性问题”。简单来说,如果一个集合中所有数都只有奇数个素因子,那么用传统的筛法无法有效估计这个集合至少有多少元素。而素数组成的集合,恰好属于这种类型。

正因如此,当陈景润做出哥德巴赫猜想的突破性结果(1 + 2)时,他得到的评价是“榨干了筛法的最后一滴油”。因为如果只靠筛法,是无法证明哥德巴赫猜想的。(1 + 2)是筛法所能做到的最好结果。

但数学家们从不固步自封。要想打破“奇偶性问题”的诅咒,可以将合适的新手段引入传统筛法,籍此补上筛法的缺陷。张益唐的出发点——之前提到Goldston,Pintz和Yildirim的结果——正是这种新思路的成果。但对于孪生素数猜想而言,这些进展仍然远远不够。学界认为,虽然不能断定张益唐的方法,即使经过改进,是否仍然不能解决孪生素数猜想,但可能性似乎微乎其微。

但不能低估人类的才智。发明割圆术的刘徽,他对于无知的态度更适合我们:

敢不阙疑,以俟能言者!

参考资料:

Bounded gaps between primes, Yitang Zhang, Annals of Mathematics

Open question: The parity problem in sieve theory, Terence Tao, http://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/

Are there infinitely many twin primes?, D. A. Goldston, http://www.math.sjsu.edu/~goldston/twinprimes.pdf

关于相邻素数之差的笔记(张益唐及其他), 木遥, http://imaginary.farmostwood.net/592.html

Polymath上常数改进的页面:http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes

张益唐和北大数学78级, 汤涛, 数学文化

张益唐的照片来自新罕布什尔大学网站,其余图片来自Wikipedia。

2013/04/14

计算的极限(三):函数构成的世界

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/80229

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定

函数构成的世界

Alonzo_Church

丘奇作为图灵在数学上的前辈,思考的问题自然比图灵要深远得多。图灵考虑的问题,仅仅是希尔伯特的可判定性问题,而丘奇当时思考的,是如何重构数学的基础。

当时正是第三次数学危机勃发之际,数学界各路人马对数学基础应该置于何处争论不休。当时公理化集合论刚刚建立,作为新事物,自然有人持观望态度,而丘奇就是其中一位,他觉得自己可以创造一个更好的理论,以此作为数学的基础。与其选择集合与包含这两个概念,他选择了数学中另一个重要的概念:函数。

数学家眼中的函数,比你想像的要广泛得多。在中学数学中,说到函数,自然会联想起它在平面直角坐标系的图像。这是因为中学数学中的函数,大部分情况下不过是从实数到实数的映射而已。而数学家眼中的函数,可能与程序员眼中的函数更相似:它们更像是一个黑箱,从一边扔进去某个东西,另一边就会吐出来另一个东西。

我们并没有限定能扔进黑箱的东西。事实上,将黑箱本身扔进黑箱也是可以的。对这种把戏,数学家们再熟悉不过了,在泛函分析这一数学分支中,数学家们就经常研究一种叫“算子”的数学概念,在某些特殊情况下,就是那些将一个函数变成另一个函数的函数。所以,不去限定能扔进黑箱的东西,似乎也没什么问题。

总而言之,函数就是将一个函数变成另一个函数的东西。那么,要用符号表达这么普遍的函数概念,我们需要什么呢?

首先,就像在方程中我们用x, y, z等等符号表示未知数,我们也希望能用符号表示未知函数。我们将这些表示未知函数的符号称为变量。

其次,如果我们手上有两个函数MN,那么我们自然希望研究函数N被函数M“处理”之后会变成什么。也就是说,既然M是一个函数,能将一个函数变成另一个函数,那么M会将N这个函数变成什么呢?即使不知道具体的过程,我们也希望能表达最后的结果。所以,我们将NM处理后得到的结果记为(M \, N)。这被称为函数的应用(application)。

最后,也是最抽象的概念,就是函数的抽象(abstraction)。

我们可以用变量x来表示未知的函数,自然也可以用x来构造更多的函数。比如(x \, x)就表示函数x应用到自己身上的结果,而((x \, x) \, y)就表示将刚才得到的结果应用到另一个未知函数y上得到的结果,如此等等,不一而足。如果我们将变量x替换成一个具体的函数f,那么这些包含变量x的表达式就会变成包含具体函数$f$的表达式。

也就是说,如果我们有一个包含变量x的表达式M,对于任意一个函数f,我们可以将它对应到一个新的表达式,记作M(f),而这个新的表达式是将M中的所有x替换成f所得到的。比如说,如果M=(x \, x),那么M(f)=(f \, f)M((y \, y))=((y \, y) \, (y \, y)),等等。

一个表达式也是一个函数。我们从表达式M出发,可以得到把一个函数$f$对应到另一个函数M(f)的方法,而这正是一个函数。也就是说,我们能从一个表达式“抽象”出一个函数。我们将这个函数记作\lambda x. Mx是我们所要考虑的自由变量。

【注:在这里,我们只能替换那些所谓的“自由变量”。粗略地说,自由变量是那些之前没有被抽象过的变量。详细的技术细节略显繁复,而且也有办法绕过,所以于此略过。】

从这三点基本要求出发,丘奇开始定义他的λ演算。他将他考虑的这些函数称为“λ项”,而所有的λ项都可以从以下三种途径构造而成:

1. (变量)所有变量x, y, z, \ldots都是λ项。
2. (应用)如果MN都是λ项,那么(M \, N)也是λ项。
3. (抽象)如果M是一个λ项而x是一个变元,那么\lambda x. M也是一个λ项。

接下来,丘奇定义了一些λ项之间的转换法则。

首先是\alpha重命名,这项转换可以使我们在遵循一定的规则下,任意变换λ项中的变量名称,而不改变λ项本身的意义。也就是说,λ项中变量的名称无关紧要,无论是x, y, z还是苹果、香蕉、榴莲,又或者是小庄、游游、李清晨,项的本质是不变的。

然后是最重要的$\beta$规约:

(\lambda x.M) \, f \, \rightarrow^{\beta} \, M[x \leftarrow f]

在这里,M[x \leftarrow f]实际上是$M(f)$的严谨记法,表明了我们要替换的变量。而$\beta$规约实际上就是根据定义计算函数的一个过程。

最后,还有一个\eta变换。它的实质是所谓的外延性,也就是说,如果两个项对所有函数的作用都是相同的话,那么就认为这两个项是相同的。

这么几条简单的法则,就是丘奇的λ演算的全部内容。

那么简单的法则,很难想象λ演算能表达什么复杂的数学概念,这看起来不过是符号的简单推演而已。但既然同样简单的图灵机中也暗藏玄机,那说不定λ演算也有它自己的复杂内涵。

y-combinator_2

分崩离析的世界

丘奇最初建立λ演算的目的,是希望将它作为一种逻辑推理的方法。我们可以将某些逻辑公理表达为λ项;对于某个逻辑命题,我们可以先将其转化为λ项,再根据λ演算的法则将它不断简化,而命题正确与否就蕴含在计算结果之中。

通过这种方法,丘奇成功地在λ演算的框架下表达了不少的数学系统。λ演算看起来是如此的成功,甚至达到了无所不能的程度。

但如果我们还记得哥德尔的教训的话,无所不能有时并不一定是什么好事,因为在数学和逻辑的领域中,对于有意义的逻辑系统,强大的表达能力必然伴随着坚不可摧的限制。如果一个系统无所不能,那么更大的可能是它本身就自相矛盾。就像一个理论,如果对的也好错的也罢,正面反面都能解释得通,那相当于完全没有解释。

果然,几乎在丘奇向学术界展示他的λ演算的同时,Kleene和Curry就证明了,作为一个逻辑推理系统,λ演算在本质上就存在着矛盾,它是不一致的。通过适当地构造一些λ项,Kleene和Rosser成功地利用λ演算找到了一切命题的证明,甚至包括那些错误的命题!一个连错误的命题都能证明的逻辑系统,也就是说一个不一致的逻辑系统,没有任何意义。

值得一提的是,上面这几位后来都成为了数理逻辑界的大人物。Kleene和Rosser是丘奇的学生,而Curry则师从希尔伯特。我们后面还会讲到这位Curry教授,他的事迹之一就是有整整三个不同的编程语言是以他的名字命名的,连中间名都用上了,影响力可见一斑。

事实上,丘奇当初在筑建λ演算之时,就已模糊地认识到了这个问题,但他觉得这只是一种幻象,通过某些适当的限制,就能摆脱这些恼人的问题。但丘奇错了,实际上这是一个本质性的问题。

那么,问题的根源在何处?

我想,读过本系列之前文章的读者应该都猜到了,又是那绕不过去的自我指涉!

但是,自我指涉在什么地方呢?

还记得λ项是什么东西呢?它的原型是函数,但不是一般的函数。在定义λ项之时,我们允许它将任意的λ项转化为另一个λ项。既然是任意的λ项,那么当然也包括它自己。如果将λ项看成程序的话,那又是一个可以将自己当作输入数据的程序。与图灵机不同的是,在λ演算之中,根本没有数据和程序之分,一切都是λ项,它们既是程序,也是数据。

λ演算的能力不止于此。考虑所谓的Y组合子:

Y \, = \, \lambda x. (\lambda y. x \, (y \, y)) \, (\lambda y. x \, (y \, y))

将它应用到任意一个函数$f$时,我们会得到:

Y \, f \, = \, (\lambda x. (\lambda y. x \, (y \, y)) \, (\lambda y. x \, (y \, y))) \, f
\rightarrow^{\beta} \, (\lambda y. f \, (y \, y)) \, (\lambda y. f \, (y \, y))
\rightarrow^{\beta} \, f \, ((\lambda y. f \, (y \, y)) \, (\lambda y. f \, (y \, y)))
= f \, (Y \, f)

这样不停替换下去,得到的结果就相当于将函数f应用到自身任意多次。λ演算的能力,特别是在自我指涉方面,于此可见一斑。

正是如此强大的表达能力,使得作为逻辑系统的λ演算一无所能。如果还记得图灵机是怎么在[link=turing2]停机问题[/link]上失效的话,实际上利用相似的技巧,对于任意的命题,我们可以构造一个λ演算中的证明,无论命题本身是对是错。

后来Curry的工作在更深刻的意义上揭示了这一点。他概括了λ演算的某些特性,然后证明了对于无论什么逻辑系统,只要它拥有这些特性,那么它必然是不一致的。而这些特性,也恰好是会碍事的那部分自我指涉所需要的。

于是,作为一个逻辑模型,λ演算一败涂地。

但丘奇没有就此止步。虽然λ演算不能如他所愿成为数学的推理基础,作为一个计算模型似乎倒也不错。我们可以将一个计算过程看成函数,将输入数据转化为输出数据的函数。于是丘奇将“可有效计算”定义为“可以用λ演算表达的函数”。这时,自我指涉的特性就成为了不可多得的优点,因为这实际上说明λ演算有强大的计算能力。利用自我指涉的特性,通过相似的构造方法,丘奇同样解决了希尔伯特的可判定性问题,得到了与图灵相同的结论。

丘奇在构想λ演算之时,瞄准的是更为基本的数学基础模型,但它却成为了可计算性的模型,真可谓“无心插柳柳成荫”。这就是图灵看到的那篇论文的由来。

不难想象图灵当时读到这篇论文时的心情。如果将数学比作攀山,当你千辛万苦登上一座处女峰,却蓦然发现山顶已经插上了别人的旗帜,你大概会觉得一切都似乎失去了意义。

但数学毕竟不是攀山,不同的路径可能有不同的景致,要论高下为时尚早。况且要比较两者,要先知道两者解决的到底是不是同一个问题。虽然图灵和丘奇解决的都是同一个问题,但他们对“可计算性”各自做了不同的假定。图灵认为“可计算的问题”就是图灵机可以解决的问题,而丘奇则认为那应该是λ演算可以解决的问题。

问题是,图灵机和λ演算这两个计算模型,它们解决问题的能力一样吗?两种视点下的可计算性,到底是殊途同归,还是貌合神离?

2013/02/24

混沌,又一次数学之旅

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/78893

大家还记得几年前的数学电影《维度》(Dimension)吗?前不久,《维度》的原班人马推出了新作:《混沌》(Chaos)。里昂高师的 Jos Leys, Étienne Ghys和Aurélien Alvarez,又一次为我们带来了一场精彩的数学之旅。

上下求索

洪水、地震、旱灾、疫病,远古先民遇到这些灾难时,只有束手无策,而这些灾难来得又是如此突然。于是,预测未来的冲动就深深地植根于人类内在的渴望。卜筮、占星、巫祝,这都是先民掌握自己命运的天真尝试。

但天真的尝试有时是理性分析的开始。从占星脱胎而来的天文学,在17世纪初,第谷和开普勒的努力,向人们揭示了天体运动的某些规律。原来一度象征着天意那些不可捉摸的星辰,在天文学家的努力下,渐渐褪下神秘的面纱。

newton

牛顿则将对自然的探索推上了新的台阶。原本人们以为,处于众神居所的天体,必定不受凡尘俗世规则的束缚。但牛顿力学与万有引力理论却说明,天体和苹果都遵守着同一套物理规则,万物平等。有了牛顿力学,再加上他和莱布尼兹发明的微积分,人类似乎拥有了梦寐以求的预言未来的能力。自此,人们对科学愈加重视,冀望有朝一日摸清自然的规律,从而预知甚至改变未来。

为了达到这个目的,数学家发展了一整套数学工具。他们将微积分拓展到多维空间,甚至一般的流形,用以描述更加多变的模型。计算工具也从原来的常微分方程拓展到偏微分方程,而计算的不仅是数字,还有向量。时至今天,在这些模型的基础上,人们对自然规律的数学探索已经演化为数学的重要分支之一:动力系统。

无处可寻

但知道规律并不代表能预见将来。

举个例子,桌球的物理规律并不复杂,牛顿力学足以解释。但要从桌球开局的一击推断球的最后分布,却是难上加难。

billard

这里边有两重原因。

第一,虽然理论上,如果知道击球的准确力度,就能精确计算出之后每个时刻每个球的位置和速度,但桌上的球数目众多,之间所有可能的碰撞实在难以预计。所以,虽然理论上的计算是可行的,但实际操作中却是困难的。这就是多个客体相互影响所带来的复杂性。

第二,从日常经验中,我们知道即使击球的力度稍有改变,或者球的摆放稍有差异,甚至是桌布上的一点点灰尘导致的偏离,也会给击球的结果造成非常大的影响。换句话说,桌球这个动力系统对于微小的扰动是敏感的。

微小的扰动可能给系统带来巨大的影响,这种敏感性的学名,就叫混沌。用“差以毫厘,谬以千里”来描述这种现象,恐怕是再合适不过了。

restricted-3-body

最简单而引人注目的混沌,莫过于三体运动。仅仅三颗星体的运动,就能变得复杂而眩目。这种复杂曾令数学家们在百年间困惑不已。如果只有两个天体,那么一切是多么简单,18世纪的伯努利就已解出了运动的所有可能轨迹,用合适的坐标,就能用简单的曲线描述。但仅仅是多了一个天体,就要等到19世纪的庞加莱,才给出了差强人意的答案:没有漂亮的解(正式术语是三体系统是不可积的)。这并非因为人类的智慧所限,而是从本质上来说,三个天体之间的运动轨迹不可能用简单的式子表达。自然并不像原来期盼的那么简单,它的复杂性令人绝望。大刘《三体》中的三体人,大概最明白这一点。

3-body-periodic

但正是这种复杂性孕育了无数可能。并非所有三体系统都不可理解,通过合适的构造,我们可以得到一些会沿着既定曲线运转的系统。通过合适地安排速度和位置,我们也可以使其中一颗星体按照任意给定的顺序探访其余两颗星体。但这些系统是如此脆弱,一点点扰动就会打破微妙的平衡,后果可能是其中一颗星体被抛射出去,从此分道扬镳。实际上,我们连我们所在的太阳系的稳定性都不清楚,不知道数百万年后,木星和土星的巨大质量会不会将其它行星,包括地球,抛射到广袤的恒星间空间中。这种事情曾经发生过,而由于混沌,我们不可能完全确定这不会再度发生。混沌,似乎代表了无尽的不确定性,以及所带来的恐惧,就像我们的先祖曾感受过的那样。

celestial-system-collision

失而复得

但也许并非一切都不可掌握。

climate

三体系统只是一种特殊的动力系统。除此之外,在生活中能遇见的动力系统还有很多,比如说天气。天有不测之风云,天气系统涉及整个地球上所有洋流和大气、速度和温度,比起天体的运转更要复杂得多。时至今天,天气预报仍然是个大难题。

对于这种复杂的难题,科学家的第一个想法总是先将它简化。由易到难,由浅入深,这是科学家的一贯作风。“一切应该尽量简单,但不能过分简单”,这是爱因斯坦的话。

如此看来,气候学家洛伦茨在1963年论文中提出的天气模型,恐怕属于“过分简单”的范畴。天气系统如此复杂,用数百万个变量来描述都不为过,但洛仑兹将其压缩到了三个变量:x,y和z。这只是一个玩具模型。

Lorentz-attractor

但实际上,这个玩具模型对于他的论点来说,也许恰到好处。以前的天气模型大多是线性的,没有过多考虑各种因素之间的复杂关系,洛伦茨早已对此有所不满,认为这样简单的模型无法描述多变的天气。而他的玩具模型,尽管只有三个随着时间变化的变量,但变量之间却有着非线性的联系,很好地诠释了因素之间的相互影响。

就在这样简单的玩具模型之下,竟然也出现了混沌现象。而且这种现象似乎是普遍的,因为在三个变量取值的大部分可能性下,系统演变的轨迹都会渐渐趋近于同一个产生混沌的区域,就像磁铁吸引着图钉,混沌的行为成为了必然。这就是人们发现的第一个混沌吸引子:洛伦茨吸引子。它的形状,就像一只蝴蝶。这大概也是洛伦茨将这种混沌的现象称为“蝴蝶效应”的原因。一只南美洲蝴蝶的扑翼,在蝴蝶效应的放大下,也许可以引起得克萨斯州的一场飓风。天气不可能准确预测,因为天气是混沌的,微小的扰动在长远看来是不可忽略的,而我们又无力去追踪无数的扰动,只能一边预计,一边修正。

existence-of-measure

但也许并非一切都不可掌握。除了蝴蝶效应以外,洛伦茨吸引子还有另一种特性。对于几乎任意一种初始状态,也许我们不能描述系统的具体运行轨迹,但当时间趋向于无穷时,我们可以知道系统每个变量处在不同区间的可能性。我们不知道变量具体的值,但是知道变量的值处于某个范围的概率,而这个概率不依赖于初始状态。用行话来说,洛伦茨吸引子具有某种测度。即使我们不能精确预言系统的未来,但我们仍有希望知道某种未来发生的概率。

遗憾的是,并非所有动力系统都有这个特性,尽管这种特性可能相当普遍,可能对于绝大部分的动力系统,包括天气、星系甚至社会,都有着不依赖初始状态的概率测度。但我们的认识仍然太浅薄,难以给出哪怕是模糊的答案。探索,才刚刚开始。

non-existence-of-measure

最后,我们以影片中引用法国博物学家布丰的话作结。对于混沌,也许这是再适合不过的描写。

“一切相互影响,因为时间,一切将会相遇。而在自由延伸的空间,以及无限延续的运动中,所有物质缠绕着,幻作所有形状,映出所有轮廓。一切且近且远,且聚且散,且合且离,且生且死。而这全因那些或吸引或排斥的力,只有它们是永恒的。它们不知疲倦地摇摆着,使宇宙焕出活力,成为一座舞台,用不断重生的实物演着常新的戏码。”

chaos-copyright

影片在线观看地址

Youtube(英语,有中文字幕): http://www.chaos-math.org/en/film

Youku(中文字幕):

http://v.youku.com/v_show/id_XNTAwNzg1MzI4.html

http://v.youku.com/v_show/id_XNTAwNzg3NDIw.html

http://v.youku.com/v_show/id_XNTAwNzk0NjQ0.html

http://v.youku.com/v_show/id_XNTAwOTMyMjUy.html

http://v.youku.com/v_show/id_XNTAwOTQ5MTIw.html

http://v.youku.com/v_show/id_XNTAxMDMyNjQ4.html

http://v.youku.com/v_show/id_XNTAxMDQ5Nzg0.html

http://v.youku.com/v_show/id_XNTAxMDYxOTUy.html

http://v.youku.com/v_show/id_XNTAxMDgwMjE2.html

关于版权信息

所有图片均为影片截图,蒙电影制作方惠允使用,其版权归电影制作方所有。

2012/12/24

计算的极限(二):自我指涉与不可判定

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/75957

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题

矛盾的自我指涉

在现实中,证明某种东西不存在是非常困难的。要证明某种东西存在,只要举出一个例子就可以了;但要证明某种东西不存在,就要想办法排除所有的可能性,而在现实生活中,这几乎是不可能的。所以,只要能排除那些比较主要的可能性,任务就算完成。但在数学中,情况大不相同:通过形式逻辑的方法,我们可以确实地证明某种数学对象不存在。这都要归功于数学那彻底的抽象化和形式化。

数学家在证明某个数学对象不存在的时候,经常会来一招“欲擒故纵”:首先假设它存在,那么它必然具有某些特定的性质,再利用这些性质,用严密的逻辑推理引出一个不可能的结论。既然结论是不可能的,而逻辑推理又没有问题,那么一定是推理的出发点出了差错:作为推理基础的那个东西,其实并不存在。这种证明方法,就是反证法。

现在,我们尝试用反证法证明停机问题是不可计算的。

按照反证法的格式,我们先反其道而行之,假设停机问题是可以计算的。根据定义,这说明存在一台图灵机P,使得向它输入某个图灵机M的状态转移表编码<M>,以及初始输入I,图灵机P就能在有限步运算内,判断出机器M在输入I上是否会停止。

接下来,我们将要用图灵机P构造一个逻辑上不可能存在的结构,这将是证明的关键。

我们来考虑一个新的图灵机R,它的输入是某个图灵机M的状态转移表编码<M>。图灵机R先“调用”图灵机P,判断图灵机M在初始输入<M>上是否会停止。用现代的计算机语言来说,就相当于调用函数P(<M>,<M>)。如果图灵机P得出的结论是机器M在输入<M>上会停止的话,图灵机R接下来就会进入死循环;否则,如果机器M在输入<M>上不会停机的话,图灵机R就停止。

flowchart

图灵机R的构造有两个奇怪之处。

首先,在图灵机R的运作中,它尝试判断一台图灵机M在它自身的编码<M>上的运作情况。此时,图灵机M不仅是程序,同时也是数据。这提醒我们,其实程序和数据没有实质的区别。程序只是一种特殊的数据,能够被分析、整理、改写。

事实上,我们每天都在使用处理程序的程序。比如说杀毒软件,其实就是一种扫描程序的程序。它检查每个程序的内容,判断程序中有没有威胁计算机安全的恶意代码。用杀毒软件扫描它自身,实际上就是让这个程序运作在它自身的代码之上。我们也可以用记事本打开记事本的程序本身,或者用压缩软件打一个包含它程序本身的压缩包。这些例子都说明了一个道理:程序就是一种数据。正因为程序就是数据,我们才得以完成图灵机的自我指涉。

其次,在图灵机R的构造中,如果M在<M>上停机,那么R就不停机;如果M在<M>上不停机,那么R就停机。这就是说谎者悖论的翻版:它的行为要与自己的判断相悖。

这样,我们就凑齐了说谎者悖论的两个要素:自我指涉和自我否定。剩下的,就是如何将这两个要素组合在一起,引出不可调和的矛盾了。

为了引出矛盾,我们来考虑图灵机R在自己的编码<R>上的运行情况。

如果R在<R>上停机的话,R必定没有进入死循环。所以,在调用图灵机P时,得到的必然是“图灵机R在输入<R>上不会停机”,才能避免死循环。但图灵机P的这个结论不符合我们的假设,出现了逻辑矛盾,所以R不可能在<R>上停机。

如果R在<R>上不停机的话,因为图灵机P必定在有限时间内完成计算,所以R必定进入了死循环。而R进入死循环的先决条件是,在调用图灵机P时,得到的是“图灵机R在输入<R>上停机”。而图灵机P的这个结论,同样不符合我们的假设。由于同样的逻辑矛盾,R同样不可能在<R>上不停机。

所以,根据严密的逻辑,我们构造的图灵机R在自己的编码<R>上,既不可能停机又不可能不停机,这是不可能的。另一方面,我们的逻辑推理也是没有问题的。尽管多么不情愿,剩下的可能性只有一种:我们假设的那个能完美解决停机问题的图灵机P,根本不存在!也就是说,停机问题是不可计算的。

这个结论,我们称之为停机定理。以上的论述,作为停机定理的证明远远不算严谨,还有很多细枝末节需要填充。但这些细节都是技术性的,并不妨碍主要的思想:矛盾的自我指涉。

停机定理的证明,一如哥德尔不完备性定理的证明,核心是化了妆的说谎者悖论。图灵机的能力如此强大,一台通用图灵机就可以完成一切图灵机的工作,将所有图灵机作为数据处理。也正因如此,图灵机不能解决某些牵涉它自身的问题,否则总会存在一些自我否定的“说谎者”,利用能解决牵涉自身问题的那些图灵机,完成被逻辑所禁止的,致命的自我指涉。图灵机的能力,在必然的逻辑推演下,同时也成了它的枷锁。

不可判定的重复

实际上,图灵一开始并没有证明停机定理。他证明的是:不存在这样的程序,能判断任意图灵机是否会至少打印出一个1。这里的“1”可以换成任意的符号。这个证明的方法要稍复杂些,不过本质上仍然是通过自我否定与自我指涉来制造悖论。而事实上,许多(但不是所有)有关图灵机的问题,都能用同样的方法被证明是不可计算的。这样,图灵手上就有了一套不可计算的问题,可以开始考虑希尔伯特的问题了。

我们回顾一下希尔伯特的问题。哥德尔证明了,所谓的“一阶谓词演算”是完备的。也就是说,在这个数学系统中,每个真理都能被证明,“真”和“能被证明”这两个概念是一致的。希尔伯特的可判定性问题是:是否存在一种计算过程,可以在有限步运算内,判断在这个完备的数学系统中每个命题的真假?

一阶谓词演算作为数学系统,在能力上实在是比不上数学家们常用的逻辑系统:它连自然数都不能很好地定义。但图灵发现,这个稍弱的数学系统已经足以表达图灵机的运行过程。对于每个图灵机M,通过巧妙然而机械化的操作,图灵都能构造出一阶谓词演算中的一个命题U(M),使得U(M)成立当且仅当图灵机M会至少打印出一个1!也就是说,命题U(M)是否为真与图灵机M的运行过程息息相关。

剩下的证明就如同探囊取物了。如果希尔伯特的可判定性问题是可以计算的话,必定存在一台图灵机H,可以在有限时间内,判断每个命题的真假。对于一台图灵机M,我们要知道它是否会至少打印出一个1,可以先机械化地计算出与M有关的命题U(M),然后用图灵机H去判断U(M)的真假,从而判断图灵机M是否会至少打印出一个1。也就是说,利用图灵机H,我们可以用计算回答一个不可计算的问题,而这是不可能的。所以,图灵机H并不存在,希尔伯特的可判定性问题的答案只有三个字:不可能。

希尔伯特的期望,又一次化为泡影。逻辑弄人。

图灵确信自己解决了希尔伯特的判定问题后,很快将他的想法写成了论文,它的题目是:

论可计算数,及其在可判定性问题上的应用》(On Computable Numbers, With an Application to the Entscheidungsproblem)

他将论文交给了数理逻辑课的纽曼教授。这篇论文在纽曼教授的桌上放了几个星期。当教授终于有时间细读图灵的论文时,一开始根本不敢相信希尔伯特的问题竟然能通过对如此简单的机器的论证而解决,但无懈可击的逻辑论证最终战胜了怀疑。这无疑是划时代的工作,最终埋葬了希尔伯特的宏伟计划。

但正当纽曼教授联系各方,想办法发表图灵的论文时,从大西洋彼岸的普林斯顿,寄来了一篇论文:

初等数论中的一个不可解问题》(An unsolvable problem of elementary number theory)

它的作者是丘奇(Alonzo Church),普林斯顿大学的一位年轻数学教授,当时在数理逻辑这一领域已经小有名气。而这篇文章的最后一句话是:

In particular, if the system of Principia Mathematica be ω-consistent, its Entscheidungsproblem is unsolvable.
(特别地,如果《数学原理》中的系统是ω-一致的话,它的可判定性问题是不可解的。)

对于图灵来说,这绝对不是一个好消息,因为这与他的结果是一样的。

那么,丘奇又是如何得到这个结论的呢?

2012/12/04

Every tree with at most 39 vertices is graceful

Using a new algorithm (described once in a mail to J. A. Gallian), recently I have completed a verification of the graceful tree conjecture for trees with at most n=39 vertices, advancing the recent verification record for n up to 35.

The computation of n=36,37 is done on a T7200. For n=38, it was done with the Amazon EC2 cloud computing service. For n=39, the computation was done on a T7200 then on an i7-3720QM.

Due to heterogeneous computing environment, exact timing is difficult to obtain. A rough estimation is that, the case n=39 took roughly 700 day*core on an i7-3720QM.

An article summarizing my recent verification efforts on graceful tree conjecture and harmonious tree conjecture (in process on yoyo@home) is being prepared.

It would be difficult (at least for me with limited computation resource) to further advance the verification on graceful tree, since the number of trees to verify explodes exponentially. New theorectical results are needed to provide sufficient optimization for further verification to be feasible.

2012/11/21

计算的极限(一):所有机器的机器,与无法计算的问题

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/75175

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限(零):逻辑与图灵机

所有机器的机器

图灵机非常简单,只要明白了它的运作过程,任何一个受过足够训练的计算机系本科生都可以写出一个模拟图灵机运行的程序。只消输入状态转移表和纸带的输入内容,程序就可以一步一步模拟相应的图灵机在纸带上爬来爬去的过程。对于一些熟悉图形编程的程序员来说,做个模拟动画也问题不大。即使不用计算机,靠人手一步步操作,也是一件小孩子也能完成的事。图灵机就是这么简单的一种机器。

虽然看上去简单,但实际上图灵机能做的事情远远超出一般的想象。只要有足够长的纸带和足够好的耐心,今天的电脑能做的计算,一台精心设计的图灵机也能完成。诀窍在于,电脑中的电路是有限的,电路的状态也是有限的,我们可以用图灵机去模拟电脑中的电路状态。只要有足够长的纸带,那就可以模拟出足够大的寄存器、内存和硬盘;而CPU中的电路,虽然所有可能的状态极其多,但终究是有限的,可以用图灵机模拟,虽然这台图灵机的状态转移表将会有着令人头痛的大小,以及令人偏头痛的复杂程度。但是,从原则上来说,用图灵机模拟一台电脑是完全可能的,虽然每次“读写内存”时,读写头都需要花长得令人咋舌的时间在纸带上来回奔波。

也就是说,从原则上来说,只要配备适当的输入和输出设备,以及极其好的耐心,我们完全可以用图灵机上网、玩游戏甚至执行自己写的程序。特别地,存在一台特定的编写程序专用的图灵机T,我们可以在纸带上写程序,将它输入到T,然后T就能执行这个程序。那么,如果我们将方才本科生写的那个可以模拟任意图灵机运行的程序(暂且把它称为程序P),写在纸带上输入到T中,让T去执行的话,原本的机器T就摇身一变,变成了一台可以根据输入的状态转移表来模拟任何一台图灵机的图灵机。

更精确地说,因为程序P的长度是有限的,我们可以将它直接写进原来机器的状态转移表,得到一台新的机器UTM。UTM会在纸带上读取两样东西:一台图灵机M的状态转移表的二进制编码,以及作为M的初始输入的纸带数据。然后,UTM会根据M的状态转移表和初始输入数据,在纸带上模拟M的运作过程。换言之,UTM是一台可以模拟任何图灵机的图灵机。它是所有机器的机器,所谓的通用图灵机(Universal Turing Machine)。当然,通用图灵机并不是唯一的,只要一台图灵机能完成根据状态转移表模拟任意图灵机的任务,它就是通用图灵机。

通用图灵机的一个例子
一台通用图灵机,数据具体格式请参见来源:http://rendell-attic.org/gol/utm/utmprog.htm

通用图灵机的想法,在如今这个计算机泛滥的时代,似乎并不新鲜。但在图灵的1935年,电子计算机甚至仍未问世,机械计算机还只能执行内设的一套指令。即使是Charles Babbage和Ada Lovelace的超越时代的设想,其中执行外部程序的概念也相当含混不清。在这种历史背景下,要归纳出通用图灵机这个概念,本身就需要极为丰富的想象力,而且这种图灵机是否存在,这是个远非显然的问题。而图灵不仅设想到了这个概念,而且正确地判断出它的存在性,这需要何等非凡的直觉!

但单纯的直觉终究不能令人信服,数学家讲究的是逻辑和证明。而要证明通用图灵机的存在,最直接的方法莫过于直接给出一个通用图灵机的实例。这并不简单,如果读者想尝试一下的话,我建议先尝试构造一个能做二进制加法的图灵机。为了降低难度,可以假设纸带上有第三种符号,表示空白,但即使如此,要构造一个能做加法的图灵机,远比想象中的困难。可想而知,通用图灵机的构造肯定更为复杂繁琐。即使是图灵,他在一开始给出的构造也是有问题的,而这些问题甚至在后来的勘误中也没有成功修正。比构造更麻烦的是证明给出的图灵机的确是一台通用图灵机,在图灵解决希尔伯特可判定性问题的论文中,有关通用图灵机的构造和证明占了相当大的篇幅。这部分非常繁复琐碎,而且其中还有错误,如果细细研读的话,绝对有诱发剧烈偏头痛的危险。

幸运的是,无论细节多么复杂,图灵的想法还是被逻辑学家们接受了。一旦领会到图灵机的能力,接受了通用图灵机的构想,再检查几个能完成基本任务的图灵机之后,大部分数学家都会认为通用图灵机的确存在,尽管他们并不一定会细看图灵的详细构造。而现代电子计算机的发展,更是验证了通用图灵机的存在:每一台电脑都相当于一台通用图灵机。

通用图灵机的存在,从侧面说明了图灵机这个计算模型的强大之处:图灵机作为一类机器,其中一个特例就可以模拟整个类别中的任意一台机器,宛如能折射大千世界的一滴水珠。但在这种强大的背后,隐隐也暗藏着不安定的因素。哥德尔不完备性定理告诉我们,有时候越强大的数学理论,因为能表达的概念太多,甚至连理论的命题和证明都能表达,反而会导致不能被证明的真命题的存在。如果一个系统足以描述它自己,那魔法般的自指将是不可避免的。图灵机如此强大,它的其中一台就可以模拟所有图灵机,会不会导致不能用计算来回答的问题存在呢?

很不凑巧,答案是会。

无法计算的问题

在哥德尔不完备性定理的证明中,哥德尔构造了一个描述了本身不可证明性的自指命题,通过这个命题完成了他的证明。要想照葫芦画瓢的话,那些关于图灵机本身的问题,将会是很好的候补。

关于图灵机,最简单的问题是什么呢?回想一下图灵机的运作过程,一台图灵机从初始状态开始,根据纸带上的内容,一边不断变换状态,一边更改纸带的内容,如此往复永无休止,除非它遇上了表示停机的那个状态,才能从这机械的计算过程中跳出,获得静息的安乐。一个自然的问题是:一台图灵机什么时候会停机呢?

更严格地说,会不会停机并不是图灵机本身的属性,它跟纸带的初始输入也有关系。对于同一台图灵机,不同的纸带输入也可能导致不同的结果和行为。比如说,我可以设计一台图灵机,它的任务只有一个:一步一步向右移动,寻找输入中的第一个1。如果输入纸带上全是0的话,那么,这台图灵机自然不会停止;但只要纸带上有一个1,那么它就会停止。所以,真正严谨的问题是:给定一台图灵机M以及一个输入I,如果我们将I输入M,然后让M开始运行,这时M是会不停运转下去,还是会在一段时间后停止?我们将这个问题称为停机问题。

初看起来,停机问题并不难。既然我们有通用图灵机这一强大的武器,那么只需要用它一步步模拟M在输入I上的计算过程就可以了。如果模拟过程在一段时间后停止了,我们当然可以得出“M在输入I上会停止”这个结论。问题是,在模拟过程停止之前,我们不可能知道整个计算过程到底是不会停止,它可能会在3分钟后停止,可能要等上十年八载,更有可能永远都不会停止。换句话说,用模拟的方法,我们只能知道某个程序在某个输入上会停止,但永远不能确定那些不停止的状况。所以说,单纯的模拟是不能解决停机问题的。

实际上,停机问题比我们想象中要复杂得多。

举个例子,我们可以编写一个程序GC,它遍历所有大于等于6的偶数,尝试将这样的偶数分成两个素数的和。如果它遇到一个不能被分解为两个素数之和的偶数,它就停机并输出这个偶数;否则,它就一直运行下去。用现代的工具编写GC这样的程序,对于计算机系的学生最多只能算一次大作业;用图灵机实现的话,也不是什么极端困难的事。然而,GC是否会停止可是牵涉到了哥德巴赫猜想。如果哥德巴赫猜想是正确的,每个大于等于6的偶数都能分解为两个素数之和的话,那么GC自然会一直运行下去,不会停机;如果哥德巴赫猜想是错误的话,必定存在一个最小的反例,它不能分解为两个素数之和,而GC在遇到这个反例时就会停机。也就是说,GC是否永远运行下去,等价于哥德巴赫猜想是否成立。如果我们能判定GC是否会停止,那我们就解决了哥德巴赫猜想。

数学中的很多猜想,比如说3x+1猜想、黎曼猜想等,都可以用类似的方法转化为判断一个程序是否会停止的问题。如果存在一个程序,能判断所有可能的图灵机在所有可能的输入上是否会停止的话,那么只要利用这个程序,我们就能证明一大堆重要的数学猜想。我们可以说,停机问题比所有这些猜想更难更复杂,因为这些困难的数学猜想都不过是一般的停机问题的一个特例。如果停机问题可以被完全解决,我们能写出一个程序来判断任意图灵机是否会停机的话,那么相当多的数学家都要丢饭碗了。

停机问题如此复杂,机械的计算看起来没有足够的力量来完全解决它。停机问题似乎是不可计算的。但要想严格证明这个结论,似乎仍要求助于深藏在图灵机之中,那魔法般的自指。

2012/07/20

计算的极限(零)

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权请勿转载(对的,某网站,我就是在说你)。

本文在科学松鼠会发表,地址:http://songshuhui.net/archives/70194

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

 

一切从逻辑开始

1900年的巴黎,在世纪交替之际,希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的“希尔伯特计划”的最后一步。这位数学界的巨人,打算让整个数学体系矗立在一个坚实的地基上,一劳永逸地解决所有关于对数学可靠性的种种疑问。一切都为了回答三个问题:

数学是完备的吗?也就是说,面对那些正确的数学陈述,我们是否总能找出一个证明?数学真理是否总能被证明?

数学是一致的吗?也就是说,数学是否前后一致,不会得出某个数学陈述又对又不对的结论?数学是否没有内部矛盾?

数学是可判定的吗?也就是说,能够找到一种方法,仅仅通过机械化的计算,就能判定某个数学陈述是对是错?数学证明能否机械化?

希尔伯特明确提出这三个问题时,已是28年后的1928年。在这28年间,数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久,仅仅三年后,哥德尔就得到了前两个问题的答案,尽管这个答案不是希尔伯特所希望看到的。

哥德尔的答案分两部分。

第一,任何包含了算术的数学系统都不可能同时拥有完备性和一致性,也就是说,如果一个数学系统包含了算术的话,要么它是自相矛盾的,要么存在一些命题,它们是真的,但我们却无法证明。这说明,希尔伯特的前两个问题不可能同时为真。在这里,“算术”有着精确的含义,就是皮亚诺公理,一组描述了自然数的公理。

第二,任何包含了算术的数学系统,如果它是一致的,那么我们不能在它的内部证明它本身的一致性。这说明,我们没有希望解决第二个问题。

这就是著名的哥德尔不完备性定理,与其说它回答了希尔伯特的前两个问题,不如说它阐述了为什么我们根本不可能解决这两个问题。

哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化,然后给每个符号串赋予一个数字,这个过程被称为哥德尔配数法。借助数学归纳法,我们可以建立针对所有自然数的陈述,而这样的陈述本身对应着一个数字,这个数字也符合陈述本身的要求。换言之,这个陈述陈述了它本身的性质。哥德尔正是通过这样魔法般的自指,完成了他的证明。这个证明之所以重要,是因为它第一次提供了一套完整的数学工具和方法,用于证明有关数学证明的不可能性。这本身就是数学的一次重大胜利,说明数学的力量强大得可以用纯粹逻辑的方法,证明它本身的力量是有界限的。在数学的领地上,有些东西我们不知道,也不可能知道。

希尔伯特的前两个问题已经解决,只剩下最后一个问题。然而,如果一个数学系统不完备的话,它显然不可能是可判定的,因为机械化的计算本身也可以看成一种证明,而在一个不完备的系统中,真理不总能被证明。所以,最后一个问题只对完备的数学系统有意义。

所幸,完备的数学系统是存在的。同样是哥德尔,他证明了所谓“一阶谓词演算”的逻辑系统是完备的,这被称为哥德尔完备性定理。一阶谓词演算是一个比较弱的逻辑系统,在其中我们甚至不能有效唯一地描述算术。比如说,自然数系统符合皮亚诺公理的一阶版本,但它并不是唯一的,还有无数种所谓“非标准模型”同样符合这套一阶系统。在一阶谓词演算中,对于一套公理系统,如果一个命题在所有的模型中都正确,那么必定可以形式地证明这个命题,这就是一阶谓词演算的完备性。在一阶谓词演算中,真理总能被证明。

在这个弱得多的逻辑系统中,我们有了完备性,真的命题必定可以被证明。那么,它是不是可判定的?我们能不能找到一种机械计算的方法,判定其中数学陈述的对错?数学称述的真假,是否可判定的?这个问题,就是希尔伯特的可判定性问题。

复杂的简单机器

在纽曼教授的数理逻辑课上,图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天,他刚刚完成在剑桥国王学院的四年本科学习,以优异的成绩被选为学院研究员,正准备在数学界大显身手,数理逻辑自然而然吸引了他的兴趣。图灵清楚地意识到,解决可判定性问题的关键,在于对“机械计算”的严格定义。考究希尔伯特的原意,这个词大概意味着“依照一定的有限的步骤,无需计算者的灵感就能完成的计算”,这在没有电子计算机的当时,算是相当有想象力又不失准确的定义。

但图灵的想法更为单纯。什么是“机械计算”?机械计算就是一台机器可以完成的计算,这就是图灵的回答。

用机器计算的想法并不新鲜。17世纪的莱布尼兹就曾设想过用机械计算来代替哲学家的思考,而19世纪的Charles Babbage和Ada Lovelace就设计出了功能强大的“分析机”,只可惜Babbage欠缺管理才能,这台超越了时代的机器始终没有完全造好。但图灵需要的机器,跟先驱设想的机器稍有不同。它必须足够简单,简单得显然能造出实物,也可以用一目了然的逻辑公式描述它的行为;它又必须足够复杂,有潜力完成任何机械能完成的计算。图灵要找的,是一种能产生极端复杂行为的简单机器。

这并非易事,但图灵做到了,据说这是他某次长跑过后,在某块草坪上发呆的成果。他设计了一类机器,然后定义“机械计算”为“这类机器可以完成的计算”。他设计的这类机器,正是日后以他名字命名的图灵机。


图灵机的示例。绿点指示处为当前状态,每条规则的4项分别是:当前位置读入的字符、当前位置写入的字符、纸带的移动方向、将要转移到的状态。

图灵机的结构非常简单,它由两部分组成:一个读写头,还有一条两边无限延长的纸带,纸带被划分为小格,每格中只能有0和1两种符号。读写头的限制则稍微宽松一些,虽然每次只能对着纸带上的一个格子,但它本身可以处于不同的状态,虽然状态的数目是有限的。在所有状态中,有一个特殊的“停机”状态,读写头一旦处于停机状态,就会停止运作;但如果读写头一直没有到达停机状态的话,它就会永远运转下去。

整台图灵机的秘密在于读写头的状态转移表,它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则,就是“如果在状态A的读写头对着符号x,那么对当前格子写入符号y,将纸带左移一格/右移一格/保持不动,然后转移到状态B”。状态转移表就是由一系列这样的简单规则组成的。可以说,状态转移表就相当于图灵机的源代码。

实际上,我们平时笔算乘法的思维过程,跟一台图灵机的运转非常相似:在每个时刻,我们只将注意力集中在一个地方,根据已经读到的信息移动笔尖,在纸上写下符号;而指示我们写什么怎么写的,则是早已背好的九九乘法表,以及简单的加法。如果将一个笔算乘法的人看成一台图灵机,纸带就是用于记录的纸张,读写头就是这个人和他手上的笔,读写头的状态就是大脑的精神状态,而状态转移表则是笔算乘法的规则,包括九九表、列式的方法等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来,图灵机虽然看起来简单,但它足以作为机械计算的定义。

既然图灵机如此简单,能不能将它“升级”,赋予更多的硬件和自由度,使它变得更强大呢?比如说,让它拥有多条纸带和对应的读写头,而纸带上也不再限定两种符号,而是三种四种甚至更多种符号?的确,放宽限制之后,在某种程度上,对于相同的任务我们能设计出更快的图灵机,但从本质上来说,“升级”后的图灵机能完成的任务,原来的图灵机也能完成,虽然也许会慢些。也就是说,这种“升级”在可计算性上并没有意义,放宽限制后的机器能计算的,原来的机器也能完成。既然计算能力没有质的变化,无论采取什么样的结构,用多少种符号,都无所谓。

图灵机的一大优点,就是它的简单。只要给出状态转移表,任何一个人都可以模拟一台图灵机的计算。对工程师而言,在现实中用机械建造一台图灵机也并非什么难事。对于程序员来说,写一个模拟图灵机的简单程序更是不在话下。但如此简单的机器,它又能做什么呢?它真的能充当“机械计算”的定义吗?

(未完待续,所有图片均来自Wikipedia)

关注

每发布一篇新博文的同时向您的邮箱发送备份。