计算的极限(七):宛如神谕

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

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

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

计算无处不在。

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

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

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

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


图灵的哑谜

说到底,谕示是什么呢?我们来看看图灵在他的博士论文中的定义:

“假定我们拥有某种解决数论问题的未知方法;比如说某种谕示。我们不深入这个谕示的本质,除了它不可能是一台机器这一点。通过谕示的帮助,我们可以构筑一种新的机器(叫做o-机),它的基本过程之一就是解决某个给定的数论问题。”

在这里,图灵说的“数论问题”,其实是指描述自然数的一类特殊的逻辑命题,用现在的术语来说叫\Pi^0_1 命题。“数论问题”只是图灵取的一个名字,与真正的数论研究关系不大。

图灵的这段文字其实定义了一种新的图灵机,图灵把它叫做“o-机”,而它的现代术语叫“谕示机”。一台谕示机就是一台有点特别的图灵机,仅仅多了一个新功能,就是能“免费”得到某一个特定的判定问题的答复。比如说,一个带有素数判定谕示的谕示机,除了能做普通图灵机能做的一切事情以外,还能瞬间判定纸带上写的某个自然数是否素数,而不需要实际去计算。

那么,是不是谕示机就一定比普通的图灵机强大呢?就像两位学生参加同一场范围不定的不限时开卷考试,他们的能力与掌握的知识相同,一位学生带了一本参考书,而另一位则什么资料都没带,带了书的那位是不是一定比另一位更有优势呢?

test-without-book

test-with-book

这就要看参考书到底是什么了。如果两位学生都懂参考书中的所有内容的话,那么参考书并不会带来什么优势,可能带书的学生会答得快一些,但既然考试不限时,没带书的学生多用点时间也总能答出来。但如果参考书是两位学生都没有见过的内容的话,带了书的学生自然略有优势。如果考试题目中包含了参考书中的一些内容,而两位学生本来都不懂的话,带了书的可以翻书回答,没带书的就只能干瞪眼了。

同样,在我们比较一台谕示机与一般的图灵机的能力时,也要看看谕示回答的具体问题是什么。如果谕示解决的问题本来就是可计算的话,一般的图灵机即使没有谕示,也能多花点时间把答案计算出来,这时谕示机毫无优势;但如果谕示能解决一个不可计算的问题,比如说停机问题的话,谕示机显然能解决同样的问题,而一般的图灵机则无法解决,因为问题本身是不可计算的,这时谕示机的能力显然比没有谕示的图灵机要强。

所以说,谕示机的力量蕴含在它拥有的谕示能回答的问题,而谕示机中谕示的具体问题可以是任意的。我们可以考虑带有停机问题谕示的谕示机,如果这台机器的纸带上写着一台普通图灵机的“代码”以及输入,那么它不需要计算就能可以瞬间知道,这台普通图灵机遇到指示的输入时到底会不会停机。所以,对于谕示机而言,它不受普通图灵机的可计算性的限制,能够“计算”超越机械计算本身极限的问题。当然,这也意味着,对于一个不可计算的问题,我们不可能实际地建造一台谕示机。

也就是说,谕示机这个概念,只是一个单纯的数学概念,仅仅用于数学上的探索,而不可能实实在在地出现在我们面前。图灵当然也意识到这一点,在他的论文中,也确切声明谕示机并不属于机械计算的范畴。也许这就是图灵使用“谕示”这个名字的原因。“谕示”的原文oracle,来自拉丁语中的oraculum,从orare加上物化工具后缀-oculo得到。orare的意思是“祈求”或者“祷告”,而oracle的意思就是“神的宣布”,也就是神谕。图灵是一位无神论者,他相信神是不存在的,所以神谕当然也不存在。用它来命名一台不可能实现的机器,实在是再适合不过了。

Duerer-Prayer, from Wikipedia

Duerer-Prayer, from Wikipedia

那么,在论文中图灵用谕示机证明了什么呢?

图灵考虑的是一类特殊的谕示机,其中的谕示能回答一切“数论问题”,也就是说,这个谕示能判断任意的“数论问题”是否为真。但除此之外,它就是一台普通的图灵机,于是我们也能考虑关于它的停机问题:给定一台这样的谕示机的代码(不包含谕示本身),以及一个输入,这台谕示机在这个输入上会不会停机呢?

对于普通的图灵机而言,停机问题是不可判定的,这早已被证明。而图灵发现,即使将证明中的所有“图灵机”三个字都换成“带有‘数论问题’谕示的谕示机”,其他部分一字不易,证明依然成立!也就是说,就像普通图灵机不能解决关于自身的停机问题,谕示机也不能解决关于自身的停机问题,无论它的谕示有多么强大。

所以,图灵的结论是,存在带有“数论问题”谕示的谕示机也不能解决的问题,但既然这种谕示机能解决所有“数论问题”,所以不能归结为“数论问题”形式的数学问题是存在的。

这个结论,未免大材小用。不需引入谕示机,以图灵的才智,也有办法证明相同的结论。在整篇论文中,谕示机这个概念只出现在第四章,专门用于探讨“数论问题”的局限性,而这一章基本与论文全体独立,即使删去也不影响结论。用不必要的工具,证明了不必要的结论,图灵到底在想什么,其中是否别有深意?为什么要加上这一章?这些问题的答案,只有图灵自己知道。

幸而,仅仅5年后的1944年,就有人破解了谕示机的哑谜。


谕示机的谕示

让我们回到开卷考试的比喻。在日常生活中,范围不定的考试毕竟少见,多数考试的范围都是相对明确的某个科目,比如说高考语文、数学分析、考研英语、公务员考试中的申论等等。我们经常说,某某省的高考数学难度比某某省的要大,或者高等数学比数学分析要简单。那么,当我们说“某门科目的考试比另一门简单”的时候,我们到底在说什么?

我们尝试一下用数学家的思路来解决问题。

首先,我们希望比较不同的科目,给它们排个顺序。我们潜意识认为,每个科目都有它固有的难度。如果科目A比科目B要难,科目B比科目C要难,那么科目A比科目C要难。也就是说,这种顺序是有“传递性”的。于是,从数学的角度来看,我们要考察的是不同的考试之间的所谓“序关系”,也就是说它们之间两两的难度顺序关系。

其次,我们也发现并不是所有的科目都能相互比较。比如说高考理科数学和对外汉语,高三理科生对前者可能驾轻就熟,但对后者大概一筹莫展;而对外汉语专业的大学生可能恰好相反。所以,科目之间的难度不是一个绝对的数字,有些科目之间不能比较。这与日常生活中的“顺序”关系很不相同,比如说日期或者温度,总有个前后高低之分,不会有两个不能比较的日期或者温度。像日期和温度这类总能比较两个元素的序关系,在数学上被称为“全序关系”;像考试科目这类不一定能比较任意两个元素的序关系,则被称为“偏序关系”。这里的“偏”跟“以偏概全”中的意思差不多,指的是“不全面”。

Partial ordering of the sciences, from Wikipedia

Partial ordering of the sciences, from Wikipedia

现在我们知道,我们要寻找的其实是考试科目之间的偏序关系。那么,给定两个考试科目,有什么办法能分辨两者孰难孰易,又或者无法比较呢?

有一些科目之间是很容易比较的,比如说小学数学当然比中学数学要容易,这是因为中学数学包含了小学数学的内容。一名能完成中学数学考试的学生,必定能完成小学数学考试。但有一些科目就不那么好比较了。线性代数和简单电路计算,初看风马牛不相及,一个是数学一个是物理,似乎没法比较。一个会线性代数的学生,如果没学过电路,似乎也没有理由能进行电路的计算。但如果这位学生知道基尔霍夫定理的话,他就能将电路计算的问题转化为线性方程组,从而用线性代数的知识去解决电路计算的问题。从这一点上来看,似乎电路计算要比线性代数容易,因为存在一种机械而固定的方法(电路的基尔霍夫定理),将电路计算的问题转化为线性代数的问题,而线性代数的问题则不一定能表达成电路的形式来求解。

把这种直觉抽象成数学语言的话,如果对于两门科目A和B,存在一种简单的方法P,能将科目A中的任意问题转化为科目B中的问题的话,那么B就不比A更简单,因为如果我们能解决科目B中的问题,那么面对科目A中的一个问题,我们只需要先用P将这个问题转化到我们能解决的科目B中,再用我们的知识去解决转化后的问题,那么就相当于间接解决了科目A中的原问题。如果这种转化是双向的,也就是说如果存在另一种方法能将科目B中的任意问题转化为科目A中的问题,那么我们就说A与B难度相当,否则我们就说B比A难。

solve-diagram

这种将一个领域的问题变换到另一个领域来处理的方法,在数学中被称为化归或者规约(reduction),是数学家们常用的手段。将组合计数问题化归成连续函数的计算与展开,将代数方程的解空间化归成连续流形,不同的化归手法被数学家们源源不断地创造出来,一开始是神来之笔,但经过几代数学家的努力,最后积淀下来的就是一门全新的数学分支。通过规约,数学家能借用不同领域的各种工具来解决千变万化的各种问题。可以说,对于规约这一门手段,数学家们是再熟悉不过了。但将“规约法”本身抽象出来,则需要真正的数学洞见。

也许是因为太熟悉太习以为常,几乎没有人想到,规约法暗含着计算的另一重含义。

回到考试科目的比喻。如果有两门科目A与B,它们非常非常难,没有学生能不靠课本完成考卷里的任何一道题目,但只要有相应的课本,那么要拿到满分也不是特别困难。虽然两门科目都很难,但大家一般也认为B比A要更难一些。幸而这两门考试都是开卷,所以也没有人抱怨。有一天,一位学生急匆匆跑到科目A的考场,打开书包一看,才发现课本拿错了,手上只有科目B的课本。怎么办?

一般来说,开卷考试带错课本基本上就是死路一条。但我们知道科目A比科目B要容易,也就是说,存在一种方法,可以将科目A的问题转化为科目B的问题。那么,既然有科目B的课本,那么如果这位学生同时也知道问题转化的方法,那么先将试卷上的问题转化为科目B的问题,然后参考科目B的教科书解决这些问题,根据对应问题的答案,自然就能完美完成科目A的考试。

而谕示机,实际上就是一名带着课本参加开卷考试的学生。

判定问题即是考试科目,课本即是谕示,而学生本人,则是带有程序的图灵机。而我们比较考试科目相对难度的方法,实际上就是比较判定问题相对难度的方法。

我们知道,一台谕示机其实就是一台图灵机加上一个能解决某个特定判定问题的“谕示”。假设我们有两个特定的判定问题A与B,而我们希望比较两个问题的“难度”。对于判定问题A,我们将记载了A的所有解答的谕示称为谕示A。那么,我们考虑那些带有谕示A的谕示机,它们都能很快解答A的任意实例。如果存在一台这样的谕示机,它总能正确解答判定问题B的话,那么我们就说问题A至少比问题B要难。这跟开卷考试一样,不能奢求每位学生都知道怎么将科目B的问题转化到科目A中,但只要有一名学生知道怎么做,那么这种转化的方法就存在。在这种情况下,我们说问题B能够“图灵规约”到问题A,可以记作( B \leq_T A );如果同时问题A也能图灵规约到问题B的话,我们就说A与B是“图灵等价”的。

通过图灵规约与谕示机,我们可以比较不同的判定问题之间的相对难度。但谕示机本身就是一种计算方法,它从一个已知的问题出发,通过谕示假定这个问题已经被解决,从而探索那些相对于已知问题而言可以计算的问题。带有某个特定谕示的谕示机,它们能进行的计算是相对于某一个特定问题而言的。某个问题能否计算,取决于我们手上的谕示,换句话说,我们手上已有的知识。

作为一个概念,可计算性是相对的,而不是绝对的,这就是谕示机带给我们的谕示,也许也是图灵论文中哑谜的答案。

那么,揭示出这个谕示的,到底是怎么样的人呢?

From Wikipedia

From Wikipedia

计算的极限(六):无穷的彼岸

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

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

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

计算无处不在。

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

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

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

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


从点集开始

为了超越哥德尔不完备性定理,为了获得一个既不自相矛盾又能证明其中一切真理的数学系统,图灵需要从皮亚诺公理开始,一次又一次地添加新的公理,得到越来越大的数学系统。但无论添加多少次,在获得的系统中,一致性与完备性仍然不可两立,即使添加无穷条公理,也无法跨越“有限”所设置的障壁。要达到原本的目的,图灵必须尝试添加更多的公理。但既然已经添加了无限条新公理,新的公理还会起作用吗?又要怎么去描述“无穷之后”的新公理?“无穷之后”又是什么?

无独有偶,在大约五十年前的十九世纪80年代,另一位数学家也碰到了类似的问题,而他的工作正好给图灵提供了描述“无穷之后”的语言。

这位数学家叫格奥尔格·康托尔,集合论之父。

格奥尔格·康托尔,来自Wikipedia

虽然康托尔最大的贡献是为集合论奠基,但他科研生涯的起点与集合论相去甚远。他师从库默尔和魏尔斯特拉斯,博士论文的题目自然也是与数论相关。让他转向集合论研究的关键人物,是爱德华·海涅(Eduard Heine),一位专攻数学分析的数学家。康托尔博士毕业后不久,就在德国的哈雷大学找到了一份教职,而他的新同事中就有海涅。正是海涅鼓励康托尔研究有关三角级数的问题,他对康托尔提出了这样一个问题:什么样的函数拥有唯一的三角级数表达?

三角级数,顾名思义,是由正弦和余弦这些三角函数组成的级数。无论是正弦还是余弦,它们的图像都如同周期性的波纹,而实际上它们也的确描绘了各种各样的简谐振动。在数学上而言,它们是一些特别简单的周期函数,有着特别美妙的特性。但现实往往是复杂的,在工程中,为了实际应用,我们常常逼切地需要计算与工程中出现的函数有关的各种数量和性质。但这些来源于现实的一般函数,几乎不存在任何规律,同样缺乏任何可资利用的特性。于是,如何借助简单而规则的三角函数,来表达复杂而无序的一般函数,这自然同时吸引了数学家、物理学家与工程师。

三角级数正滥觞于此。在1822年,法国数学家傅里叶在他的著作《热的解析理论》中,为了研究热传导的现象,将热量的分布函数分解为三角函数的级数和,并且提出一个构想:所有函数都能表达为三角级数。

当然,事情并没有那么简单。尽管现实中遇到的函数(连续函数)都拥有这样的表达,但对于更为复杂的函数,这却不一定成立。另外一个问题是,对于任意的一个函数,尽管都可以通过傅里叶变换得到对应的三角级数,但谁也不知道会不会有另外一个三角级数也会给出同样的函数。也就是说,虽然通过傅里叶变换,可以知道必定存在一般函数的三角级数表达,但这种表达是否唯一,却并非显然。

康托尔一开始希望解决的,就是这个问题。

凡事总得一步一步来。在1870年,康托尔证明了某个区间上的连续函数必定有唯一的三角级数表达,后来又证明了,即使函数在区间中的有限个点处不连续,也不影响这种表达的唯一性。最后,他在1872年证明了一个非常广泛而复杂的结论:如果函数在区间上大体是连续的,只有在某个点集P上的点不连续,那么如果P满足某个复杂的性质,那么函数就有唯一的三角级数表达。

函数傅立叶展开的前几项,来自Wikipedia

而正是这个“复杂的性质”,向康托尔暗示了无穷之外另有洞天。

对于任意的点集P,我们可以构造另一个点集P’,它包含所有可以用P中的点无限逼近的点。用数学的术语来说,点集P中的某一点p在P’中,当且仅当对于任意小的距离e,都存在P中不同于p但与p距离小于e的点。既然e可以要多小有多小,这也就是说可以用P中的其他点无穷逼近我们所考虑的点p。这样构造出来的点集P’,又叫P的导集。导集P’本身也是点集,所以它同样有自己的导集,记作P”。导集的导集也有自己的导集,如此反复,直至无穷。我们可以将P取n次导集操作后的结果记为P^{(n)}

容易知道,一个点集的导集必定是点集的一个子集。实际上,从不太严谨的观点来看,求导集这一操作可以看作一个将点集中那些“离散”的点,也就是那些与所有其他点“保持某个距离”的孤零零的点(或者叫孤立点),从点集中去掉的操作。在一次又一次求导集的操作中,由于我们不停地去掉孤立点,可能会有新的点因为我们除去了它的所有“邻居”而变为新的孤立点,所以多次求导集并非没有意义。

导集的定义并不直观,它的性质也相当复杂。对于一个只有有限个点的点集来说,它的导集必然是空集;而对于一个区间来说,它的导集就是它本身;由数列0.1, 0.01, 0.001, …组成的点集,它的导集就是仅仅包含0一个点的集合,它的二次导集就是空集。给定一个正整数n,通过一点点思考,再加上一点点数学分析的知识,很容易构造这样的集合,在求它的逐次导集时,前n次得到的都不是空集,最后第n+1次得到的才是空集。有兴趣的读者可以自己尝试构造一下。

pointset1

pointset2

而康托尔的定理中所谓“复杂的性质”,就是上述的性质:如果对于一个点集P,我们对它进行逐次求导集后,在有限次操作后能得到空集,那么即使函数在其上不连续,只要在区间的其它地方都连续,那么它就必然有唯一的三角级数表示。

当然,也有一些集合,无论求多少次的导集,也不会得到空集。但康托尔发现,如果恰当地定义集合的“极限”,那么可以通过有限次求出的导集定义“无限次”的导集,记为P^{(\omega)} 。之所以用ω,大概是因为这是最后一个希腊字母,代表着终结,正适合“无限”这个概念。

那么,这个挂上“终结”标签的无穷次导集,是否的确是导集这个操作的终结呢?按理说,已经进行了无穷次的导集操作,再操作一次也是无限次,同样无限次的操作,应该只会得到相同的结果。但康托尔发现了一些违背我们期望的集合,即使取了无穷次的导集,得到的结果仍然存在着孤立点,可以通过再次取导集除去。这到底意味着什么?

这一定意味着,我们并没有完全理解无穷。但康托尔的观点甚至更加激进:他认为我们连自然数都没有理解透彻!


数量与顺序

回想我们清点物品,比如说桌子上的书,又或者盒子中的巧克力时,我们到底干了些什么?我们指着一个物体,说一声“一”,又指着另一个物品,说一声“二”,再指着又一个物品,说一声“三”。在这里,“一”、“二”、“三”到底代表什么?最自然的解释是,因为我们正在清点,所以这些数字代表的就是我们清点过的物品的数量。另一种同样自然的解释是,这些数字代表我们清点的次序,“一”就是第一个物品,“二”就是第二个,如此类推。

也就是说,我们平时使用的自然数,实际上有数量顺序的双重意义。在清点时,我们指着一个物品说“五”,实际上说了两件事情,一是之前一共清点了五件物品,二是现在指着的物品是第五件。对于任何一个自然数,这两重意义总是同时出现,难以分割,所以我们自然难以察觉到,在喃喃自语清点物品时,我们口中说出的每一个数字,实际上都有着双重的含义,而这两种含义实际上是完全不同的。

而康托尔的洞见之一,就是对于无穷而言,这双重的含义不再重合,也不再同时出现在同一个“数字”上。本来数量与顺序就是两种截然不同的东西,两种含义不同才自然。

同样一堆物品,可以有许多不同的清点顺序。比如说光的三原色,可以是红蓝绿,也可以是蓝红绿,还可以是红绿蓝。对于清点顺序的唯一要求,就是对于任意两个物品,清点的时候总是能分出个先后,而且要求有一个物品是“第一次被清点”的,也就是说是所有物品中最先被清点的。用数学术语说,就是要求物品之间有一个全序关系,并且有一个最小元素。

但从另一个方面来看,一堆物品的数量应该是一个固定的值,一个只依赖于这堆物品本身的值,一个从属于这堆物品的固有属性。即使我们需要通过清点这种方式来得知物品的数量,但这个数量应该独立于清点的方式,无论我们如何清点,这堆物品的数量应该都是相同的。

对于有限个物品来说,如果不考虑物品之间的差异的话,清点的方法只有一种。无论是红蓝绿还是绿红蓝,实际上都是1-2-3这个清点顺序。所以对于有限而言,数量和顺序之间可以一一对应起来,所以我们只需要自然数这一个概念,就能同时描述有限的数量与有限的顺序,每一个自然数也因此具有双重的含义。但对于无限个物品来说,即使是同一堆东西,我们也可以有无穷无尽的清点方法。我们最常接触的有无限个元素的集合,就是所有自然数组成的集合,这个集合就可以有许多种不同的清点方法。

最自然的方法当然是从小数到大:

0, 1, 2, 3, 4, …

也可以先数偶数,再数奇数:

0, 2, 4, 6, …, 1, 3, 5, 7, …

也可以先数质数,再数合数,最后数1:

2, 3, 5, 7, 11, …, 4, 6, 8, 9, 10, …, 1

当然也可以先数比5大的所有数,然后再数剩下的:

6, 7, 8, …, 0, 1, 2, 3, 4, 5

清点的方法无穷无尽,但自然数的个数应该是一个固定的量,独立于这些各不相同的清点方法。康托尔洞察到了这一点,他意识到,对于无穷而言,需要用两个不同的概念,分别描述数量与顺序。为此,他提出了基数与序数两个概念,前者描述集合的数量,后者描述清点的顺序。这两个概念一直沿用至今。给出一个清点的顺序,自然能得到集合中元素的数量,所以一个序数对应着唯一的基数;但对于某个特定的集合,它可以有许多种不同的清点方法,所以一个基数可以对应许许多多不同的序数。对于有限的集合来说,它们的基数对应着唯一的序数,所以可以将二者混为一谈,这正是我们常用的自然数。

在厘清有关无限的观念滞后,关于点集导集的谜题就自然消解了:当我们说“进行了无限次导集操作之后再取导集,也是相当于取了无限次导集时”,实际上我们谈论的是操作的数量;但导集毕竟是一个操作,逐次重复操作的结果有着内在的顺序关系,先有前面的结果,再有后面的结果。导集的结果,实际上对应的是序数,而我们却用基数的观念来思考,当然会导致似是而非的结果。

实际上,许多关于无穷的看似矛盾结论,都可以归根于我们在日常经验中对数量与顺序的混淆。比如说有人会认为偶数比自然数少,是因为自然数除了偶数之外还有奇数,但实际上这种说法隐含了“先数偶数再数奇数”的这一清点顺序,用这种方法偶数会比自然数先清点完,而我们现在知道,对于无限个物品来说,可以有无数种不同的清点方法,清点方法一先一后穷尽,并不必然代表数量一大一小,关于无穷的怪论也就自然消解了。我们在日常生活中接触到的物体都只有有限个,所以将基数和序数混为一谈也没有关系,但对于导集这种可以产生无穷个对象的机制来说,基数与序数,也就是数量与顺序,一定不能混淆。

以此为基础,康托尔意识到了集合的重要性,并以此为基础发展出了朴素集合论,也意识到“无穷”也有无穷个不同的级别,并称之为“超穷”,意即超验(超越日常经验)的无穷。经过第三次数学危机之后,由朴素集合论发展而来的公理集合论已经成为公认的数学基础。对公理集合论的研究,已经成为了数理逻辑的重要研究方向之一。而超穷基数与序数也已经成为数学研究中不可或缺的概念。希尔伯特这位大数学家的评价或许最为恰当:“没有人能将我们驱逐出康托尔创造的这片乐园”。

序数构成的螺旋,来自Wikipedia

但康托尔本人的命运却远不如他的理论那么幸运。他提出的基数与序数,一开始并没有得到理解,也因为涉及到无穷,以及无穷种无穷,而被当时执德国数学界牛耳的数学家克罗内克所排挤与敌视。克罗内克的格言是“上帝创造了自然数,其余一切均是人为”。他连超越数也不承认,康托尔提出的“超越经验的无穷”,也就是拥有无穷个阶别的无穷,对于这位“统治”当年德国数学界的数学家来说自然是“大逆不道”,甚至到了多次在公开场合言语攻击康托尔的程度。再加上康托尔的理论本来就难以为当时的数学家所理解,因此康托尔在当时的数学界过得并不特别好,一直郁郁不得志,这种压力可能也是他患上精神分裂症的诱因之一。康托尔那辗转于疗养所的晚年,也许部分而间接地要归根于他那伟大的洞察。

生命是灰色的,而理论之树常青。


无穷的彼岸

但对于五十年后的数学界来说,基数和序数的概念早已被广泛接受,图灵对此自然也非常熟悉。利用序数的概念,来探寻无穷扩充之后的公理体系,亦是水到渠成之事。窥探无穷的彼岸,不再是一件不可思议又充满矛盾的事,而是确确实实令人信服的数学手段。

对一个公理系统进行扩充,可以看成对公理系统的一种操作,正如取导集可以看成对点集的一种操作。对于无限次操作之后得到的结果,再施加一次操作,也是有意义的。对于操作来说,重要的不是数量,而是操作的顺序,而序数正适合标记这种顺序。

利用序数,我们能表达无穷次扩充后得到的公理体系。就算无穷次扩充之后,我们仍能一次又一次地进行扩充,直到无穷;但仍能继续扩充,直到无穷次无穷,无穷次无穷次无穷,无穷次无穷次无穷次无穷,如此等等,不一而足;但这并不是终点,我们甚至还能继续进行体系的扩充,达到连用“无穷次无穷次……无穷”也需要重复无穷遍的地方……这令人头晕目眩,但序数可以轻易表达这一切,而这只是序数涵盖领域的九牛一毛而已。

于是,我们能一刻不停地扩充原有的体系,得到一个又一个的新体系,这个过程永无止尽,每一个新的体系都比原来的更强大,而每个体系都拥有自己的一个序数,标志着它们在这个超穷的扩充过程中出现的顺序。每一个能表达出来的序数,都对应着一个公理系统。而所有这些公理体系,依由它们对应的序数,组成了一整个层次结构。

图灵将这一系列的公理系统称为序数逻辑,这个原创的体系正是他的博士论文的研究内容,而提出新研究体系的博士论文,可是凤毛麟角。

他希望这个工具能在某种意义上超越哥德尔不完备性定理。虽然任何一个(可有效生成的)公理体系都不可能同时是一致而完备的,但对于一系列的一致的公理体系而言,这种限制并不存在。即使其中每个公理体系都有不可证明的命题,但如果对于任意的命题,都能在序列中找出一个能证明或否定它的一致的公理体系,那么,在作为一个整体的意义上,这一系列的公理体系是完备的。当然,这与哥德尔不完备性定理并不矛盾,因为一系列可有效生成的公理体系,它们合并起来并不一定是可有效生成的,既然定理的前提不适用,那么定理的结论自然也不适用。

那么,在这个层次结构中的一个“证明”,应该是怎么样的呢?

因为命题总是要在某个体系中被证明,所以首先要指定一个体系,相当于指定这个体系对应的序数,剩下的就是直接写出这个命题在对应体系中的证明。当我们要检验一个证明时,首先查看指定的序数,然后查看对应的体系中的公理,知道公理之后就能如同一般的证明一样进行检验了。也就是说,跟一般的证明相比,在层次结构中的证明只是多了“指定证明所在体系的序数”这一步,似乎没什么了不得的。

但魔鬼往往潜藏于细节之中,这一步并不像想象中那么容易。


直觉与技巧

序数是超穷的,比无穷还要无穷,但证明的长度是有限的。所以,我们实际上不能任意指定序数,而只能指定那些我们用有限个符号能够表达的序数。所以,实际上我们指定系统用的不是序数,而是序数的一种表达方式。这种表达方式要满足两个条件:表达式的长度是有限的;如果某个序数能够被表达,那么小于它的所有序数也应该能被表达。当然还有一些技术上的条件,但我们暂时按下不表。

满足这两个条件的序数表达方法很多,图灵选择的是其中最复杂的一种:克林-\mathcal{O} 表达。这种方法用自然数的因子分解来表达序数。虽然这种方法并不能表达所有序数,但在某种意义上,它已经是最强大的表达序数的方法。但与强大能力相随的是这种方法极端的复杂性。实际上,要判断某个自然数是不是一个序数的表达,这是一个高度不可计算的任务,虽然对于特定的自然数,可能可以进行判断,但不存在统一的判断程序。

既然不可计算,那么也无法验证,那么这种证明还有意义吗?

要回答这个问题,我们先回想一下:在做数学证明题的时候,我们到底在做什么?

第一步,一定是审题,弄清楚题目讲的是什么数学内容,是立体几何还是圆锥曲线,又或者是各种函数。不仅是简单的分类,有时一类问题会伪装成另一类问题,比如戴着“圆锥曲线”帽子的数列,或者披着“概率”外衣的组合。搞清楚具体的问题,搞清楚要证明的结论,这才是完整的审题。第二步,才开始正式的证明,在前一步的结果指引下,用对应领域的定理,慢慢探索从条件到结论的路径。而写在答卷上的,就是第二步得出的证明。审题虽然重要,但并不体现在证明中。

数学的可靠性,植根于证明的严谨性。但如何得到一个证明,却难以仅仅依赖严谨的逻辑。比如,命题需要用哪一个数学体系,这就难以用逻辑判断,需要数学家本人的直觉。也就是说,证明某个命题,其实需要两个部分的工作:第一部分来源于直觉,指引着证明的方向;第二部分来源于技巧,将直觉付诸实践。

作为一名数学家,图灵对数学证明中发生的一切当然深有体会。他认为,这种直觉与技巧的关系,与他的序数逻辑当中的证明不谋而合:指定序数的步骤,相当于直觉,告诉我们应该在超穷的层级结构中的哪一个数学体系中寻找证明;具体证明的步骤,相当于技巧,从直觉指定的公理出发,一步一步迈向需要的结论。而序数逻辑甚至将直觉与技巧的关系发挥到了极致:需要用到直觉的,只有开头的一步,但这一步是高度不可计算的,是逻辑不可能完成的任务;而剩下的,则是完全逻辑化的证明,甚至可以用机械完成。也就是说,可以说在序数逻辑的证明中,直觉与技巧的部分完全独立,一览无遗。

图灵认为,这正是他的序数逻辑存在的意义。

但世事往往不如人意。图灵研究的序数逻辑,主要是通过一致性断言扩充而得到的,而这种序数逻辑并没有图灵所期盼的那种完备性。图灵只能证明,他的序数逻辑对于一小类命题(所谓的\Pi_0^0 类)是完备的。这并不尽如人意,但至少第一次跳出了哥德尔不完备性定理的界限。

然而,以后见之明看来,图灵的博士论文中,最大的贡献并不是序数逻辑。在论文第四节中,图灵提出了一个孤立的新概念,这个概念对于论文的其他部分并无深刻贡献,图灵也未曾深入探讨,这使整个第四节看似无关紧要。但在后学看来,这个新概念却是整篇博士论文中最重要的部分,甚至比序数逻辑更重要。可以说,这个概念后来开创了可计算性理论的又一片新天地。

这个概念,叫谕示(oracle)。

(未完待续)

机械证明可不仅仅是枚举——最近Erdos某猜想特殊情况的证明

前段时间有这么一个新闻,说是有人用计算机证明了Erdos的一个猜想的特殊情况。因为忙,最近才看了这个论文,想给大家说说是怎么搞的。

首先,我们来说说这个问题到底是啥。

我认为这个问题可以归到拉姆赛类型的问题中,粗略来说,这类问题说的是即使在非常无序的结构中,当结构的大小达到一定程度时,必然会有高度有序的子结构出现。比如拉姆赛定理,说的就是对于任意给定的整数k和l,将完全图任意染红蓝两色,当完全图本身足够大时,最后要么出现红色的k阶完全子图,要么出现蓝色的l阶完全子图。也就是说,完全的无序是不可能的。

Erdos的这个问题,叫Erdos差异问题,也是同样的类型。我们取一个由+1与-1组成的数列,然后考虑它的一些子数列。如果是完全随机的话,这些子数列的和应该很接近0。但Erdos认为,只要数列足够长,长到无限长,对于任何的常数C,应该可以找到这样的子数列,它们的和的绝对值超过C。

具体的数学定义如下:对于任意由+1和-1组成的数列(a_n)_{n \in \mathbb{N}},考虑它的前N项。其中对于所有d \leq N,考虑子数列a_d, a_{2d}, \ldots, a_{\lfloor N/d \rfloor d}的和的绝对值S((a_n)_{n \in \mathbb{N}}, N, d) = \left| \sum_{k=1}^{\lfloor N/d \rfloor} a_{kd} \right|,然后取所有d中这个绝对值最大的d,将这个最大的绝对值记作MaxS((a_n)_{n \in \mathbb{N}}, N)。Erdos的问题就是,是否对于任意一个常数C与任意一个数列(a_n)_{n \in \mathbb{N}},当N足够大的时候,MaxS((a_n)_{n \in \mathbb{N}}, N)必定会超过C?也就是说,当数列无穷时,是否必定存在一个上述形式的有限子数列,它的和的绝对值超过C?

这样的子数列在某种意义上也可以看成一种需要每个分项配合的“秩序”,虽然可能比较弱,因为随机游走的结果也可以做到这一点。在这种情况下,我们可以认为这个问题的本质差不多也是“不存在完全的无序”。

当然了,这不是唯一的看法。另一种看法是这个问题实际上说明了,不存在某种可以避开所有子数列的结构,不过我觉得这也跟拉姆赛问题有些擦边。

然后之前一段时间有数学家把C=2的情况做掉了,具体论文在这里:http://arxiv.org/abs/1402.2184。也就是说,必定找到想要的子数列,使得和的绝对值大于2。

他们是怎么做的呢?其实很简单,他们用计算机证明了,只要数列长度超过1161,那么就必定能找到和的绝对值大于2的给定形式的子数列。显然这么长的数列,要人工分析是不太可能的,必须扔给电脑,但是怎么扔呢?

在自动推理的学界,有一样神器,叫SAT Solver。

如果你是计算机系的学生,那么你一定听说过SAT,也就是可满足性问题:给定一个由与、或、非连接布尔变量组成的命题,是否存在一个变量的赋值满足这个命题,也就是说使得这个命题为真?这个问题著名,主要是因为它是第一个NP-完全的问题,很多问题都是通过规约到SAT来证明是NP-完全的。也正因如此,很多工业和数学上遇到的问题,都可以规约为SAT问题。在这里,规约的意思是将问题表达为布尔变量组成的命题,其中命题的解与原问题的解相互对应。所以,如果命题可满足,那么原来问题必定有解;如果命题不可满足,原来的问题就没有解。只要解决了对应命题的SAT问题,那么就解决了原来的问题。

正因为很多问题都可以规约为SAT问题,所以与其对每个特定的问题开发解法,可能直接开发一个SAT问题的通用算法更方便。这就是SAT Solver,专门解SAT问题的程序。你只要给它一个公式,它吭哧吭哧一段时间就可能给你一个答案(对于所谓Complete Solver而言),虽然要多少时间是完全不知道的,取决于问题的难度。

SAT Solver的研究其实还算相当热门,几乎每年都会有一项SAT Solver的竞赛,由SAT Competition与SAT Race轮流,前者比较偏学术,后者比较偏应用,不过形式是类似的,就是选择一大堆问题,然后让很多SAT Solver去解,谁用的时间少谁赢。

SAT Solver一般分两大类,一类是基于推理,另一类基于撞大运……后者就是先随便找一个赋值,然后尝试改进这个赋值,使得满足命题的程度越来越大,最后如果运气好,就能撞上一个能满足命题的赋值。问题是,如果命题本身就是不可满足的,那么就永远不可能出解……

基于推理的SAT Solver则更加有趣。它们基本上就是一个叫DPLL的算法的变种,这个算法会把命题分成很多子句,要每个子句都为真,命题才为真,然后用逻辑与组合这些子句然后根据逻辑规则简化这些组合,不断重复,如果在某一步得到“False”,那么这个命题就是不可满足的,因为从应该为真的子句导出了矛盾。有时候这样的重复不足以揭示问题,所以也会给某些变量赋值,如果得到“False”,证明变量不可能取这个值,比如取另一个值。这样重复下去,直到找到一个满足的赋值,或者证明所有的赋值都是矛盾的所以命题不可满足。对于不可满足的命题,有些Solver会给出一个证书,通过某些证书(比如Backbone variable)可以在不重复相同计算的情况下验证这个命题不可满足。

说了这么多,这个与自动推理又有什么关系呢?

这些子句,在DPLL Solver的术语中也叫引理。组合子句,其实就是通过组合引理导出新的引理,而如果得到了“FALSE”的引理,也就意味着原来引理的组合可以推出“FALSE”,也就是说,原来的命题本身就有矛盾。

这实际上就是自动推理的一种。

当然,这个算法是50年前的了,现在的SAT Solver要更加先进得多。首先,它们有很多不同的优化,可以加速算法本身的运行。而更重要的是,它们有非常精巧的推理方法。要知道,推理方法,也就是在每一步选择哪些引理进行组合,得到新的引理,这一点对于效率非常关键。SAT Solver近几年的常青树之一,glucose,核心就是一种叫glue clause的引理选择。另外,引理的组合是无穷的,但内存是有限的,如何判断哪些引理重要,哪些引理可以舍弃,这本身就不容易。如果舍弃了重要的引理,可能就要兜一个大弯才能解决问题。但有些推理方法,对一类问题很有效,对另一类问题可能就要花比较长的时间,这时候就要进行取舍。这里边的学问非常深,而且与实际操作关系很大,因为SAT Solver设计出来就是要解决现实中的问题的。现在,最好的SAT Solver可以解开需要几百MB的数据才能表达的问题,也能解出一些非常难的问题。这对于工业来说很重要,比如说一些电路设计的线路排布,就需要用到SAT Solver。SAT Solver不仅是研究,而且对生产也是大大的有好处,绝对是非常有用。

好了,兜了这么一个大弯,回到Erdos的问题上。那些数学家是怎么证明C=2的情况呢?很简单:他们把长度为1161的数列用布尔变量编码,然后将对应的问题规约到SAT,也就是说翻译成命题,然后喂给SAT Solver,他们用的是Lingeling和glucose。这两个Solver哼哧哼哧了一段时间,不断把引理倒来倒去,最后报告了这个命题是不可满足的。glucose还顺便给出了一个证书,这个证书很大,大概是13GB。然后这个问题就被证明了。

有人可能觉得方法很暴力,但是从我的经验看来,其实这里边技术含量很高。先不说暗藏在SAT Solver里的技术含量,就算是将问题规约到SAT,也不是件容易的事。同一个问题可以有非常多的规约方式,但不是每种规约方式求解需要的时间都是一样的。我曾经尝试解某个问题,用一种方式死活解不开,另一种更精细的方法Solver就秒解了……有很多组合问题,其实即使用SAT Solver解,不找准问题的结构所在,盲目去规约的话,基本上做不出来。说到底,Solver是一个自动推理程序,如果一开始给的路就不对的话,那当然需要时间;如果一开始就根据问题结构把引理切好,那显然解起来容易得多。所以,这些数学家把问题做出来了,本身就说明他们很好地理解了这个问题。

可以预见,未来用SAT Solver解的离散数学问题会越来越多。但要记住,这其实并不是暴力枚举,而是巧妙的自动推理,其中的智慧,只有一群人经过漫长的积累才能做到。

起码在目前来说,计算机的智慧,其实是人的智慧的延伸。

二十五

五年过去了,看了看自己的想法有什么变化。似乎大方向上没什么改变,只需要多加几笔。

————————————————————————————————————————

萨特说得好,存在先于本质。人存在,然后再去找意义。我找到的,跟别人找到的,都是对的,都是错的,但无可依靠,只能一直走下去。我的“华丽悲剧”理论(姑且先这么叫),也跟几个人讲过,不为什么,只是我觉得从无所依靠中寻找依靠,这仍然算是个貌似可行的理论,也希望少数几个朋友能明白,为什么我向来说着悲观的言论,却没有被悲观压垮。

我向来对作为一个整体的人类没有信心。那么,如何在这个由人类构成的社会中生存下去,就成了一个困难的问题。《乌合之众》之中的论述,虽然有失偏颇,但也有一定的道理。我更希望保持我自身的判断力,虽然在这个信息横流的社会这越来越难做到。何况为了生存,我仍然要想办法从社会中获取需要的资源。

这也是我选择数学的原因之一。首要原因当然是因为我喜欢数学,无论是数学本身还是数学自有的美。另一个原因就是,我做的数学起码在我活着的相当一段时期不会带来实质性的用途。“山木自寇也,膏火自煎也。桂可食,故伐之;漆可用,故割之。”没有价值,才能来去自由。但凭借数学我仍然可以得到报酬,这是一种社会的投资,目的是长远的价值。但只要没有即时的价值,那么就是安全的,况且我对所谓“长远的价值”也抱有很大的疑问,甚至希望这种价值不存在。

除此以外,我实在不想跟人类打交道。特别是在习惯看微博之后,更加惊叹于人类的愚蠢。绝大部分的人仍然用古旧的方式来思考,毫无逻辑只讲气势。社会也许还会继续进步吧,但我相信大众的思想是绝难改变的,鲁迅先生写的东西到现在还栩栩如生,这就说明了一切。毕竟社会在进步,总有领先的,而大部分人总是落后的。如何在这种环境下,不违心地生存下去,这是个复杂的问题。“多闻数穷,不若守于中”,也许某种程度和形式的随波逐流是必须的。

但是,必须时时警惕不忘本心。我自有要做的事,目标即自我。

想成为什么样的人,就要成为什么样的人,就成为什么样的人。

————————————————————————————————————————

我只是一个平凡的人。

所以我不相信运气,不相信奇迹。一切都是概率,从不盼望小概率事件。相对地,一切事情,无论概率多小,发生了就是发生了,先处理,再反思,没有后悔咒骂的余地。

我只是一个平凡的人。

所以我不相信自己对这个世界有什么显著的影响,一切目光可见的改变,迟早会被岁月磨光。我没有期盼,但是对于我相信的事情,我仍然会做下去,即使早已知道不会有结果。

我只是一个平凡的人。

所以世界上像我这样的人多得是,多我一个不多,少我一个不少。只是对我身边的人来说,“我”这个个体才有意义,否则最多是一个符号,甚至是统计数字。我也不认为我有什么优越,只是条件不同。

我只是一个平凡的人。

所以也有喜怒哀乐,也曾经历悲欢离合,只是说或不说而已。

我只是一个平凡的人。

————————————————————————————————————————

朋友们,相信我,我并没有把你们忘掉。我的记忆力还不算坏,虽然不记得昨天午饭吃了什么,但比如多年前在北京谁跟我讲过些什么,很多时候我还是记得的。我只不过不习惯主动说出来。这种习惯是好是坏,我也说不好。

这几年做科研也做科普,有时候外出演讲多了,渐渐发现自己的又一个奇怪的地方。在面对一帮陌生人演讲的时候,情绪似乎特别高涨,好像换了一个人似的,连我自己都觉得吃惊。现在想起来,大概是应激反应吧,或者说学习了父亲那种奇怪的激动?在社会上,这种技能当然是有好处的,这也许也是我的自我的一部分。

但一个人的时候,坐在椅子上,听着歌,想到的东西基本都是悲观的,如果不是不带情绪的话。科研环境会如何恶化,社会舆论会如何反智,经济整体会如何低迷,气候变化会如何恶劣,这些都是关乎自身生存的问题,但我总是持有非常悲观的观点。

当然,这种悲观的想法并不会使我变得脆弱,毕竟这是我的美学观点的立足之处。

也许这就是我的生活方式。

————————————————————————————————————————

这几年读了些书。慕名多年,终于读到了戴蒙德的《枪炮、病菌与钢铁》,还有他的《崩溃》。《裸猿》是好久之前读的了,与之相对的还有一本《盛装猿》。我一直觉得,这一类书对于了解“人类”很有帮助,也推荐过给朋友。《思考,快与慢》也想读,但是据说翻译不行,打算直接买本原文。

人类是很复杂的东西,如果不研究一下,就很难理解现在发生的种种现象。这些现象,背后或多或少有着千百万年前环境在先祖身上留下的印记。

人毕竟是种动物,即使它有理性。

在人类的日常决策中,理性常常缺席。现代社会节奏太快,理性越来越缺席,在一秒不到的功夫里就能做到的事情,人们思考得越来越少。人们“凭感觉”“靠经验”,却鲜少用推理与实证的方法来处理问题。当然,在餐厅选甜点,大可以凭感觉。一次半次的话,凭感觉得到的满足不一定比衡量营养均衡后带来的收益高多少。但事情总是积少成多。在意识到的时候用理性决策,先不说带来的收益,以后在重大决策中发昏了头的概率大概也会小一些。

人毕竟有理性,虽然本质上是种动物。

但是正是理性,是我们与众不同。探索千亿年跨度的事物,思考现实中并无对应的抽象概念,这都是人类独有的。只有在最大程度上利用理性,才能彰显出人类的不同。而理性带来的谋划能力,也许能给生命存续带来一线生机。

可惜,理解到这一点的人,太少,太少。

————————————————————————————————————————

我害怕群众。

他们能量太大,但没有阀门;他们行动迅速,但从不细思。事实经过三个人,可能已经走板荒唐,而造谣撒谎更是无数,为名为利当然有,但更多时候只是因为好玩。他们可以迅速关注一件事情,造成强大的舆论压力,但转移注意力甚至更快,许多事情草草收场。他们的关注,无论一开始是好是坏,最后总会带来无尽的伤害。

群众是强大的,但也是盲目的。没有什么东西比这更危险。

我希望避免这种危险。但我无处可逃。只能尽量避免成为目标,尽量不引人注目。

但有时候这是必须的。这时我只能小心翼翼、谨小微慎。

我可以跟一个人做朋友,但面对群众,我宁愿沉默。

而民主,有时更加可怕。

————————————————————————————————————————

世界上还有一种可怕的事情,我将它称为“无人犯错的过失”。一件给人带来极大伤害的事情,它的发生可以完全由善意的人们通过善意的手段与善意的体系达成。没有人应该受到惩罚,但却有着严重的后果。可能是运气,可能是疏忽,可能仅仅是没有考虑过于特殊的情况。如果这种事情发生,人们甚至无所用其力。由于善意,甚至难以反思。

所以我认为意向并不重要,最重要的是结果。人本来就不能了解别人,只能用范畴的眼光看问题,事物的属性由它与其它食物的互动所完全决定。纵然心存善念,坏事就是坏事,没有借口。

回想当年华附经历,许多伤害的来源并无主观恶意。但这也正是这些伤害的可怕之处。因为主观没有恶意,所以也不会有愧疚,也不会停止。

我宁愿不受这种人的关注。同时,我也倾向于在没有清晰预期之前,不去干扰他人。

我不想受伤,更不愿意伤害别人。

————————————————————————————————————————

我做数学科普,因为我觉得数学很美妙,而让更多的人知晓这种美妙,不失为一件快事。写得漂亮,更是愉悦。

但我并不觉得也不希望我做的科普会带来实质的用途。开启民智,这个词语太大,实在承受不起。但只要大家能领会数学的美感和重要性,即使不懂细节,也是一件好事。

有朋友跟我说,我这样做科普影响可能不大,现在的人是要喻于利的,我写的都是喻于义,没有市场。

这也是不算什么坏事,本来就不需要它赚钱。起码目前不需要。

我只是因为我想写,于是就写了。

唯一一点不好的就是,我大概应该更勤奋。

————————————————————————————————————————

关于真理与有用的问题,我在图灵传的书评里已经讲过了。

我坚持真理,只希望能尽量不违背自己的良心。

仅仅是希望,因为我知道这绝无可能,只是迟早与程度的问题。

希望遇到这种情况,我能更成熟地处理。

————————————————————————————————————————

返璞归真。

如果说是生活方式的话,这是不可能的。

人类发展到现在,早已没有回头路。比如说农业,无论看上去多么天然的做法,实际上都是人类用各种方式操控自然的结果。不这样做,不可能获得足够的粮食。现在看似天然的有机农业,其实还是基于我们操控自然的经验,而且对环境的影响还不一定小。

现代化的脚步已经遍及每个角落,很多人之所以反对现代化,留恋往昔的生活,实际上可能仅仅因为他们的思考不能适应现代化的步伐。他们不能理解生命的神秘,思考仍停留在亚里士多德的年代,所以不能理解新兴的生物技术。他们不能理解抽象的力量,所以数学对他们而言一钱不值。但他们从来不会想到,如果缺少科技,他们的生活将会寸步难行。

于是拆变电站,拆信号塔,反这个,反那个,仅仅因为“不理解”与“宁可信其有,不可信其无”。而他们无法理解他们自己的不足之处,所以也绝不可能更改他们的意见。肤浅的取像类比,加上年资与传统,这就是他们的利器。

殊不知现在是现代,是理性的年代。也许只有世代更替,才能改变这样的局面。

但也许世代更替仍然不够。在中国,传统的力量是无穷的。

但精神上的返璞归真,却是一件好事。在现代,人更要直面本心,才不至于迷失。

————————————————————————————————————————

Life is so hard.

fin.

数学突破奖半解析:告诉你真实的数学

本文遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守。

本文在果壳网发表,有删改,地址:http://www.guokr.com/article/438708/

科学是目前人类探知客观世界最好的方式。对于科学的投入,尽管不一定能一蹴而就得到什么切实有用的成果,但长远来看却是技术发展最好的动力源。与技术开发不同,对科学的投入更像是公益活动,因为科学研究得到的成果属于全人类。而数学作为科学的语言,也有着类似的性质。

在目前富豪争相投身公益事业的社会潮流下,我们能听到的科学相关奖项也越来越多。除去老牌的菲尔兹奖、诺贝尔奖以外,我们时不时还能听到一些新的奖项。在前不久的6月23日,又有一个新的奖项横空出世,它名为“数学突破奖”,它的目标是“认可本领域内的重要进展,向最好的数学家授予荣誉,支持他们未来的科研事业,以及向一般公众传达数学激动人心之处”。

这个奖项引人注目之处之一它的奖金来源:Facebook的创始人扎克伯格以及数码天空科技的创始人之一米尔诺。此前他们还设立了“基础物理突破奖”与“生命科学突破奖”,合作者更包括Google创始人之一布林以及阿里巴巴的创始人马云。他们都是互联网造就的新贵,大概也正因如此,他们也更理解科学的重要性,因为正是科学的飞速发展,带来了日新月异的信息技术,也给他们带来了庞大的财富。

另一个引人注目之处则是高昂的奖金:三百万美元,这是诺贝尔奖的2.5倍有余,与解决3个克雷研究所千年难题所能获得的金额相同。这是科学奖项目前最高的奖金,它很好地完成了吸引公众眼球的任务。

那么,这次的获奖者都有哪些呢?他们的贡献又是什么呢?

西蒙·唐纳森(Simon Donaldson),来自石溪大学以及伦敦帝国学院,他因“四维流形革命性的新不变量,以及在丛以及法诺簇两方面,对其中代数几何与全局微分几何中稳定性之间联系的研究”而获奖。

马克西姆·孔采维奇(Maxim Kontsevich),来自法国高等科学研究院,他因“在包括代数几何、形变理论、辛拓扑、同调代数以及动力系统等在数学众多领域中产生深刻影响的工作”而获奖。

雅各布·劳瑞(Jacob Lurie),来自哈佛大学,他因“有关高阶范畴论和导出代数几何方面基础性的工作,对全扩展拓扑量子场论的分类,以及对椭圆上同调的参模理论解释”而获奖。

陶哲轩(Terence Tao),来自加州大学洛杉矶分校,他因“在调和分析、组合学、偏微分方程以及解析数论中的众多突破性贡献”而获奖。

理查德·泰勒(Richard Taylor),来自普林斯顿高等研究院,他因“在自守形式理论方面的多项突破性工作,包括谷山-韦伊猜想、一般线性群上的局部郎兰兹猜想以及佐藤-泰特猜想”而获奖。

看着这些简介,你现在的脑海里一定充满了各种“这些字每一个我都认识但是合起来是啥”又或者“哇好厉害啊好高深啊他们干的到底是啥”之类的念头。不要急,让笔者带大家分析每一位的主要贡献。


理查德·泰勒:代数数论

J-invariant from Wikipedia

我们从最后一位的理查德·泰勒开始。他的名字可能不太为人熟知,但如果说起费马大定理以及安德烈·怀尔斯,每个人可能都略有耳闻。泰勒是怀尔斯的学生。在当年怀尔斯证明费马大定理的故事中有一个小插曲,怀尔斯最初发布的证明其实是不正确的,其中存在一个漏洞。大家一开始看不出来,但随着数学界慢慢审视这项重要的工作,漏洞很快就被发现了。怀尔斯花了一年的时间找到了绕过漏洞的方法,而与他一起完成这项工作的,就是泰勒。

泰勒主要研究的领域是自守形式理论,这是代数数论——用代数结构研究自然数的一门数学分支——的一个重要部分。要理解自守形式,最好先从模形式开始。模形式是一种特殊的复值函数,它定义在复平面的上半部分,满足一定的增长条件,而最重要的是它有着高度的对称性,在一个被称为“模群”的特殊变换群的各种变换下仍然保持不变。这个群中的元素都是所谓的“默比乌斯变换”:

z \mapsto \frac{az+b}{cz+d}, \, a,b,c,d \in \mathbb{Z}, \, ,ad-bc=1

(有关群论与模形式理论的另一个联系,请参见《有限单群:一段百年征程》)

这里的a,b,c,d都是整数,也正因如此,模形式与数论天生就具有密不可分的关系。许多数论中的问题,甚至最耀眼的黎曼猜想,都能在模形式中找到联系,特别是一类被称为“椭圆曲线”的特殊曲线,与之关系更为密切,而这正是泰勒与他的合作者证明的谷山-韦伊猜想(现在又被称为模性定理)的内容。不仅是费马大定理,许多形式类似的方程解是否存在的问题,最终也能归结到有关某类椭圆曲线与模形式之间的关系,经过谷山-韦伊猜想指示的联系,从而得到解决。

除此之外,椭圆曲线除了是代数数论研究的轴心之一,也是计算数论中重要的研究对象,从而在实际生活中的应用占据着一席之地,特别是与每个人密切相关的密码学。与椭圆曲线有关的不对称加密协议,已经成为密码学的重要分支之一。这类加密协议虽然速度较慢,但在相同的密钥长度下,可以提供更可靠的保护。而这些加密协议的有效性以及具体应用,反过来又与椭圆曲线的理论研究息息相关。有许多加密时使用的工具,比如说泰特配对,就来源于理论研究。另外,椭圆曲线本身就能用于整数的因子分解,这也是RSA密码体系的命门。

至于泰勒研究的自守形式,则是模形式的一种推广,而椭圆曲线的对应推广又被称为超椭圆曲线。对于这些“升级版”的研究可以说根·本·停·不·下·来。它们结构之精致、地位之重要、内涵之丰富,再加上应用的潜力,实在使数学家们欲罢不能。


陶哲轩:解析数论、调和分析

对于陶哲轩,我们熟悉得多。他是华裔,也是神童,研究的领域之一——解析数论——也早已经由陈景润与哥德巴赫猜想而在中国家喻户晓。

同样研究自然数,陶哲轩走的路子跟泰勒的相去甚远。泰勒研究的代数数论,是尝试通过代数结构来理解自然数;而陶哲轩研究的解析数论,则是尝试通过函数的解析性质(例如有关上下界的估计)来进行探索。

在解析数论中,能用到的工具很多。除了经典的微积分(也就是高数中能学到的东西),还涉及更复杂的调和分析、代数数论以及组合中的一些工具。解析数论中的两大方法,筛法与圆法,前者可以看成组合学中容斥原理的巧妙应用,后者则是复分析与调和分析的集大成者。而陶哲轩在解析数论领域的重要贡献之一,就是引入了新的工具与技巧。他与本·格林证明了,存在任意长(而不是无限长)的等差数列,其中的每一项都是素数。在这个证明之中,他们用圆法拓展了组合中一个由斯泽梅雷迪发现的深刻定理,利用了有关加性组合的新思想解决解析数论的问题。这也使人们更多关于有关加性组合的研究。

(要更深入了解解析数论,请参阅《素数并不孤独》以及果壳网对Helfgott的专访

除此之外,陶哲轩在调和分析、偏微分方程方面也有重要的贡献,这两个领域对实际应用的影响更大。在工程中经常使用的小波分析,其实就是调和分析的一种应用。而陶哲轩对调和分析的研究,也直接催生了一门新的技术——压缩感知。在工程学中,我们经常需要测量某些信号,比如在摄影中,测量就是照相,而信号就是要成像的物体。压缩感知,其实就是如果我们知道信号的某些特殊性质,那么即使只进行少量的测量,在合适的情况下仍然能大体还原整个信号。利用这种方法,已经有人制作了只需单个像素感光元件的照相机,效果还不错,而需要记录的数据量则大大降低。这项技术在医疗诊断、人脸识别等广泛的领域都有重要的应用。

陶哲轩在组合学方面的工作,除了与解析数论有关的加性组合以外,还有代数组合。他与艾伦·克努森(Allen Knutson)发现的蜂窝模型给出了李特尔伍德-理查森系数的又一个组合解释,这些系数与一般线性群的表示论以及格拉斯曼簇的上同调有关,他也借此解决了代数组合中的一些猜想。


广阔的数学

还有剩下三位的工作又是什么呢?

很遗憾,笔者也不清楚。

剩下的这三位,笔者仅仅知道他们研究的领域都与“代数几何”这一数学分支有关。虽然代数和几何大家都很熟悉,但“代数几何”作为一个整体,听说过的人可说是寥寥无几。代数几何奠基于希尔伯特的零点定理,之后经过格罗滕迪克之手一发不可收拾,目前已经发展数学中一门非常重要而又高度抽象的分支,与数学的其它分支有着各种各样深刻的联系。笔者虽然也有做代数几何的朋友,但是聊天的时候从来没有听懂过他的工作。

先不要急着用皮鞋追打笔者,也不要揭穿笔者各种打小广告的行为,笔者这样捉急,也是有原因的:

数学的跨度实在太广了,而每个领域都太深奥了,现在,即使穷尽一个人的一生,也难以涉猎数学的所有领域,而这些专家的所有工作横跨各种各样的领域,要一一详细解释更是难上加难。即使是数学系学生,对于很多没有钻研过的领域的理解,也只是“听说过大概是那么一回事”的程度而已。

这并不是数学特有的现象。实际上,现在整个科学体系经过数百年的不断积累,已经发展为一个庞大的整体。在牛顿的时代,一人尚且可以跨越数个不同的学科同时有所建树;在居里夫人的时代,一人最多也只能在一个学科的许多领域都有贡献;在现代,一人最多只能在一个学科的几个领域得到重大的成果,而绝大部分的研究者熟悉的仅仅是他们主攻的一两个领域。学科的细分前所未有,这也是一种必然,科学体系经过一代又一代研究者成年累月的积累,迟早会突破个人能掌握的极限,即使是天才。专业化、细分化,这是唯一的出路。

而数学研究领域之广阔,研究对象之丰富,研究方法之多样,也是其他学科中少见的。这也造成了数学分支之间前所未有的隔膜。研究量子群论的数学家,丝毫不会担心公理集合论中不可达基数的存在性会不会影响他的研究;埋头苦干纳维-斯托克斯偏微分方程的研究生,多半也永远不会用到范畴论中有关自伴逆变算子的结论;即使是代数几何的大拿,如果被问起随机幂律图的直径分布,大概也只能摇摇头。也正因如此,数学中跨领域的合作弥足珍贵,一个领域的数学工具如果能用在另一个领域中,常常也会带来意想不到的惊喜。

除了专门化之外,数学还有一个其它学科少有的特点:高度的抽象化。在欧拉的时代,数学还能表现成那种人人熟悉的数学式子;而在希尔伯特的时代,数学家们早就不满足于这种略显简单的抽象,决意利用更为抽象的语言将数学精确化,于是诞生了公理集合论;而随着代数拓扑与代数几何的发展,公理集合论已经略显繁琐,数学家们又引入了更抽象的范畴,又推广出高阶范畴,在其中,即使是无比复杂的结构,也被抽象为点与箭头、箭头之间的箭头、箭头之间的箭头之间的箭头,层次永无止尽;而到了现在,又兴起了对一种名为“拓扑斯”的特殊而又更为抽象的范畴,某些数学家甚至希望用它来代替公理集合论作为数学的基础。

这也使有关数学的传播难上加难。由于数学固有的抽象性,向一般大众传播有关数学的新知,常见的结局无非两种:传达的信息正确无误,但读者只能不明觉厉;传达的信息过度简化甚至歪曲,读者读得高兴,自以为理解,实际上却是谬种流传。而在科技日新月异的今天,即使是身边的技术,其中的包含的数学也早已非一般人能够掌握。对于现代的数学研究而言,高中数学不过是玩具,而大学中传说挂了无数人的高数,也只不过是基础中的基础。但对于绝大多数人来说,高数已经远远超过他们所需要掌握的数学。在保持正确性的前提下,现代的数学研究即使经过高度简化也难以为大众所理解,这也是非常正常的事情。如何逾越这个障壁,将数学的美、数学的作用以及研究数学的乐趣向大众传达,走出新的道路,这是一个难题,也是一个必须思考的问题。

互联网新贵们设立这个数学巨奖来奖励数学家,也是这种数学传播的一种尝试。他们希望能将公众的注意力吸引到数学研究上,让更多的人关注数学、喜欢数学,从而间接地鼓励未来的数学研究,还有未来的科技发展。“数学突破奖”这个奖项,在奖励数学家以及吸引公众目光这两方面已经胜利完成任务。但君子之泽,三世而斩。接下来,如何将这种对数学的一时关注转变为长期关注,转变为观念,转变为更好的政策,转变为文化,这是同时考验慈善家、数学工作者、媒体工作者、政治家,以及我们每一个人的问题。

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

本文遵守首页的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 ——也能证明自身的一致性,而这是不可能的。

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

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

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

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

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

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

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

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

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

计算无处不在。

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

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

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

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

殊途同归

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

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

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

Lambda演算

图灵机模型

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

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

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

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

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

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

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

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

伦敦皇家学会学报

万变之宗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最小的通用图灵机

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

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