数和符号的轨迹:2020年阿贝尔奖解析

本文首发于微信公众号“赛先生”,遵守首页的CC版权声明:署名-非商业性使用-禁止演绎,请自觉遵守,非授权者禁止转载。


所谓数学家,就是能够发现定理之间相似之处的人。
好的数学家能够看到证明之间的相似。
最优秀的数学家则能够看到理论之间的相似。
可以想象,终极的数学家应该能够看到相似之间的相似。

——斯特凡·巴拿赫(Stefan Banach,1892–1945)

凡物无成与毁,复通为一。唯达者知通为一。

——庄子

你取来一杯黑咖啡,在电脑前坐下来,将准备好的牛奶倒进咖啡,然后用勺子慢慢搅拌,咖啡很快就从黑白分明变成了棕色,散发出温和的香味。然后你在电脑上看到这样的文字:

假设X是一个上密度为正的自然数集合,那么对于所有的正整数k,在X中都存在一个长度为k的等差数列。

这似乎跟你和你的咖啡毫不相干,但阿贝尔奖,也可以说是数学界的终身成就奖,今年的两位得主希勒尔·弗斯滕伯格(Hillel Furstenberg)和格里戈里·马尔古利斯(Grigory Margulis)获奖的原因,正是他们看到了搅拌咖啡和代数、数论以及组合的某些问题之间的相似性,并由此解决了许多问题,发展出了新的数学分支。

但在具体解释两位获奖者的工作之前,我们先来考虑一个问题:为什么将加了牛奶的咖啡搅拌之后,它就会慢慢变得均匀?

图片来自Pixabay

结局与路线

这个问题似乎太简单了,本来分开的东西,搅拌一下就会混合起来,咖啡是这样,颜料也是这样,这都是天经地义的事情,还用问吗?

问题在于,这并不是天经地义。比如说水和油,如果随便搅拌一下的话,只消静置几分钟,水和油就又分离开来了。虽然在特定的条件下,油可以分为极其细小的油滴悬浮在水中,与水均匀混合,比如说牛奶就是这样,但这种状态并不是绝对稳定的。比如说,拿起半瓶牛奶用力摇晃十几分钟后,你就会发现牛奶分成了固体和液体两部分,固体部分就是奶油,也就是原来悬浮着的油滴。

那么,为什么牛奶和咖啡可以轻易混合,但水和油却不行呢?物理中的热力学给出了答案:水分子和油脂分子非常不喜欢靠近对方,硬要混合它们就需要很大的能量,而如果顺其自然的话,假以时日它们会逐步到达能量最低的地方,也就是水油分离。牛奶和咖啡的分子没有这个问题,所以能够均匀混合。

这是个很好的解释,但并没有回答我们一开始的问题。热力学告诉我们咖啡和牛奶能够混合均匀,但却没有告诉我们搅拌在其中扮演了什么角色。热力学能告诉我们结局,但对于如何到达这个终点却是无可奉告。就像人终有一死,这是热力学的答案,但我们更关心的是这个人经历了什么,是重于泰山还是轻于鸿毛。能告诉我们这些的,是物理的另一门分支,也就是动力学。

太阳系行星轨道,图片来自NASA JPL

太阳系行星轨道,图片来自NASA JPL

动力学研究脱胎于庞加莱对天体力学的研究。自从牛顿发现天体流转和苹果落地同样遵循万有引力的同一套微分方程之后,人们就开始利用微积分的语言来描述和研究行星的运动,也依此发现了海王星。自此之后,数学家将同样的一套方法论应用到不同的物理体系甚至数学体系中,也就形成了一门新的学科。

动力学研究的,就是物理系统怎么样从一种状态演变为另一种状态。被搅拌着的咖啡和牛奶构成了一个所谓的“动力系统”,而动力学研究的,则是各种各样的动力系统如何随时间而演变。无论是钟摆来回摇动,还是气象风起云涌,甚至连太阳系的运转,都可以看成某种动力系统。而对动力系统的研究,随着研究对象越来越多,也逐渐变得越来越抽象,最后演变为一门独立的数学分支。

飘摇的轨迹

为了研究不同的动力系统,数学家引入了状态空间的概念,在物理学中也叫相空间,它是一个抽象的几何空间,其中每个点都对应于动力系统的某个特定的状态。比如说,如果考虑太阳系行星这个动力系统的话,可以固定太阳的位置为原点,而八大行星各自的位置和速度就组成了动力系统的状态。每个行星的位置和速度都分别需要3个数来描述,合起来的话,要描述太阳系行星这个动力系统就需要48个变量,而它对应的状态空间也就是一个48维的空间。动力系统随时间的演变就相当于状态空间中点的轨迹,而动力系统理论研究的就是这些轨迹的行为。

不同的动力系统,对应的状态空间中也有着各种各样的轨迹。比如说太阳系对应的状态空间,有的轨迹经过一段时间就会一去不复返,这就意味着某个行星永远地离开了我们;有的轨迹是闭合的,一次又一次地重复自身,形成动态稳定的体系;有的轨迹虽然不会完全重复自身,但却会无限靠近某条闭合的轨道;有的轨迹却更加任性妄为,行为捉摸不定,但却像被某种奇异的力量吸引着,永远不会远走高飞。可以说,这些轨迹就决定了动力系统的性质,所以动力系统理论的研究目的之一,就是刻画这些轨迹的性质以及它们之间的关系,还有确定某个特定的状态会遵循什么样的轨迹等等。

Van der Pol oscillator,图片来自Wikipedia

Van der Pol oscillator,图片来自Wikipedia

因为动力系统发源于物理学,所以人们最初研究的那些动力系统,比如星体和天气,都遵循着刻画物理规律的微分方程,对其的研究也紧紧遵循着数学分析的传统,其中的重镇就是俄国数学家亚历山大·李雅普诺夫,他对于连续动力系统中轨迹稳定性的判定有着极为重要的贡献。此外,数学家也意识到,有时候我们并不需要知道整个系统在任何时间的行为,而只需要知道在某些特定的时间间隔中系统的行为。由此得到的就是离散动力系统的概念,其中连续的时间变成了离散的时刻,而动力系统本身就决定了这个时刻的状态会如何变换成下一个时刻的状态。

洛伦兹吸引子,图片来自数学电影《Chaos》

洛伦兹吸引子,图片来自数学电影《Chaos》

但随着对动力系统研究的深入,人们发现了那些捉摸不定但却永不远离的轨迹,只要它们的初始状态有一丝一毫的偏离,经过一段时间的演化,它们就会踏上完全不同的道路。这就是混沌现象,而对这种现象的研究也已经发展成混沌理论这一独立的学科,它与概率论、分形都有密切的关系。同时,随着数学家研究的动力系统越来越复杂,他们发现确定性的微分方程似乎已经落后于时代,反而是描述随机性的概率论和描述一般空间的拓扑学更加符合他们的需要。于是,动力系统的研究方法就慢慢转向概率以及拓扑,也就此取得了更大的成果,也由此扩展到了更为广泛的对象,不一定是连续的空间,也可以是离散的对象。这就给弗斯滕伯格和马尔古利斯的工作埋下了伏笔。

走遍天下

让我们回到咖啡的例子。之前说到,热力学说明咖啡和牛奶组成的体系最终会到达能量最低的状态,但其实牛奶刚刚倒进咖啡之后,它们的能量就已经是最低的了!也就是说,热力学并没有说明为什么在搅拌之后两者会混合起来而不是仍然分离。

如果你熟悉热力学,你可能会说这就是热力学第二定律的结论,因为体系会停留在熵最大的宏观状态,也就是对应微观状态数最多的宏观状态。对于咖啡和牛奶来说,就是完全混合的状态。此话不假,但实际上正是热力学第二定律包含了一个隐含的假设:体系处于能量相同的任意微观状态的可能性都是相同的。这个假设被称为遍历假设,“遍历”的意思就是体系可以经历所有状态,而且这些状态对它来说都是平等的。遍历假设自然可以推出热力学第二定律,但在动力学上却并非显然正确,因为完全有可能存在某个状态永远不能达到。于是,想办法证明某种类似的结论就成了数学家心头的一大问题。

把牛奶加入咖啡中,搅拌之后牛奶还是那么多,只不过分散在了整杯咖啡之中,搅拌的操作不会改变牛奶的多寡。许多动力系统也是如此:我们可以在状态空间中定义某种“容积”的概念,用术语来说就是测度,使得一组占据一定容积的系统状态,无论经过多少时间,仍会占据着相同的容积。这种动力系统被称为保测动力系统,“保测”的意思就是“保持测度”。

庞加莱在研究天体力学时就已经注意到任何由常微分方程定义的动力系统都满足这一条件,也就是说,所有通过经典力学构建的动力系统都是保测动力系统。同时,它们因此有着特殊的性质:如果系统中没有任何轨迹会无限远离的话,那么从任何初始状态出发的轨迹,假以时日,即使不能回到初始状态,也可以到达离它要多近有多近的某个状态。这就是庞加莱复现定理。这个定理也被另一位数学家策梅洛用于质疑热力学第二定律:如果系统总是能返回初始状态的话,那么混合好的咖啡和牛奶也终有一天会重新泾渭分明,这似乎正是热力学第二定律所禁止的。

幸而,正如热力学只告诉我们最终结局,庞加莱复现定理也只告诉我们最终会回到某个非常靠近初始状态的地方,但没有说清楚需要多少时间。通过仔细计算,我们能够得到大概所需的时间,也就是所谓的庞加莱复现时间。对于一杯加了牛奶的咖啡来说,这个时间比宇宙的年龄还要长得多,这就保住了热力学第二定律作为经验法则的地位。但这也意味着,如果我们希望考虑系统长期的变化,也许不应该着眼于单个时刻的状态,而更应该考虑长期变化的平均值。

在二十世纪三十年代,冯诺依曼和伯克霍夫等人各自在这个方向上的努力最终结出了成果。他们证明了所谓的“遍历定理”:假设由常微分方程定义的动力系统满足某些假设,那么给定状态空间中的某个领域,从任意状态出发的演化过程通过这个领域的时间比例几乎必然会趋近于领域在整个状态空间中所占据的空间比例。比如说,如果搅拌的方法满足某些假设,那么即使我们不去追踪咖啡杯里牛奶的某个液滴划过的轨迹,也可以确定它大概有一半时间会呆在咖啡杯左半边。这就相当于证明了遍历假设在平均意义上是正确的,于是热力学第二定律也是如此。

那么,遍历定理中的“某些假设”到底是什么呢?

说起来也简单。在状态空间中,我们考虑某个容积不为零,但严格小于整个空间的区域。直觉上来说,如果所有能够到达这个区域的状态恰好就是这个区域内的所有状态的话,那么遍历假设显然就不成立,因为区域以外的大量状态无法进入这一区域。神奇的是,只要假定这种区域不存在,遍历定理就必然成立。满足这个条件的保测动力系统就是所谓的遍历系统,而遍历理论就是对遍历系统的研究。

伯克霍夫也意识到,他的遍历定理实际上并没有局限于常微分方程定义的动力系统,而是应该对于其他遍历系统也成立。后来的研究者沿着这个方向,将遍历定理进行了大量的推广。随着研究的逐渐深入,人们意识到,虽然保测动力系统脱胎于微分方程描述的物理系统,但它的定义只牵涉到状态空间上的测度。也就是说,保测动力系统系统实际上相当于某个测度空间上的保测变换,正是这个保测变换让我们能从一个状态达到下一个状态,而遍历系统所需的条件也能完全用测度的语言来描述。

所以说,遍历系统的本质在于测度,而具体的状态空间到底表示什么,是整个系统的状态还是牛奶液滴的位置,这都只是表象,可以忽略的表象。正因为遍历系统的本质在于测度和保测变换,所以即使遍历系统本身没有包含任何不确定性,但遍历理论与同样建基于测度的概率论仍然有着许多共通之处。这两个领域中的研究互相渗透,已经得到了丰硕的成果。

但遍历理论和概率论毕竟仍然属于广义上的分析,它们与广义上的代数似乎相差甚远。想必任何学过大学数学课程的人都会感觉微积分与线性代数就像两个完全不同的世界。弗斯滕伯格和马尔古利斯的贡献,就在于他们借助遍历系统本身的抽象性,成功跨越了分析和代数之间的鸿沟,将遍历理论的方法应用到了代数和组合的广泛领域中,得到了大量的成果,开创了全新的领域。

弗斯滕伯格:整数中的遍历系统

Hillel Fursterberg,图片来自Wikipedia

Hillel Fursterberg,图片来自Wikipedia

弗斯滕伯格出生在1935年的德国柏林。对于一名犹太人来说,这个时机实在太坏。他可能也不太记得在德国的生活,因为在1939年的水晶之夜之后,为了活命,他父母就带着一家人逃到了美国。颠沛流离之后接下来的并不是好日子,弗斯滕伯格的父亲去世之后,他们一家的生活过得更为拮据。但这并没有阻碍弗斯滕伯格求学的脚步。他就读了专门为犹太人开设的宗教学校,然后升入了当地的大学。就在那里他接触到了数学的美,并就此走上了数学的道路。

在大学的期间,他就已经在数学方面崭露头角,因为利用拓扑的语言证明了素数有无限个而小有名气。这也许也预示了他能在不同数学分支之间看到相似性的能力。之后他到了普林斯顿大学就读博士,博士导师是同样由德国逃出来的博赫纳(Salomon Bochner)。当时博赫纳正在深入研究概率,而弗斯滕伯格的博士论文,题为《预测理论》(Prediction Theory),自然也是有关概率的。这篇博士论文讲述了对时间序列进行预测的理论,其中也牵涉到遍历理论。对于这篇论文的水平,某位评委的评语是“这是一篇具有高度原创性的第一流博士论文,涉及的课题也相当困难”。

博士毕业之后,弗斯滕伯格开始尝试将概率论的方法应用到别的数学对象之中。他通过对于随机矩阵乘积的研究,开始探索所谓“半单李群”这一类代数对象的结构,并且在一系列论文中逐步明晰定义了所谓的“弗斯滕伯格边界”,用以刻画半单李群上的调和函数。他的这项工作利用概率论的工具剖析了某些群的结构,即使这些结构与随机性毫无瓜葛。这一跨界的工作也对相关的代数研究产生了巨大的影响。

这一系列论文之后,弗斯滕伯格名声大噪,很快就得到了美国明尼苏达大学的教授职位。但此后不久,他就离开美国移居以色列,并在这个犹太人魂牵梦萦的“应许之地”扎下了根。在那里,他开始尝试继续钻研遍历理论,提出了不少重要的概念与猜想。比如说,通过类比整数之间互质的关系,弗斯滕伯格提出了遍历系统之间的“不相交性”(disjointness)。这个概念相当自然,但人们发现其实它也极为深刻,在分形几何、信号处理等领域都有着重要的应用。

但弗斯滕伯格最激动人心,大概也是最容易解释的工作还在后头。在他就职的耶路撒冷希伯来大学,经常有不同领域的数学家来做讲座。有一次,一位访客做了一个关于组合数论的报告,其中提到了当时刚刚被塞迈雷迪(Szemerédi Endre)证明的一个精彩定理。假设有一个整数的集合A,如果无论取多大的正整数n,都有一个比它更大的正整数N,使得在-N到N之间的整数至少有某个固定的比例包含在集合A中,那么A就必定包含任意长度的等差数列。用数学术语来说,就是拥有正上密度的整数集合A必然包含任意长度的等差数列。

这是个奇妙的结果。我们对集合A的要求相当弱,只要不算太稀疏,满足这个条件的集合A可以随意包含任何元素,自然也可能混乱得毫无章法。但无论集合A多么混乱,只要它的上密度为正,那么我们必定可以在这种混乱中找到某种结构,在这里就是要多长有多长的等差数列!这种断言我们必定能在混乱中找到结构的定理,属于所谓“拉姆齐理论”的范畴,它的研究牵涉到组合数学和数理逻辑,其中有着许多困难的问题,而这个后来被命名为塞迈雷迪定理的结论也是其中之一。

当时塞迈雷迪对塞迈雷迪定理的证明惊动一时,不仅是因为定理本身的难度,还因为塞迈雷迪在证明中提出了一个重要的引理,后来又将其推广,成为了今天所说的塞迈雷迪正则性引理。这个引理在图论中有着非常广泛的应用,甚至可以说,这个引理比塞迈雷迪定理本身更为重要。

但弗斯滕伯格在这个定理中却看到了别的东西。在讲座结束之后不久,他就给讲者发了一封电子邮件:“我可能找到了这个定理的另一种证明。”他在塞迈雷迪定理中看到的,自然是动力系统。

我们考虑所有由整数组成的集合,这些集合组成了一个状态空间。对于某个集合A,如果将其中的每个整数都加上1,我们就得到了另一个集合,这种变换又叫平移变换。然后弗斯滕伯格利用平移变换,定义了有关整数集合的一些保测动力系统,而塞迈雷迪定理就相当于断言这些保测动力系统假以时日必定会以特定的方式多次“回归”初始状态,就像庞加莱复现定理所证明的那样。接下来,弗斯滕伯格洞察到,这个结论不仅对于这些有关整数集合的保测动力系统成立,而且对更广泛的双射保测动力系统也成立。于是他将庞加莱复现定理推广到多次回归的情况,证明了所谓的“弗斯滕伯格多次复现定理”,由此也就推出了塞迈雷迪定理。

弗斯滕伯格对于他的多次复现定理的证明也很耐人寻味。首先,定理中的动力系统可以分解为遍历系统,所以我们可以利用遍历理论的工具来研究这一点。虽然遍历系统数不胜数,但它们之所以拥有遍历这一性质,基本上出于两种原因:要么系统本身几乎是周期性的,也就是说,经过一定时间之后,系统中的状态会几乎回到原始状态,但却有一点点偏差,日积月累的话,靠这种偏差就能逼近所有状态;要么系统本身就处于混沌之中,不同部分的状态在经过一些时间之后就会均匀地混合在一起无法区分,而每个状态也会很快“忘记”自己的起点,和光同尘。虽然本质并不相同,但这两类遍历系统中都存在多次复现的现象。然后弗斯滕伯格证明了,他考虑的动力系统中必定包含前面其中一种遍历系统,从而也会有多次复现的现象。这个证明就很有拉姆齐理论的风格:无论动力系统如何复杂混乱,都能从中找出拥有特定规律的一部分。

弗斯滕伯格的证明的意义在于,它打开了利用动力系统的工具来研究困难组合问题的大门。塞迈雷迪原本的证明虽然很有意义,但却非常艰深,用到了复杂的技术,不容易推广到更普遍的情况。但弗斯滕伯格的证明,虽然用到了看似复杂的动力系统,但总体而言更直观更容易理解,也容易推广。之后不久,弗斯滕伯格和他的合作者就将这个动力系统证明进行了各种各样的推广,获得了与塞迈雷迪定理类似的数个更为强大的结论。在弗斯滕伯格等人的开拓下,利用遍历理论对类似问题的研究已经成为了一门名为“遍历拉姆齐理论”的分支,也结出了相当的成果。

虽然弗斯滕伯格除此以外还有不少其他方向的研究,但他在整数中看到动力系统的这一洞察,将原本属于连续的方法延伸到了离散,用全新的视角得出了出人意料而又困难的结论,并且他开辟的这条道路仍然有着大量的问题等待探索。可以说,弗斯滕伯格的这项成果,属于数学中第一流的贡献。

马尔古利斯:代数中的遍历系统

Grigory Margulis,图片来自MFO

Grigory Margulis,图片来自MFO

另一位获奖者格里戈里·马尔古利斯的运气相对来说稍微好一些。他也是犹太人,然而他出生于1946年苏联的莫斯科,虽然也被歧视,但起码性命无虞。马尔古利斯很早就展露出了数学天赋,16岁时参加国际数学奥林匹克就获得了银奖,之后也进入了在数学方面最负盛名的莫斯科国立大学就读。因为是犹太人,所以马尔古利斯想必也攻破了在入学口试中专门用于防止犹太人入学的“棺材问题”,也就是有着初等解答但却极端困难的问题。他居然能够作为一名犹太人入读莫斯科国立大学,只能说明他的数学天赋实在是出类拔萃。

在博士期间,马尔古利斯师从动力系统专家雅科夫·西奈(Yakov Sinai,2014年获阿贝尔奖),动力系统也就成了他研究的主线。但他研究的并不算是传统的动力系统理论,而是动力系统理论在代数领域的应用。

我们身边的许多东西都有着令人惊异的对称性。五瓣的梅花旋转72度后,与原来丝毫不差;六芒的雪花,如果将它旋转60度,或者沿着某根主轴翻到另一面,也保持与原来几乎相同的形态;光盘更是无论如何旋转,几乎都无法与原本的状态区分开来。所有这些东西,如果对它们执行某些特定的动作,那么得到的结果与原来的状态没有区别,这就是它们对称性的一种体现。对称性越高,符合这种条件的动作也越多。我们会觉得轮胎比梅花更对称,因为旋转梅花时,如果角度不是72的倍数,那么花瓣就会错位,但光盘无论旋转什么角度都几乎不变。从这种对称性抽象而来的数学对象就是群,那些动作就是群的元素,而群论就是通过群这种抽象结构来研究种种对称性的数学分支。

数学中有着各种各样的群,而数学家花了大量的精力来对这些群进行分类。最简单的分类之一就是连续群和离散群。光盘的对称群就是连续的,因为我们可以旋转任何角度,稍微多转一点少转一点,对于光盘来说无关紧要。也就是说,光盘的对称群中的元素是可以连续变化的。另一方面,梅花的对称群就是离散的,要保持形状完全不变,旋转角度就必须是72的倍数,多一点少一点都不行。所以,梅花的对称群中每个元素之间都被远远地分隔开来,这就是它被称为“离散群”的原因。

不同的群之间可以有各种各样的关系,最直白的就是一个群可以包含另一个群,这时我们也说后者是前者的子群。比如说光盘的对称群就包含了梅花的对称群,因为梅花的对称群中的元素都是角度各异的旋转,而光盘的对称群包含了所有角度的旋转,自然也包含了梅花的对称群中的所有元素。容易发现,连续群中可以包含离散群,但离散群却无法包含连续群。数学家发现,对于某些连续群来说,只需要研究它包含的离散群,就能得出许多关于连续群本身的重要性质。马尔古利斯的研究就处于这个方向,而他研究的群,专业术语里被称为“半单李群”,而其中包含的离散群被称为“格子群”。

但这些群跟动力系统又有什么关系呢?

之前提到,群可以看成保持某些结构不变的操作组成的集合,但这个结构完全可以是这个群本身!我们可以将整个群看成一个状态空间,而群里的元素就是状态。但群里的元素也可以看作对状态空间的变换。于是,我们可以通过选取合适的元素作为变换,在整个群中定义出各种各样的动力系统。此外,在群中也可以定义某种特定的“容积”,也就是测度,使得所有这些通过群里元素定义的动力系统都是保测动力系统。从这里开始,遍历理论就能派上用场了。

在马尔古利斯之前的数学家就已经意识到,通过某些特定的连续动力系统的性质,就能推测出连续群的各种性质,而马尔古利斯在前人的基础上更进一步,利用动力系统以及概率论的方法,证明了半单李群格子群的许多重要结论。其中最重要的大概是他在1975年证明的“超刚性定理”,刻画了半单李群中被称为“算术格子群”的一类有着重大意义的格子群,还有他在1978年证明的“正规子群定理”,刻画了半单李群格子群的重要性质。正因为做出了这些重要的工作,他被选为1978年菲尔兹奖的四位获奖者之一。

但他并没有亲自领到这一奖项。

1978年,冷战正酣。虽然几年前美苏和欧洲各国签订了赫尔辛基条约,在欧洲换得了暂时的和缓,但很快双方关系又因为其他冲突继续恶化。在当时的苏联,出境必须预先向政府报批,而马尔古利斯未能获批去往赫尔辛基参加国际数学家大会。这也许是苏联的传统,马尔古利斯的前辈谢尔盖·诺维科夫(Sergei Novikov)在八年前也获得了菲尔兹奖,同样由于未受苏联政府批准出境而无法出席领奖。只有到12年后的1990年,苏联已然苟延残喘时,他们的后辈弗拉基米尔·德林费尔德(Vladmir Drinfeld)才能够亲身领到属于他的菲尔兹奖。

而即使已然跻身顶尖数学家的行列,这也没有给马尔古利斯带来多少好处,因为他是苏联的犹太人。在博士毕业之后,尽管已是同龄人中的佼佼者,他却无法在苏联数学水平最高的莫斯科国立大学找到教职,只能就职于信息通讯问题研究所(Institute for Information Transmission Problems)。这个研究所的名字,一看就知道与马尔古利斯所研究的数学相去甚远。

但这也许并不完全是一件坏事。马尔古利斯在研究所的同事主要研究计算机科学。有一次,他们向马尔古利斯提到了扩展图的概念。扩展图是一种特殊的组合对象,在复杂度理论中,它可以将少数几个随机比特扩增为一大批随机性足够强的伪随机数来提供给随机算法使用。因此,研究者会利用它将某些随机算法“去随机化”,将其转变为确定性的算法。但在1973年,人们只知道扩展图必定存在,但却没有人知道如何明确构造一系列的扩展图。马尔古利斯听到这个问题之后不久,就找到了一个明确的构造回答了这一问题,而他的构造利用了他在研究半单李群格子群时用到的所谓“卡日丹(Kazhdan)性质(T)”,一个牵涉代数表示论的性质。深奥的代数结论带来的重要构造,在计算机科学的历史上可以说凤毛麟角,而这一跨界行为也展现出马尔古利斯解决各种问题的能力。

然而,马尔古利斯之后的跨界更为惊人。

我们在中学都学过多项式,比如说xy+yz+xz就是一个三元二次多项式。不仅如此,因为它的每一项都是二次的,所以我们也说它是一个齐次的多项式。数学家猜想,对于至少包含三个变量的实数多项式,假设它的取值可以为正也可以为负,而且所有系数同时除以任何实数都不会同时得到有理数的话,那么随便选取一个实数x,都能找到一些整数,将它们代入多项式之后得到的值可以离x要多近有多近。这就是所谓的奥本海姆猜想,它属于“丢番图逼近”这一领域,也就是关于用整数或者有理数通过不同的方法来逼近任意实数的研究,属于数论的范畴。

一般来说,丢番图逼近的问题都不怎么容易,通常会用到分析数论或者代数数论的深奥结论。奥本海姆猜想也不例外,但那些常用方法在这里却碰到了死胡同。但在1987年,马尔古利斯利用遍历理论漂亮地证明了这个猜想。他首先观察到一个已知的结果:奥本海姆猜想等价于有关某个特殊的半单李群格子群的断言。然后通过之前对半单李群格子群的研究,他找到了这个断言与某些遍历系统之间的关系,从而利用遍历理论中的方法得出了证明。

马尔古利斯的这一证明,给丢番图逼近这一领域引入了全新的方法。自此之后,人们开始关注动力系统与丢番图逼近之间的关系。而更重要的是,马尔古利斯利用遍历理论的方式非常新颖,从中发展出了一门名为齐性动力系统的全新分支,并且由此得到了大量与数论等其他领域相关的重要结果。

与弗斯滕伯格一样,马尔古利斯除此之外还有众多重要的工作,但他利用动力系统的视角去解决代数问题,然后又在数论问题中觉察到代数结构,然后再利用动力系统与代数结构之间的联系去解决数论问题的这一洞察力实在令人赞叹,不仅在数学的不同分支之间看到了相似的结构,而且还能活用这种相似性来解决困难的问题,甚至连解决办法本身都引出了更深入的研究方向。毫无疑问,对于数学来说,这同样是第一流的贡献。

顺带一提,马尔古利斯在获得菲尔兹奖之后,虽然职位和待遇一时也没有什么变化,但出国访问比较容易获得批准了。之后他经常出国访问,在苏联解体之后也很快移居到了美国,就任耶鲁大学的教授,直到退休。

结语

纵观弗斯滕伯格和马尔古利斯的工作,可以说,他们各自的工作将动力系统这一原本更偏向于概率论的数学分支,与代数、组合、数论等看似风马牛不相及的数学分支联系了起来,由此创造了新的数学分支。他们证明的结论不仅重要,而且富有洞察性,为数学开辟了新的道路。两人都曾获得沃尔夫数学奖,这次同时获得沃尔夫奖这一数学界的终身成就奖,完完全全实至名归。

数学,是研究抽象结构及其之间关系的学科。虽然数学被人为分成了无数的分支,不同的数学分支有着不同的方法论,对抽象结构的着眼点也各不相同,但抽象结构本身却并不专属于任何一个分支,而是可以在截然不同的分支之中同时出现。然而,只有那些智者,才能洞察那些繁杂的数学分支,发现它们之中有着相同的抽象结构,从而将一个分支的方法,通过同一个抽象结构,用于解决另一个分支的问题。在科研越来越细化的今天,这种能力越发珍贵。

参考文献

  1. De la Salle, Mikael, “Raconte moi… la propriété (T) “, Gazette des Mathématiciens, Société Mathématique de France, 2016.
  2. Dinur, Irit, “The PCP theorem by gap amplification” (PDF), Journal of the ACM, 54 (3): 12–es. 2007.
  3. Eskin, Alex, “Unipotent Flows and Applications”, Clay Mathematics Proceedings, Volume 10. 2010.
  4. Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel. “The ergodic theoretical proof of Szemerédi’s theorem”. Bull. Amer. Math. Soc. 7 (3): 527–552. 1982.
  5. O’Connor, John J.; Robertson, Edmund F., “Grigory Margulis”, MacTutor History of Mathematics archive, University of St Andrews.
  6. O’Connor, John J.; Robertson, Edmund F., “Hillel Furstenberg”, MacTutor History of Mathematics archive, University of St Andrews.
  7. “Furstenberg and Smale Receive 2006–2007 Wolf Prize” (PDF). Notices of the American Mathematical Society. 54 (4): 631–632. 2007.
  8. “A biography of Grigory Margulis”. The Abel Prize. Retrieved 2020-03-22.
  9. “A biography of Hillel Furstenberg”. The Abel Prize. Retrieved 2020-03-22.
  10. “Citation by the Abel Committee for the Abel Prize 2020”. The Abel Prize. Retrieved 2020-04-02.
  11. “Ergodic hypothesis”. Wikipedia. Retrieved 2020-04-02.
  12. “Ergodic theory”. Wikipedia. Retrieved 2020-04-02.
  13. “Grigory Margulis”. Wikipedia. Retrieved 2020-04-02.
  14. “Hillel Furstenberg”. Wikipedia. Retrieved 2020-04-02.

计算的极限(十三):数字空间的幽灵

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

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

计算无处不在。

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

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

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

当汤玛斯(Robert Tomas)在1971年写下他的“小小实验”所用的代码时,肯定不会想到,他写下的Creeper代码会开启数十年后的一门“黑色产业”。现在,面前的计算机上,掌心的智能机中,广阔的互联网内,有着无数幽灵飘来荡去,凯觎一切有价值的信息,操纵一切能被操纵的机器。这是一个庞大的产业,而同样庞大的是为了防御这些幽灵而生的守护者。计算机病毒和杀毒软件,两者你追我赶,永无止尽。注定这两者命运的,正是一条数学定理。


到处乱窜的代码

在计算机发展的早期,计算资源非常珍贵,只有军队或者大学才拥有计算机,还要排队才能用上。但如此宝贵的计算资源有时候却会被白白浪费。计算机不需要休息,但是人却必须睡眠。人不在的时候,计算机往往就空下来了,这就造成了需求的不平均。有某些计算需要特定的数据,但如果只为了一次计算去传输未免太浪费,这就是数据的不平均。要想将计算资源压榨到最后一滴,就需要消除这些不平均的因素。用现代术语来说,就是负载平衡的问题。

1969年见证了一样新奇事物的诞生。为了共享资源,美国军方开发了阿帕网(ARPANET),旨在将散落在美国各地的军用计算机连结起来。那就是网络的石器时代。我们现在习以为常的各种概念,比如说电子邮件、网络协议等等,当时还不存在。程序员手中所掌握的,就是几台大型计算机,以及连结它们的简陋而原始的网络。

但条件匮乏并不能阻碍程序员的脚步,他们是开辟新天地的先锋。既然信息可以在网络中流动,那么运行的程序本身可不可以在计算机之间转移呢?可行的话,某个程序在一台计算机繁忙的时候,可以自动跳到空闲的计算机上,而如果这台计算机上没有需要的数据,它也可以自动跳到有相应数据的计算机上执行。“程序自动转移”的这个想法,一下子就能同时解决需求和数据不平均的问题,岂不美哉?

当时汤玛斯在一间名为BBN的公司里,与同事为阿帕网内的计算机编写操作系统。这个操作系统叫TENEX,其中内置了网络功能,汤玛斯琢磨着,能不能利用相应的功能,写出一个能自动转移的程序呢?

他成功了。

他写了一个叫Creeper的程序,功能很简单:首先在当前计算机上读取一个文件,然后寻找网络上的另一台计算机,将程序本身和附带的文件都打包传送过去,在当前计算机上删除自身,最后留下一句话:

I’M THE CREEPER : CATCH ME IF YOU CAN.
(我是CREEPER:有本事就来抓我吧。)

-说我? -走开,不是说你! -不开心,要炸了……(图片来自gamepedia)

Creeper说明“程序自动转移”确实可行。但问题是,放出来的Creeper不太好收拾,一时间它在阿帕网上跳来跳去,令人烦心。

但糟糕的还在后头。没几天,新版本Creeper出现了,它在传送的时候不会在原来的计算机上删除自身,也就是说它将自己复制到了另一台计算机上。据说始作俑者是汤玛斯的同事雷·汤姆林森(Ray Tomlinson)。可以说,新版本的Creeper满足了广义上病毒的定义:在用户不知情的情况下自我复制的程序

跟所有病毒一样,新版本Creeper也惹来了大麻烦:它很快就感染了网络上的所有计算机,而且即使人们在一台计算机上将它清除,也很快会受到来自网络上另一台计算机的感染。也许是为了人道主义的补锅,汤姆林森很快写出了另一个名为Reaper的程序,它基本上就是Creeper的变种,会以同样的方式感染网络上的计算机,但在感染完成后,会尝试移除计算机上的Creeper,最后自行关闭。

这就是第一个计算机病毒。


从玩笑到犯罪

在计算机发展的早期,因为用户群体相对小,宵小之徒还没来得及盯上这个领域。当时大部分病毒被编写出来的目的,其实是为了炫耀技术,或者搞搞无伤大雅的恶作剧。所以,当时的计算机病毒通常不会造成什么大损失,而且经常带着一丝幽默。比如说1982年出现的Elk Clone病毒,“危害”就是会自动显示一首诗。还有1990年前后肆虐的Cascade病毒,就会使终端命令行的字符“掉下来”(当时的界面也差不多只有命令行)。这些病毒都是通过软盘传播的,现在已经成为了时代的眼泪。

另一些病毒则是阴差阳错的结果。比如说第一个木马病毒ANIMAL,它在1975年出现,本体是一个猜动物的小游戏。为了进行自动更新,作者另外编写了另一个小程序PERVADE,执行时会将自身和ANIMAL复制到当前用户能访问的所有文件夹之中,包括共享文件夹,与其他用户共享。每当用户运行ANIMAL游戏时,它会自动执行PERVADE程序来完成复制,通过共享文件夹,整套程序就完成了从用户到用户的感染。要放到现在,这应该就叫P2P自动更新推送。另一个例子就是1986年出现的Brain病毒,本来是防盗版措施,但在作者加入自我复制的功能之后,它就成了名副其实的病毒。

随着计算机的普及,奸诈之徒也开始出现,病毒也越来越有破坏性。强行关闭计算机和删除文件自然不在话下,加密文件以勒索赎金也早就有人干过。甚至直接破坏计算机硬件的病毒也出现了,比如臭名远扬的CIH病毒,是经历过上世纪90年代洗礼的人们心中难以拂去的梦魇。

进入21世纪之后,犯罪分子编写病毒的目的也逐渐改变,从单纯的破坏转为牟利。将感染转化为利益有很多方法,最直白的就是勒索软件,它们通过强大的加密“劫持”重要数据和操作系统这些“人质”,只有受害者支付一笔“赎金”之后,才能“赎回”计算机的正常使用。最近的WannaCry就是一个例子。另一种方法就是搜索和截获信用卡的账号和密码等有价值的信息,然后直接通过这些重要信息牟利。还有一种方法就是操纵被感染的机器,把它们用在其他恶意用途上,比如DDOS[link]或者发送垃圾邮件,而黑客可以出售这些“服务”来牟利。无论哪种方式,都是一本万利的生意。

重利之下,病毒的始作俑者也变得团队化和全球化,对信息安全造成了重大威胁。只要是可以运行程序的机器,他们都不放过,比如新近出现的物联网,由家用电器组成的网络。因为物联网上的设备通常疏于更新而且留有后门,入侵起来实在易如反掌。目前最大的僵尸网络Mirai(日语中意即“未来”),大部分就是由物联网设备组成的。就规模而言,似乎这个模式的确是恶意软件的未来。

盯上病毒的除了贼还有兵。为了进行情报活动,各大国对计算机安全的研究都进行了巨大的投入,编写出前所未有精巧的新病毒,危险性远远超出了犯罪团伙。最近美国国家安全局“囤积”的大量漏洞和黑客工具被泄露,更是说明了国家力量可以造成多大的损失。其中仅仅一个漏洞“永恒之蓝”(Eternal Blue),就给我们带来了WannaCry这个勒索软件,使世界各地的许多机构陷于瘫痪。


矛与盾

有无相生,先后相随。既然有病毒,用户就有清除病毒的需要,也就有了杀毒软件。可以说,杀毒软件追随着计算机病毒而生。杀毒软件的任务就是识别并清除病毒。

面对如此麻烦的病毒,人们自然想追求一劳永逸的解法。是否能写出一个完美的杀毒软件,它不仅能查杀一切已知的病毒,还能查杀以后可能出现的任何病毒呢?

然而,牵涉到判断计算机程序具体行为的问题,基本上都是不可能完美解决的。我们之前已经看到,不存在一个程序能够判别任何一段代码在执行时是否会出错。同样,不存在这样的杀毒软件,能完美无缺地辨别任何计算机病毒,不论是已知的还是未知的。这实际上是Frederick B. Cohen在1987年证明的定理,他又被誉为计算机病毒防御技术的创始人。对于本系列的读者来说,这个定理其实是停机定理的推论,这也许并非意料之外。

所以,对于任何杀毒软件来说,下面两种情形至少有一种会发生:要么把正常的程序当作病毒消灭了,要么在眼皮底下放过病毒,前者叫误杀,后者叫漏杀,两者此消彼长。当然,不存在完美的杀毒软件,并不阻碍我们精益求精,做出越来越精密的杀毒软件。再加上逐利不竭的犯罪分子,可以说,杀毒软件这个行业永远不会停止发展。

那么,人们是如何一步一步改进杀毒软件的呢?杀毒软件的目标,在于区分正常程序和计算机病毒。不同的病毒查杀技术,实际上就是各种将病毒从正常程序中区分出来的方法。

最早的杀毒软件可以追溯到1987年,当时的病毒很简单,数量也很少,要将它们同正常程序区分开来也很简单。当时的病毒通常有一些特定的程序代码,用以执行感染和发作的步骤。安全研究人员可以先定位并提取不同病毒中这些有特征性的代码(又称为“特征码”),放到杀毒软件的数据库里。杀毒软件的工作,就是检查每个文件是否存在相应病毒的特征码,如果存在,这个文件十有八九就包含了病毒。


幻化万端

但道高一尺,魔高一丈。病毒的制作者当然也观察到了这样的现象,他们开始想尽办法制作不同的变种,改变病毒的代码,比如在病毒体内加入没有实际效用的所谓“花指令”,或者将不同的指令变换为功能相同的指令,以此躲避杀毒软件的检测。但这样的手段,即使一时骗过了杀毒软件,在新病毒被研究人员捕获并分析之后,杀毒软件很快就能更新到能查杀新的变体。

病毒制作者自然不会善罢甘休。既然特征码针对的是病毒代码之中的固定部分,那么如果病毒在每次传播时,具体代码都会改变,那不就能逃脱特征码查杀的套路了?沿着这种思路开发的病毒,又叫自修改病毒。

最早的自修改病毒叫1260,早在1990年就出现了。它由两个模块组成:代码模块和解密模块。代码模块平时是被加密压缩的,而病毒在被激活时,会先运行解密模块,把包含真正的感染和破坏指令的代码模块解密,然后再去执行代码模块。而当病毒感染其他文件时,会随机打乱解密模块的部分内容,形成新的解密模块,然后用它来将代码模块重新加密。这种复杂的构造,就能保证每次感染时出现的病毒体都与以往完全不同,大大增加了查杀的难度。这种相对简单的自修改病毒,又叫多态病毒(polymorphic virus)。

然而这种小技巧并没有难倒安全研究人员。就像自然界中真正的病毒那样,多态病毒即使变异很快,仍然有一些至关重要的部分保持相对稳定,那就是解密模块。研究人员很快就学会了利用解密模块的特征来识别多态病毒。迫使多态病毒采用更多措施来打乱自身代码,比如说自动加插花指令和进行等价指令的替换,又或者是自动重新排列自身的代码。但安全研究人员很快就想出了反制的办法,毕竟这些改动都不算大,检测也不算困难。

最后病毒制作者只剩下一个希望:写出一个病毒,在每次感染时,病毒的几乎每一段代码都会产生重大改变。这样的话,就不可能在代码的层面上探测出这个病毒了。

说得轻巧,但具体怎么做呢?

黑客们想出了一条可谓破釜沉舟的计策:每次要感染新文件时,先把病毒本身转换为某种“中间代码”,然后将中间代码用另一种完全随机的方式编译,得到的就是全新的病毒代码。这种中间代码可以有无数种编译方式,但得到的代码执行时的行为都完全一样。以这种方式编写出来的病毒,又叫变形病毒(metamorphic virus)。通过先转换为中间代码再编译的方式,它们“变形”得到的具体代码千变万化,但具体的行为却完全一致。

最有名的变形病毒叫Simile,在2002年第一次出现,当时给安全研究人员带来了很大的麻烦。正因为它可以“变形”为与之前完全不同的代码,这使得特征码提取的方法基本失效。幸而变形病毒的研发非常复杂,尤其是“变形”所需的代码非常复杂(Simile中有90%的代码专门负责变形),所以变形病毒数量相当少。但即使变形病毒的门槛很高,随着技术的进步,也终会有普及的一天。即使是为了未雨绸缪,也应该想办法开发新技术去对付这种新型病毒。


听其言,观其行

不久之后,安全研究人员想到了两个办法,它们的核心思想都很简单。变形病毒改变的是它们“外在”的代码,但“内在”的行为,也就是病毒具体会做什么,却是不会改变的。如果有办法拨去具体代码的面纱,探测它们的“实际行为”,也就是语义,岂不是就可以成功查杀这些病毒了么?

第一个方法,就是尝试将变形病毒的“变形”过程还原,尝试将它们固定到同一个形式中。研究人员首先将变形病毒的代码拆解出来,然后用程序分析它的逻辑结构。因为变形病毒无论怎么变形,它的功能是不变的,所以具体的逻辑结构也不会有太大的变化。只要能识别它逻辑结构中不变的部分,就能识别同一类的病毒,无论它们怎么变形,代码有多不同。当然,分析一段代码的逻辑结构并不容易,研究人员借鉴了当时编译器的某些优化编译功能,可以将没有用处的指令剔除,也可以分辨出那些本质上等价的代码。最终结果相当成功,通过分析逻辑结构本身,就能有效查杀那些变形病毒。

研究人员想到的第二个办法更加直接。既然我们想要探测病毒的“实际行为”,那么何不让它实际“运行”一下,看它会做出什么举动?当然,我们不能在用户的计算机上实际运行可疑文件,否则如果可疑文件的确是病毒,那么麻烦就大了。研究人员做的,就是模拟一个病毒可以运行的环境,又叫“沙盒”,然后在这个环境中模拟病毒的运行,观察它的行为并记录下来。病毒通常会有一些特征行为,比如多态病毒就会访问并改写自己的代码,而变形病毒则会执行“变形”步骤。对于杀毒软件来说,对于可疑的程序,它可以先在沙盒中模拟这个程序,如果观察到的行为符合某个病毒的特征行为,那么这个程序很有可能就包含病毒。这种技术又叫沙盒查杀技术。但因为在沙盒内运行程序需要消耗不少的计算资源,所以只能用在一些特别重要的位置或者特别可疑的文件上,比如系统文件和内存。

“沙盒”原本是供小朋友游玩的设备,无论弄得再乱七八糟,也只是沙盒内部的事。图片来自Wikipedia

实际上,沙盒查杀技术的用途不止于此。因为它检测的不是具体的代码,而是程序的行为,所以从理论上来说,这种技术能够用于检测未知病毒,走在病毒编写者的前面。不同的病毒会有不同的特征行为。有的病毒会检查操作系统的语言和当前时间,然后决定是否进行感染;有的病毒会尝试将自身注册为操作系统的底层驱动,用以隐藏自身;有的病毒会尝试枚举所有程序,准备感染它们;有的病毒会枚举特定文件然后进行加密,这是勒索的必备步骤。不同的行为有不同的风险,面对可疑文件,杀毒软件可以先在沙盒中运行它们,记录它们的行为。如果这些行为大体类似某个已知病毒,那么这个文件就可能包含病毒。即使没有检测到相应的病毒,如果记录到的行为过于危险可疑,杀毒软件也可以对它进行标记和隔离,以供进一步研究。这就是所谓的“启发式查杀技术”。确切地说,使用沙盒的是动态启发式技术,但也有所谓的静态启发式技术,只需要观察文件的代码,而不需要具体执行。利用最近兴起的机器学习技术,安全研究人员还能进一步提高启发式技术的可靠性。

启发式技术虽好,但并非无懈可击,因为它不能完全确定检测结果是对是错,有可能会误杀正常程序,毕竟很多正常程序,尤其是系统底层的驱动程序,也会作出与病毒相似的某些行为,但它们并不是病毒,而且对于计算机的正常运行至关重要。误伤这些文件会导致很多问题,而偏偏病毒倾向于感染这种贴近底层的文件来逃避侦测。我们有时会听到这样的消息,某款杀毒软件在更新后突然干掉关键系统文件,而且是成片发生。比较极端的,甚至还有解放军在演习中武器系统被杀毒软件咔嚓了的事件。但随着技术的发展,目前这些意外已经越来越少,杀毒软件的功能也越来越强大,查杀技术也越来越精确。

在杀毒软件和病毒的斗争之中,沙盒技术和启发式查杀技术有着重大的意义,因为它第一次让安全研究人员能部分走在病毒制作者的前面。在它出现之前,杀毒软件只能跟在病毒后面亦步亦趋,但有了这项技术,病毒制作者也就不能随心所欲编写新病毒,而要对市面上的杀毒软件进行一番研究,才能保证自己的新病毒不会在沙盒中被启发式查杀干掉。事实上,现在相当一部分的病毒被查杀时,仅仅会被识别为“一般病毒”(generic virus),因为阻止它们的是启发式技术,不需要具体识别它们的类型。

现在摆在病毒制作者面前的就是这样一个问题:怎么样才能躲过沙盒技术呢?也就是说,有没有办法在执行的时候,让病毒“意识”到自己身处沙盒而不是一台真正的电脑之中呢?

办法不是没有。既然沙盒是一种需要大量资源的模拟,为了减少资源的使用,杀毒软件的沙盒必定会有某种破绽。比如说,如果沙盒对于模拟的系统时间没有特殊处理的话,因为沙盒的模拟比真正的执行要慢,所以病毒可以通过测量执行某段代码所需的时间来得知自己是否处于沙盒之中。一旦安全研究人员发现有利用这种缺陷的病毒,他们就可以修正缺陷,重新取得先机。在这个战场上,亦步亦趋的不再是安全研究人员,而是那些病毒制作者。

但沙盒毕竟是模拟环境,总会存在破绽,病毒也可以等待一段时间再发作,以此逃避杀毒软件的检测。有些安全研究人员就有了一个大胆的想法:何不让要检测的程序自由运行,等到出现了可疑的行为再查杀不迟?毕竟病毒要复制和传播,必然要进行某些特定的操作,比如说读取其他程序或者调用某些特殊的系统函数。只要在病毒作出这些操作的瞬间进行拦截,那就没有问题了。这就是行为检测技术,要做到这一点,杀毒软件需要利用特殊的技术(Rootkit)监测所有应用程序的一举一动,在它们请求操作系统进行任何任务时,拦截并分析具体的请求。这种技术一开始是病毒用以隐藏自身痕迹而开发的,现在反而成了杀毒软件的武器。


永无休止的斗争

当然,杀毒软件的技术再好,也不能保证绝对的安全。越好的查杀技术,通常使用的资源也越多。如果对每个文件都采取最高级的查杀技术,那肯定会大大拖慢系统的运行速度,所以在具体编写软件时,安全研究人员需要进行适当的取舍。既然有取舍,那就会有漏洞可供利用。另外,病毒制造者也可以先下手为强,感染时想办法先把杀毒软件干掉,或者利用操作系统本身的漏洞取得整个系统的主导权,直接架空杀毒软件。互联网技术发达之后,杀毒软件厂商可以让杀毒软件自动上报可疑文件,尽早获得新病毒的资料;病毒制作者也可以让病毒自动更新,不停逃避杀毒软件的追杀。病毒和杀毒软件的攻防战线广阔异常,从磁盘到内存甚至显卡,都是它们的战场,而攻防策略之多,无论如何列举都只能是挂一漏万。

但尽管杀毒软件现在已经成为非常成熟的技术,病毒要感染计算机,也还有别的路可以走。操作计算机的毕竟是人,跟杀毒软件相比,人的“漏洞”更多,更容易被利用。有多少人嫌麻烦不去更新系统填补漏洞,给病毒以可乘之机?又有多少人看到“请查收文件”的邮件,就急匆匆点开附件,丝毫不检查文件的来源和性质?还有多少人用的密码就是123456,或者上网看到什么链接,无论多么可疑都点进去看看?一个系统的安全,取决于最薄弱的环节。如果没有信息安全的意识,杀毒软件再好,也挡不住人类作死的脚步。

计算的极限(十二):不会出错的程序

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

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

计算无处不在。

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

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

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

相信每个人都见识过Windows那令人忧郁的蓝屏或者黑屏吧。有时因为它,一个上午的工作一瞬间毁于一旦,这就不仅是令人忧郁而是令人抓狂了。在这个时候,你是否会在心中大声咒骂那帮写程序不小心让蓝屏一而再再而三出现的程序员呢?但程序员也不是铁打的,他们也会犯错误。而且对于商业软件来说,在上市之前会进行大量的测试,即使有程序错误溜过去了,大多也可以通过打补丁来修复。

但是对于某些软件来说,情况就麻烦得多了。


无妄之灾

在1996年的一个不能说的日子,欧洲航天局第一次发射了新研制的Ariane 5运载火箭。在起飞37秒之后,新火箭很想不开地开花了。这令砸了几亿欧元进去的欧洲航天局非常不爽。经过调查,专家组发现,事故的罪魁祸首竟然是短短的一段代码。

Ariane

在Ariane 5的软件中,有一部分代码是直接来自它的前辈Ariane 4。由于Ariane 4当时非常成功,所以大家觉得这样做没什么问题,根据新的参数稍微修改一下代码就好了。问题是,修改并不完全。有一行代码需要将64位浮点数转换成16位整数,他们认为不会出现什么问题,所以没有进行修改。也没有测试这段代码。

就是这行代码,因为Ariane 5比前辈Ariane 4强力得多,于是在Ariane 4上没有问题的这行代码,在Ariane 5上发生了溢出错误:那个64位的浮点数代表的数值超出了16位整数可以表达的范围。在出错后,备用代码系统被启动,其中包含着同样的一行代码。结果就是整个系统被锁死了。更为讽刺的是,这行代码所在的函数,对于Ariane 5来说是不必要的。这场事故完全就是人祸。

经过这场事故之后,欧洲航天局大为震怒,决定要一劳永逸地解决Ariane 5的问题。他们的要求相当大胆:Ariane 5的软件代码,正式使用前要证明它们不会出现毁灭性的错误,比如不会溢出,不会死循环等等。

这其实并非易事。


停机定理

我们复习一下停机问题:是否存在一种算法,给定任意的程序和输入,都能在有限的时间内判断该程序在给定的输入下是否会停止?正是图灵,证明了这一点是不可能做到的。于是,要编写一个能判断程序会不会进入死循环的算法,这是不可能的。但对于其他类型的程序错误,能否用算法判定呢?

很可惜,这也是不可能的。实际上,我们可以将停机问题规约为检测错误的问题。假设我们有一个程序P,能检测某段代码是否会出现除以零的错误,而我们想要借助这个程序判断某个图灵机在给定的输入下会不会停止。我们可以怎么做呢?首先,对于给定的图灵机和输入,我们可以机械化地将它们转化为一段不用除法但能够模拟该图灵机的代码,然后在模拟结束之后,强行计算1/0。我们将这段代码称为T。代码T在执行时会出现除以零的错误,当且仅当图灵机会停机。然后,我们将代码T输入程序P。于是,既然程序P能判定任意的代码会不会出错,那么就相当于它能判定任意的图灵机会不会停机,而这是不可能的。停机问题不存在普遍的算法,也就是说证明代码无误同样没有普遍算法。

但是,欧洲航天局的任务是否完全不可能完成呢?那倒也不是。停机定理只是说明了不存在程序能正确判定所有程序是否会停止,但欧洲航天局只需要证明Ariane 5的软件代码这一个程序不会出错,所以这条路也没有完全被堵死。

那么,有什么办法呢?


抽象释义

虽然我们不能判定所有程序是否不会出错,但我们能有效判定某些程序不会出错。比如说,如果一个程序没有任何循环语句或者跳转语句,那么这个程序最终肯定停止。但如果程序有循环语句又怎么办?这时,我们并不能确定程序会不会停止,而最保险的办法就是说“我不知道”。

这就是抽象释义(Abstract Interpretation)方法的根本:先抽象出程序的某些信息,再对这些信息进行自动分析,来尝试确定程序是否有着我们想要的性质,比如说不会死循环、不会溢出等等。我们不强求完美的分析,不强求能够识别出所有不出错程序。但为了安全起见,我们要求这种分析是可靠的,也就是说,如果分析的结果认为程序有着我们想要的性质,那么这个结论就不会出错。正是因为这样的权衡取舍,抽象释义方法才能正确有效地实行。

Galois Connection

根据抽象出来的信息多少,不同的抽象释义方法判断同一种性质的效果也不一样。一般来说,抽象出的信息越详细,能识别的拥有某种性质的程序就越多,相应地计算时间也越长。如何在性能和识别率之间做取舍,也是一门复杂的学问,对于不同的应用和数据结构,需要开发不同的抽象方法和自动分析算法。

多种抽象方法还有另一个优点。如果某个程序有着我们想要的性质,但是手头上的抽象释义方法又不能确定时,我们可以换用更精细的、利用更多信息的抽象方法。直接改写代码也是一种规避分析失败的方法。例如,我们想要证明某段代码不会出错,但某种抽象释义方法指示在某句代码上可能会有问题,那么我们可以通过修改代码,换用更加谨慎的处理方法,来保证抽象释义方法能确认新的代码不出问题。

抽象释义方法的奠基者是法国的Patrick Cousot和Radhia Cousot。这对夫妻档总结了一些对程序进行自动形式证明的方法,在此之上提出了抽象释义方法,将其形式化严格化。他们对抽象释义方法的推广也功不可没。除了Ariane 5的代码之外,在别的一些关键应用处的代码也利用抽象释义方法进行了至关重要的验证。一个例子是空中客车A380的控制代码,经过Patrick Cousot的一个小组开发的抽象释义软件Astrée验证,证明了这些控制代码运行时,不会产生像死循环、溢出或者被零除之类的一些软件问题,从而也给安全系数多加了一层保险。

Patrick CousotRadhia Cousot

不过,抽象释义方法只能证明程序有着某种我们想要的性质,不能说明程序是否完成了我们希望的任务。有没有办法做到这一点呢?


形式证明

有一种激进的做法:让程序员在编写代码的同时,给出这段代码确实完成了给定任务的数学证明

要给出这种证明,首先要解决的就是如何将“代码完成了给定任务”转换成数学命题。程序代码可以相当容易用逻辑表达,但代码需要完成什么任务,这只有程序员才知道。所以,要让程序员在编写代码的同时给出证明,为的是让程序员能用逻辑的形式确定这个函数的功能,如此才能得到要证明的命题。这种想法不仅仅是数学家的纸上谈兵。对于某些关键系统,多么微小的疏失都会导致极其严重的后果,人们愿意几乎不惜一切代价防止错误的发生,而对于计算机程序而言,又有什么比数学更坚实的基础呢?

要贯彻这种想法,在编写程序之前,必须先选择一种逻辑体系以及描述它的一种形式语言。这种形式语言必须贯穿整个代码编写的过程:先用形式语言描述程序的输入、输出、功能与限制,然后利用这种与形式语言相近的编程语言去具体编写代码,最后还要利用形式语言给出编写的代码能完美无瑕疵地实现所需功能的数学证明。这种做法又被称为演绎验证(deductive verification),是所谓的“形式化验证”(formal verification)的手段之一。

但数理逻辑毕竟不是一门容易的学科,数学证明对于很多人来说大概比编写代码要困难得多。所以,演绎验证多数也只会用在那些不容有失的关键系统,比如说牵涉人数众多的公共交通设施。例如,在1998年开始运营的巴黎地铁14号线,就是一条全自动的地铁,列车上没有司机,安全行驶也全靠传感器和软件,调度也只需要在控制室点点鼠标就能增加或减少投入运营的列车数量。于是,安全在很大程度上在于软件的可靠性。在控制列车的计算机中,某些与乘客安全休戚相关的关键代码是利用演绎验证编写的。在2012年,巴黎历史最悠久的地铁1号线也从人工运营转到与14号线同系列的全自动化系统。现在,这两条地铁线每天接待的人数加起来超过一百万,但从未因为自动化系统的错误导致乘客伤亡。从笔者的经验来说,它们可以算是巴黎最可靠的地铁线。

Paris Metro 14

但仅有代码的正确性可能还不足以保证程序同样正确,因为代码毕竟不是程序,计算机不能直接执行代码。我们需要另一种名为“编译器”的程序。编译器是将程序员写的代码翻译成计算机能读懂的、用机器语言写就的程序。即使代码是正确的,如果编译器有问题,得出的程序还是可能出错。要避免这个问题,我们同样需要利用数学方法加固编译器这一环。

贯彻这种设计理念的一个例子是一个叫CompCert的C编译器,它由法国计算机科学家Xavier Leroy和他的小组编写。编译器的任务就是进行忠实的代码翻译,确保源代码和目标代码的行为一致。这一点至关重要,否则即使代码是正确的,也不能保证编译生成的程序不出问题。然而,现代的编译器在优化模式下,其实并不能确保忠实的编译。CompCert要解决的就是这个问题。在编写CompCert的时候,对于编译程序的每一步操作,都附带一个数学证明,确保代码的语义不变。因此,数学证明的正确性保证了CompCert编译器会完全忠实地将代码翻译成机器语言。

但即使机器语言是正确的,也还不能完全保证最后执行结果的正确性,因为程序总需要输入输出,而这些功能是由操作系统保证的。如果操作系统本身有错误,即使执行的程序本身是正确的,由于操作系统的问题,也不能保证我们看到的结果是正确的。如果想将数学证明的保证贯彻到底,还需要对操作系统下工夫。这就是seL4所做的事情。seL4是一个微内核,可以看成操作系统的核心。它的每一个功能都附带一个数学证明,在对硬件做一定的假设之后,数学证明的正确性可以保证它提供的功能都会产生我们预先设定的行为。只要硬件不出错,seL4就会正确运行。

当然,一个自然的问题是,如果硬件出错怎么办?硬件的错误可以分为逻辑性错误和物理性错误。前者例如Intel当年在芯片上除法的错误,现在主流硬件厂商早已吸取教训,用演绎验证的方法加固他们的硬件设计;后者例如宇宙射线令硬盘数据出错,这即使是多复杂的证明也避免不了,只能自求多福。尽管数学方法不能保证错误不存在,但至少将可以避免的问题全数避免,这本身就有着莫大的价值。

Real programmers, xkcd
(或者可以利用宇宙射线……?)

计算的极限(十一):黄金时代

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

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

计算无处不在。

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

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

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

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬
计算的极限(五):有限的障壁
计算的极限(六):无穷的彼岸
计算的极限(七):宛如神谕
计算的极限(八):符号的框架
计算的极限(九):叹息与奋斗
计算的极限(十):无限绵延的层级


“我要借了阿尔志跋绥夫的话问你们:‘你们将黄金时代的出现豫约给这些人们的子孙了,但有什么给这些人们自己呢?’”

——鲁迅

黄金时代

但波斯特并没有能够亲眼在《数学年报》看到他和克林的这篇论文。

双相情感障碍一直困扰着他,即使每天只工作三小时,即使用尽办法平伏情绪,每得到一些新的数学结果,这些发现和创造都让他激动不已,处于症状发作的边沿。对于数学家来说,这可能是最扭曲最恶毒的诅咒。数学家的使命在于发现新的数学,这种发现必然带来的喜悦,对于波斯特来说,却会危及他为了发现数学所必须的清醒头脑。

在1954年初,又一次的发作将他带到了纽约的一家精神病院。当时治疗精神疾病的主要疗法有两种,波斯特接受的是电休克疗法(http://songshuhui.net/archives/7382),而同样受精神疾病困扰的另一位数学家纳什接受的则是胰岛素休克疗法。电休克疗法在当时还很原始,虽然以相当高的症状缓解率得到了医生的青睐,但原始的疗法过程痛苦可怕,也有一定的副作用。

在1954年4月21日,波斯特接受了又一个疗程的电休克治疗。在他不停抽搐之时,他的心脏失去了控制。

他没有挺过去。

刊登着他和克林的论文的《数学年报》,则是在5月出版,只差不到一个月。

除了波斯特以外,可计算性理论这个领域的其他开拓者,哥德尔、图灵、丘奇这些先驱,他们的结局又如何呢?

由于二战即将爆发,哥德尔在1939年偕同家人移居到了普林斯顿,恰好在图灵回英国之后。之后,他一直作为普林斯顿的教授活跃在数理逻辑学界。但在四十年代后期,他的关注点渐渐从数理逻辑转移到了哲学,也不再发表他的数学工作。可以说,这就是他的数学生涯的终点。而他的人生的终点要等到近四十年之后。在晚年,他的心理变得不稳定,总是怀疑别人要毒害他。在他的妻子因病入院六个月时,他竟然不接受任何人的食物,活活饿死在普林斯顿的医院里。

图灵在1939年博士毕业后回到剑桥,旋即被英国军方聘用,专注破译德军密码,为二战胜利立下了汗马功劳。在战争结束后,他尝试制造一台计算机,但在英国政府的不作为,被在美国的冯·诺依曼抢了先。除此之外,图灵还提出了有关人工智能的图灵测试,并且一直思考前沿的数学问题。作为一名同性恋者,在被警方发现之后,图灵被迫接受治疗。最后在1954年6月8日,他的生命永远地终止了,床边放着一个沾着氰化物的苹果。

丘奇可能是最幸运的人。他一直在数理逻辑这个领域里奋斗,直到生命的尽头,并且硕果累累。这也许是一名数学家能希望拥有的最好结局。他也是一位优秀的博士导师,门下的31位博士中,就有图灵、克林和罗瑟这样的大师。在生命中困扰着他的,也只有晶状体混浊导致的视力问题,与其他几位先驱相比,实在无足轻重。

正因为丘奇卓越的成果,以及其他人的缺席,他以及他的学生在当时的数理逻辑学界中有着举足轻重的影响。自然,丘奇那种过分追求严谨的作风以及他的λ演算在当时也支配了整个学界。但作为计算模型,λ演算不仅不直观,而且过分形式化,很多实际上很简单的结论,用λ演算证明的话会无比繁复。数理逻辑本来就是一门艰深的学科,证明稍稍复杂一些也相对正常。但当图灵机这样直观的模型出现之后,许多定理换用图灵机模型就能被更直观更容易理解地证明,但许多人由于惯性仍然使用λ演算做研究,即使他们对此也颇有微词。

λ演算在当时的影响之大,就连图灵当时在丘奇门下攻读博士时,毕业论文中用到的计算模型也完全是丘奇的那一套λ演算,尽管他自己提出的图灵机概念更加清晰直观。有些数理逻辑学家甚至认为,图灵的序数逻辑当时不受关注,部分原因要归结于用到了λ演算这套形式语言。就连克林,他自己作为丘奇的学生,也对λ演算很不满意,可能是因为他的文章总是遭到读者的冷遇。他在1935年之后很快就抛弃了λ演算,改为用递归函数的模型来阐述结果,读者的反响果然迅速改善。而丘奇过分严谨的作风对学界的统治,使得图灵和波斯特那种诉诸直观(但能被轻易严格化)的证明,在当时被视为异类。

学界的惯性是强大的。丘奇在1935年提出λ演算,而他追求完全严谨的作风对学界的统治要直到五十年代中后期才开始慢慢松动。其中有两个原因:第一是随着可计算性理论的发展,这个领域的定理越趋复杂,λ演算这个框架在严谨性方面带来的好处,逐渐被它的复杂性所抵消;第二是随着基于图灵机模型的现代计算机的发展,人们对图灵机越来越熟悉,对图灵机的研究也越来越深入,人们对于图灵机模型的使用也越来越得心应手。这两个因素一推一拉,渐渐改变了学界的风气。时至今天,在可计算性理论中,人们更偏向于使用图灵机,而λ演算早已不见踪影。但λ演算并没有就此消失于学术界,人们很快就发现它的另一个用武之地,但这是后话,留待后文详述。

哥德尔、图灵、丘奇、波斯特、克林……这些开创者们,告诉了我们“计算”到底是什么,而计算之外又有什么。我们今天能惬意地躺在床上用平板电脑看视频打游戏,能与千里之外的朋友互通消息,也都部分地归功于他们打下的理论基础。但平心而论,我们给这些开拓者的颂扬还远远不够。在一般人心中,他们仍然寂寂无名。这些开拓者们,生前大多没有什么好的结局,就连死后也没有得到多少廉价的赞赏。他们为我们开拓了一个信息化自动化的黄金时代,但他们又得到了什么呢?

但也许他们也并不在乎。就像少年的波斯特那样,也许在他们眼里,数学比尘世间的一切都要美丽,只有万亿光年外宇宙的奇迹才能与之媲美。

这就是信息时代开拓者们的故事。

当然,数学家并不会停止他们探索的脚步。可计算性理论的下一篇章,将会在大洋彼岸被揭开。但在继续追寻之前,我们先来看看,这些开拓者们的遗产到底给我们的生活带来了什么。

计算的极限(十):无限绵延的层级

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

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

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

计算无处不在。

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

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

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

计算的极限(零):逻辑与图灵机
计算的极限(一):所有机器的机器,与无法计算的问题
计算的极限(二):自我指涉与不可判定
计算的极限(三):函数构成的世界
计算的极限(四):机械计算的圭臬
计算的极限(五):有限的障壁
计算的极限(六):无穷的彼岸
计算的极限(七):宛如神谕
计算的极限(八):符号的框架
计算的极限(九):叹息与奋斗


交错的存在所有

波斯特在演讲中谈到了关于自然数集之间归约的问题,而克林当时也正在研究类似的问题:用不同的逻辑公式定义的自然数集,它们是否不同,又有什么不同?如果在一个关于自然数的逻辑公式P(x)中,只有一个自由变元x,那么,使这个公式成立的所有值组成的集合就是P(x)定义的自然数集。每个自然数集又对应一个判定问题:某个自然数n在这个自然数集中吗?

用这种方法定义的自然数集,它们有着什么样的性质呢?

我们知道,在逻辑公式中,除了我们熟悉的变量和加减乘除,还有一种符号叫“量词”。量词分两种,存在量词\exists 和全称量词\forall ,每个量词都带着一个变元。不要将它们视为洪水猛兽,它们不过是又一些符号而已。存在量词的意思是,只要对应变元的某一个取值能满足命题余下的部分,那么整个命题就为真。比如说,“存在一道菜肴,我可以就着吃三碗饭”,那么只要举出一个例子(当然例子很多,白切鸡、清蒸鱼,不一而足),就能说明这个命题为真。而全称量词的意思恰好相反,它需要对应变元的每个取值都能满足命题余下的部分,那么整个命题才是真的。只要有一个反例,命题就被否定了。比如说,“对于所有的菜肴,我可以就着吃三碗饭”,只要举出一个例子(比如仰望星空派),就能否定整个命题。如果我们否定一个开头是存在量词的命题,得到的命题开头就是全称量词,反之亦然。而克林要研究的,就是这些量词会如何影响命题定义的自然数集。

我们知道,所有一阶逻辑的命题都可以将所有量词整理到命题的开头,对于现在的数学系学生来说,这只不过是一道小小的练习题。所以,我们可以假定所有命题都有着这样的形式。按照开头量词的具体形式,克林将所有有关自然数的命题分成了无穷个类别。没有量词的命题被称为零阶命题,而有量词的命题,它们开头必定由存在量词和全称量词交错组成,这样交错的段数,就是命题的阶数。对于一个n阶命题,如果它的开头是存在量词,我们就称它为n阶存在命题,反之则是n阶全称命题。根据这个定义,我们能轻易看出一个性质:n+1阶存在命题,其实就是n阶全称命题开头加上一些存在量词得到的。而在这个性质中,将“存在”和“全称”两个词反过来,它仍然成立。

(注:在关于自然数的逻辑命题中,还有一种特殊的量词,被称为“有界存在量词”。在n阶命题的定义中,我们忽略这些有界存在量词。)

来自Wikimedia

来自Wikimedia

我们来看一个实际的例子。著名的哥德巴赫猜想说的是,对于每一个大于等于4的自然数,都能被写成两个素数的和。对于某个特定的偶数2n+4,我们能将“2n+4能写成两个素数的和”写成以下的逻辑命题:
\forall a \forall b \forall c \forall d \exists p \exists q. n*2=p+q \wedge (\neg (p+2=a*b) \vee (a = 1) \vee (b=1)) \wedge (\neg (q+2=c*d) \vee (c=1) \vee (d=1))
这个命题是一个2阶全称命题,因为它的量词分两截,而开头是一个全称量词。

克林考虑了所有这些类别的命题能定义的自然数集。他将0阶命题定义的自然数集组成的集合称为\Delta_0 ,而将n阶存在命题和n阶全称命题定义的自然数集组成的集合分别称为\Sigma_n \Pi_n 。克林证明了,这些集合组成了一个向上无限绵延的层级,每一层都是自然数集组成的集合,阶数越高,命题能定义的自然数集也越多,表达能力也越强。对于每一层,总有存在这样的集合,它只能被这一层及以上的命题定义,而不能被下方更弱的层定义。也就是说,层级之间的包含关系是严格的。

也许不出大家的意料,克林证明这一切的方法,仍然是康托尔的对角线法。他定义的这个层级,今天被称为算术层级(Arithmetic Hierarchy),是数理逻辑中的一个重要概念。

arith-hierarchy

克林的这项工作,给了波斯特非常大的启发。这是为什么呢?

我们先来看看\Delta_0 到底是什么。假设集合S是\Delta_0 中的元素,那么存在一个只有单个自由变元的但没有量词的命题P(x),某个自然数x属于S当且仅当P(x)为真。那么,对于某个特殊的自然数,比如说42,要判断它是否属于S,只需要将42代入命题P(x)中检查即可。既然P(x)没有量词,那么只要硬算,就必然能得到答案。也就是说,我们有一个算法,它一定会停止,而当它停止时,就能得到答案。记忆力好的读者能观察到,这种算法就是所谓的递归函数。

那么,\Sigma_1 是什么呢?它涉及的命题拥有\exists a. P(x,a) 的形式,其中P(x,a)是一个\Delta_0 中的命题,如果将a看成一个符号的话。那么,要判断这个命题对于某个特殊的x值是对是错,最直接的方法就是先将x值代入命题中,然后对于存在量词中的变量a,从0开始枚举每一个值,然后将这个值代入P(x,a)中,命题中就再也没有自由变量,可以直接硬算它是对是错。一旦找到了某个a的值,使得P(x,a)为真,那么根据存在量词的定义,我们就能判定整个命题为真;但如果命题对于我们的x值来说不为真,那么这样的a值不存在,我们就得一直枚举下去。这是一个不一定会停止的算法,但它仍然是一个算法,而它定义的集合也就是可计算的。

那么,不可计算的问题,比如说停机问题,它又在哪个层级呢?可以证明,停机问题相关的命题可以在更高的\Sigma_2 层级中表达出来。既然层级无限绵延,那么我们自然会提出这样的问题:更高的层级中的问题到底是什么?换句话说,既然有些问题的层级比包含停机问题的\Sigma_2 更高,那么,这是否说明有些问题比停机问题更难?

波斯特之前的工作聚焦于难度处于可计算问题与停机问题之间的问题,但克林的工作促使他将目光投向另一个方向:难度比停机问题更高的计算问题,在图灵归约之下,它们有着怎样的结构?


无法触及的世界

我们先复习一下图灵归约的概念:考虑一台谕示机M,假设它带有问题A的谕示,如果它能解决某个问题B,那么我们说问题B能被图灵归约到A,记作B \leq_T A 。这跟开卷考试很类似,一位学生如果参加关于问题B的开卷考试,却带错了关于问题A的参考书,如果这位学生仍然能借助这本参考书完美地完成考试,那么我们可以说问题B不比问题A难。如果问题B能被图灵归约到A(B \leq_T A ),同时A也能被图灵归约到B(A \leq_T B ),那么我们说A和B是图灵等价的,记作B =_T A

图灵等价是一种等价关系:如果A图灵等价于B,而B图灵等价于C,那么A也图灵等价于C。我们可以将那些相互之间图灵等价的问题归为同一类(数学术语是等价类)。这些类别,被称为“图灵度”,它们之间可以通过图灵规约来比较难度,可以说,在同一个图灵度中的判定问题,在图灵规约的意义下,难度都是相同的,而带有其中任意一个问题的谕示,给谕示机带来的能力都是相同的,可以互相置换。

那么,这些图灵度到底看起来是什么样子的呢?

显然所有的可计算的判定问题都是图灵等价的,因为“可计算”的定义就是“存在图灵机可以解答”,既然一般的图灵机足以解答,那么任意的谕示机当然也可以。因为这些判定问题对于图灵机来说过于简单,不需要谕示就能完成,所以谕示的内容反而变得不重要,带有一个可计算谕示与没有谕示,对于图灵机来说是一样的。同样,任意的可计算判定问题都能图灵规约到任意的判定问题。可以说,在图灵规约的框架下,可计算判定问题就是那些最“简单”的问题,它们组成了最“容易”的图灵度,被记作\boldsymbol{0}

那么,停机问题又如何呢?图灵证明了任意的图灵机都不能解决停机问题,同样,带有一个可计算谕示的谕示机当然也不能解决,因为这样的谕示机与一般的图灵机的计算能力是相同的。也就是说,停机问题不能规约到任何一个可计算的判定问题,也就是说,停机问题比那些可计算的问题要严格地难,或者说,停机问题与可计算问题不在同一个图灵度。所以,我们至少有两个图灵度,一个是可计算的\boldsymbol{0} ,另一个是停机问题所在的图灵度,记作\boldsymbol{0}'

那么,如何构筑更难的问题呢?

图灵在他的博士论文中发现,在停机问题不可计算的证明中,将所有的“图灵机”全部换成“带有‘数论问题’的谕示机”,其他部分不易一字,得到的证明仍然正确。从而他证明了所谓的“数论问题”并不包含所有的计算问题。在这里,图灵选取了“数论问题”这个谕示,但实际上,无论选取什么计算问题的谕示,将它代入原来的证明,得到的证明仍然成立。也就是说,对于任意的判定问题A,带有问题A谕示的谕示机是否会停机,这个判定问题是不能用带有问题A谕示的谕示机解决的。如果问题A是某个图灵度\boldsymbol{a} 中的判定问题之一,刚刚的判定问题必定属于某个更高的图灵度,我们将它记作\boldsymbol{a'}

(注:顺带一提,类似这样可以将“图灵机”换成“谕示机”的证明被称为可相对化的证明(relativizable proof)。这个概念的变体在P与NP问题中占据着重要的地位。更精确地说,在所谓的“多项式归约”的概念下,解决P与NP问题的证明不可能是可相对化的。这个结论又被称为“可相对化障碍”。)

这就是波斯特构筑越来越难的图灵度的方法。对于某个图灵度\boldsymbol{a} ,考虑带有其中问题之一的谕示的谕示机,有关的停机问题处于另一个更高的图灵度\boldsymbol{a'} ,这个图灵度被称为原来图灵度的图灵跳跃(Turing jump)。从可计算问题\boldsymbol{0} 开始,通过图灵跳跃,波斯特能够一步步构建与克林的算术层级相似的图灵度层级,除了最底层的\boldsymbol{0} 以外,每一个层级都对应着那些不可计算的问题,而且层级越高,问题越难。

实际上,波斯特的图灵度层级与克林的算术层级之间的联系,比我们想象中的更深刻。我们定义\boldsymbol{0}^{(n)} 为从最底层的\boldsymbol{0} 出发,经过n次图灵跳跃得到的图灵度。波斯特证明了,如果将判定问题与自然数集等同起来,那么可以说\boldsymbol{0}^{(n)} 恰好处于\Sigma_{n+1} \Pi_{n+1} 的交集之中。也就是说,图灵度层级实际上与算术层级紧密地缠结着,图灵度层级中的每一层恰好处于算术层级的两层之间。

但图灵度层级实际上比算术层级延伸得更远。在算术层级的定义中,第n层是由那些拥有n段不同量词的命题构成的,因为命题的长度有限,所以n只能是自然数。在这里,n表达的是数量,也就是基数。但在图灵度层级中,定义的方法则是通过图灵跳跃,是一种顺序关系。在\boldsymbol{0}^{(n)} 这一层中,编号n实际上是一个序数。实际上,与康托尔的导集以及图灵的序数逻辑相似,图灵度层级实际上可以延伸到“无穷之外”,只有用超穷的序数才能表达所有这些层级。

也就是说,尽管人力能及的只有可计算的问题,但通过逻辑推演,我们能认识到,在那些我们无法解答的问题中,竟然还存在着一个精巧的结构。而正是波斯特,向我们首次展示了这个无法触及的世界。


无限绵延的层级

波斯特很快就将他的部分发现以摘要的形式发表在1948年的《美国数学学会通报》上。克林读到了这篇摘要,自然为波斯特的新发现而兴奋,但他对这份摘要并非毫无意见。

数学家尽管做的都是数学,但他们的处事方式却是各式各样。在提笔写作方面,有的数学家勤于下笔,每获得了新的结果,就会很快写出论文,并通过期刊或者私下流通预印本的形式让同行尽快知道他的结果;有的数学家却惜字如金,即使有了一整套新结果,也记录了相关的定理和证明,但却迟迟不肯下笔,也许是希望更好地打磨这些结果。著名数学家埃尔德什和欧拉是前者的典型代表,两者分别是数学史上发表论文第一和第二多的数学家。而同样著名的高斯和怀尔斯则是后者的典型代表。高斯是个完美主义者,他希望他的著作中毫无瑕疵,“将所有的脚手架去掉”,于是他发现的结果往往在抽屉里一躺就是几年,直到高斯终于满意他的写作,或者别的数学家再次发现这个结果为止。而怀尔斯独自一人在八年时间内钻研,完成费马大定理的证明主体,这早已传为佳话,被认为是怀尔斯坚韧性格的证明。这些不同的风格,也许在不同的环境下有着不同的适应性,但却没有绝对的对与错之分。

波斯特属于惜字如金的那个类别,但与高斯和怀尔斯不同,他喜欢在发表的论文中提及他已经得到的结果,承诺会写出相关的论文,但这个承诺却迟迟不见兑现的踪影。在他发表的这篇摘要里,他除了提到上述超穷的层级结构之外,还提示了更多的结果。也许波斯特是想吊一下别的数学家的胃口,但对于同样在这个领域工作的人,这很不公平。如果你也是研究这个方向的学者,你读了波斯特的这篇文章,可能希望在这些结论上生发出更深入的定理。但因为这些结论的证明并没有正式发表,你并不知道波斯特的这些结论到底是有凭有据,还是仅仅是虚张声势,从而陷入想用但没法用的两难境地。更糟糕的是,如果你发现了相同的结论,希望发表的话,又会出现优先权之争,而这是大家都不希望看到的。无论如何,仅仅提示结果而长久拖延正式论文的发表,对学术整体的发展相当不利。

克林对波斯特这篇摘要的意见也正在于此。他给波斯特写了一封信,除了赞扬他的结果以及一些讨论之外,还提及了不发表的这个问题。克林的信也许使波斯特的良心有些不安,他很快给克林寄去了一份包含他的新结果的手稿。这份手稿延续着波斯特一直以来的风格:依赖直觉,不太严谨,结构也很凌乱。因为这是一份手稿,混乱程度更甚。波斯特自己可能也知道这一点,他给克林的建议是:找个研究生,让他把内容整理出来,然后以合作者的身份一起发表这篇文章。克林依计行事,但这份手稿实在是太难理解,克林找来的研究生实在无能为力,最后克林只好捋起袖子自己动手。

克林是丘奇的学生,也继承了丘奇的那种追求严谨的研究风格。当年丘奇对严谨性的要求曾经让更依赖直觉的图灵吃了不少苦头,这次轮到克林被波斯特的手稿中的各种直觉描述所困扰了。但最终,克林还是将手稿中的内容整理出来,将缺少的证明补齐,并且做了一些延伸的研究,最后写成了一篇论文:

《递归不可解度的上半格》(The upper semi-lattice of degrees of recursive unsolvability)。

所谓的“递归不可解度”,其实就是不可计算的那些图灵度。而“上半格”是一种序结构。波斯特与克林证明了,所有图灵度其实组成了一个非常复杂但有序的结构。我们此前看到,通过图灵跳跃得到的图灵度层级与算术层级关系非常密切,但与算术层级不同的是,在每个图灵度层级之间,还有更加令人惊讶的结构存在,也就是说,阶梯与阶梯之间并不是空无一物,还有更多的结构蕴含其中。这也是显然的,因为自然数的子集有不可数无穷个,但每个图灵度中最多包含可数个子集。所以,图灵度的个数是不可数的,比我们想象中的无穷还要多得多。图灵度层级必然不能概括所有图灵度的结构,那么,必然有更多的结构存在于层级之间。

假设\boldsymbol{a} 是一个图灵度,而\boldsymbol{a'} 是它的图灵跳跃,我们来看看这两层阶梯之间到底有些什么。波斯特与克林证明了,\boldsymbol{a} \boldsymbol{a'} 之间,存在可数无穷个图灵度,它们之间互相不能比较,但都处于两层阶梯之间(用数学术语来说,就是两个图灵度之间至少存在一条可数无穷的反链)。同样在这两层阶梯之间,存在至少一条由图灵度构成的链,其中每个图灵度都可以相互比较,而更有趣的是,对于其中任意两个不同的图灵度,比如说\boldsymbol{c} \boldsymbol{d} ,假设\boldsymbol{c} \boldsymbol{d} 要难,那么这条链之中必定存在另一个图灵度,它的难度处于两者之间,比\boldsymbol{c} 要简单,但比\boldsymbol{d} 要难。用数学的术语来说,就是这条链是稠密的。也就是说,在图灵度层级之中的每两层之间,不仅存在着无数种方法从一层逐级攀登到另一层,而且在某些路径上,有一部分的路程不是常见的一级一级分立的阶梯,而是连续的无可割裂的斜坡。所有图灵度组成的结构,比我们能想像的还要复杂得多。

这篇论文,最终发表在久负盛名的《数学年刊》(Annals of Mathematics)上。可以说,它开创了图灵度研究这个新领域。到现在,图灵度理论已经成为了数理逻辑中非常活跃的一门分支,而其中主要的研究方法——被称为“优先方法”——它的一种雏形同样起源于这篇文章。

这就是作为数学家的波斯特,他的数学研究的顶峰。

计算的极限(九):叹息与奋斗

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

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

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

计算无处不在。

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

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

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

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


时代逝去的叹息

波斯特断言,存在一些形式系统,我们无法在有限的时间内知道其中某个命题能不能被证明或否证。可以说,他的断言与10年后哥德尔的不完备性定理非常相似。那么,为什么在数学史中,“不完备性定理”前面的名字不是波斯特,而是哥德尔呢?因为波斯特虽然在1921年得到这个结果,但要等到1943年,在哥德尔、图灵、丘奇的黄金时代过去之后,才得以在极省略的篇幅下发表。

他没有跟上时代的节拍。

当时的美国数学界普遍对数理逻辑没有太大的兴趣,波斯特与他的导师凯泽在当时算是异类。要等到第二次世界大战前夕欧洲数学家大幅迁移到美国,这种状况才开始改变。波斯特曾经将他的想法写成上下两篇论文,并且将上篇提交到《数学年刊》(Annals of Mathematics)。但他得到的回复十分令人失望,同行评议的报告对是否应该发表各执一词,而编辑部也没有给出具体的决定。如果没有上篇的理论奠基,那么下篇就仅仅是空谈。

但无人问津还不是最致命的问题。实际上,波斯特根本没有一个实打实的证明。也就是说,他并没有实际证明他的结论,那只是一种推测再加上关于证明的一些想法而已。虽然以我们的后见之明来看,他的结论与想法都是正确的,但他毕竟没有一个能让别人详细检验的证明。

在数学界,证明就是一切。没有证明,即使看上去再确定无误的结论,哪怕拥有再多的间接证据,哪怕是最优秀的数学家的想法,都只能是猜想,而不是定理。要确立一个定理,就必须有一个滴水不漏的证明。这就是数学界的规则。而很不巧,波斯特的研究风格比图灵更依赖直觉,换种说法就是更不严谨。波斯特的直觉足以预见超越时代的结论,但他却没有对应的能力来将他的直觉在当下整理为严谨而有条理的证明。他的雄心壮志超越了哥德尔,甚至超越了图灵与丘奇,但他当时没有足够的工具,也没有足够的能力来完成这样远大的目标。

但也许波斯特多花些时间整理他的思路,就能写出完整的证明来说服数学界。可惜命运没有给他这样的机会。

就在波斯特取得突破之后不久,也许是由于这个结果的冲击性太大,他的心理失去了平衡。而论文未能成功发表更是为这种失常雪上加霜。他患上的是双相情感障碍,患者会在无端愉悦与无故抑郁中震荡。此后十多年,他一直受双相情感障碍的困扰,在数学上毫无产出,申请到的大学教职也因为发作而不得不放弃。这段时期,他只能当一名中学教师聊以糊口。直到1935年,他才算是回到了学术界。

从1921到1935,波斯特错过了哥德尔,错过了图灵和丘奇。在他迷惘之时,时代巨轮已经呼啸而过,他错过了数理逻辑的黄金年代。在1941年,他写了一篇文章,详细叙述了他此前在逻辑的不完备性方面的工作,投往了《美国数学期刊》。时任编辑赫尔曼·外尔(Hermann Weyl)拒绝了这篇文章:

我毫不怀疑在二十年前你的工作,部分由于它的革命性,没有得到应有的尊重。但我们无法将时针往回拨;在这段时间,哥德尔、丘奇与其他人完成了他们的工作,而美国数学期刊并不是发表历史回顾的地方。

作为编辑,外尔的决定是正确的。探索的前线并不是向迷失者施予救济的地方,历史才是。历史不会忘记这些被忽视的探索者,他们所有的功绩、辛劳与忧伤。波斯特厚厚的研究笔记,就是历史的见证。当时发生的一切将化为铅字,被人们一遍一遍以不同的形式复述,成为集体记忆的一部分。

为传说撰写诗篇,并一直传颂下去,这就是我们能做的一切。

来自Wikipedia

来自Wikipedia


衡量难度的归约

对波斯特来说,错过时代节拍还不算是最大的打击。

当时人们对精神疾病的认识尚浅,没有确实有效的药物,没有确实有效的疗法,一切只能靠摸索。波斯特的双相情感障碍,同样没有标准疗法。当时的想法是,既然发作时出现的是狂喜和抑郁的极端情绪,那么就应该尽量避免这种极端情绪的发生,最好的方法就是限制会导致极端情绪的活动,对于波斯特来说就是数学。他的医生开出的疗法,就是限制波斯特做数学的时间:从下午四点到下午五点,用餐,然后从晚上七点到晚上九点,每天共计三小时。对热爱数学的数学家来说,这简直是能与精神疾病媲美的折磨,就像让美食家用牙签吃最爱的肉酱意粉,我不知道波斯特是如何忍受这种焦灼感的。

幸而波斯特并没有止步不前。他在症状缓解后很快重新投入到数理逻辑的研究中。在图灵刚发表他论述图灵机的论文后,波斯特在对图灵的研究毫不知情的情况下,发表了另一个与图灵机非常相似的模型,现在被称为波斯特机,它与我们常用的计算机更相似,驱动计算的与其说是状态的转移,不如说是语句的执行。他猜想波斯特机的计算能力与λ演算相同,这是个正确的猜测,但他当时无法证明这一点。图灵的桂冠并未因此旁落。而波斯特在看到图灵的构造与证明后也心服口服,他的探索再次失去了意义。他后来也考虑过图灵机在多维上的扩展,与后来的“元胞自动机”颇有相似之处。著名的“生命游戏”就是元胞自动机的一个例子。可惜他并没有发表这个想法。

之后,波斯特转到了布尔函数的研究,也就是那些变量与值都是“真”或者“假”的函数。在1941年,他发表了一个非常重要的结果:对于函数复合封闭的布尔函数类的分类定理。这些类别构成了一个被称为“格”的数学结构,现在被称为波斯特格。对于当时的研究者来说,波斯特的这个结果虽然很有意义,但研究的对象有些偏门,再加上波斯特典型的那种含混晦涩的行文风格,波斯特格这项成果在当时并没有得到太多的重视。要等到几十年后,人们研究约束满足问题时,波斯特格才重新回到人们的视线中。

来自Wikipedia

来自Wikipedia

这项结果虽然一开始不太受重视,但毕竟也是正经的研究结果。就这样,通过不懈的努力,波斯特一点一点重新追上了当时数理逻辑的研究潮流,即使每天只能做三个小时的研究。

在1944年,波斯特应邀在美国数学协会做了一场演讲。后来他将演讲的内容写成了论文并发表。他自己可能没有想到,这篇论文会成为他最有影响力的论文之一。这篇论文的题目是《递归可枚举的正整数集合与它们的判定问题》(Recursive enumerable sets of positive integers and their decision problems),它希望回答的问题非常简洁:停机问题有多难?有比停机问题容易的不可计算问题吗?

有时候错过时代节拍可能也是一件好事,起码对于波斯特而言,与主流的疏离给他带来了一种与众不同的视角。对他而言,判定问题的计算就是形式系统的推演证明,而形式系统的相互包含是一个非常自然的问题。比如说定义自然数的皮亚诺公理体系,就是一种形式系统,而这个系统中的所有命题都能翻译到集合论的策梅洛-弗兰克(ZF)公理体系中,能用皮亚诺公理证明的数学命题,在翻译后都能在ZF中证明。可以说,ZF体系包含了皮亚诺公理体系。那么,给定两个不同的公理体系A和B,我们自然希望考察它们的包含关系,比如说B是否包含A。也就是说,我们希望知道,是否存在一种方法,能将A中的命题翻译到B中,并且希望翻译后,在A中能证明的命题在B中仍然能证明。

波斯特的另一个优势,就是他之前的研究已经涉及到这样一些具体的翻译问题,只不过用的术语不是翻译,而是归约。从一般的形式系统到正则形式A,再到正则形式B,再到一种非常特殊的推演规则,这些都是归约。在关于形式系统不完备性的研究中,波斯特早已自己构造过许多这样的归约。从特殊的归约到一般的“归约”这个概念,对于数学家来说,仅仅是一步之遥。

为了简洁起见,波斯特并没有使用他的正则形式的概念,而是将计算问题表达为一个个由自然数组成的集合。对于数理逻辑学家来说,无论是形式系统、判定问题还是自然数组成的集合,本质上并没有什么不同。形式系统的命题可以用字符串表达,所以可以化为自然数,判断某个命题是否能从公理推演出来,也就相当于判断对应的自然数是否属于可推演命题对应的集合。而一个集合对应的判定问题,就是某个输入作为自然数是否处于这个集合中,所以,指定一个由自然数组成的集合,与指定一个判定问题是等价的。在这个框架下,归约的定义更方便更直观。

归约也有很多不同的种类,它们有强有弱。波斯特在研究形式系统是用到的归约,也就是上面所说的“公理体系之间的翻译”,是其中能力比较弱的一种,又叫“多一归约”(many-one reduction)。而最强的图灵归约在判断A中命题的正误时,可以在可计算的范围内任意生成B中的命题并得到解答,再从这些任意多的解答中提取结论。能获取的解答数目多了,自然也能解决更多问题,也就是说能力越强。

图灵归约是波斯特研究的最终目标,但它的能力太强,很难研究。所以在1944年的这篇论文中,波斯特主要研究的是更简单的多一归约和另一种稍微更强大的“真值表归约”。他证明了,在这两种归约方法定义的难度概念下,存在这样的计算问题,它们是不可计算的,但却比停机问题更容易。也就是说,如果按照这些归约定义的难度来排序,在可计算问题与停机问题之间,存在无数的“中间层级”。从可计算问题到停机问题迈出的这一步,实际上跨过了无数的层级。

波斯特在论文的结尾猜想,对于更强大的图灵归约,这样的“中间层级”也存在,不仅如此,其中有无数个中间层级是计算可枚举的。这并不显然,因为越强大的归约,越能填补不同问题之间难度的差距。比如说,多一归约认为问题A比问题B要难,但这可能是因为它本身太弱,如果换用图灵归约,也许就能通过多问几个问题得出答案。波斯特关于计算可枚举的“中间层级”是否存在的这个问题,又被称为波斯特问题。

波斯特的这篇论文的新观点和新结果最终引起了美国逻辑学家的注意,他终于获得了作为一个数理逻辑学家应有的赞赏。也许,他并不需要什么救济。

在那场演讲之后,在美国数学协会的聚会上,有个人叫住了波斯特。这个人叫克林,也是一位数理逻辑学家(一些读者可能还记得提出λ演算的丘奇就是他的博士导师)。他对波斯特说,有些东西想让他看看,并将波斯特邀请到了他的家中。

这就是波斯特与克林伟大合作的开端。

来自Wikipedia

来自Wikipedia

计算的极限(八):符号的框架

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

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

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

计算无处不在。

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

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

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

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


如果说图灵的经历只是时运不济,那么埃米尔·波斯特(Emil Post)的遭遇只能说是造化弄人。


梦想与现实

波斯特在1897年出生于当时属于俄罗斯帝国的奥古斯图夫(今属波兰),年幼时就随同家人移民到了美国。与你我之中的许多人一样,波斯特自幼就迷恋着璀璨的星空,一心希望长大后能当个天文学家,研究那些遥不可及的星体,揭露自然之伟力塑造这些巨大结构的法则。这对于一位少年来说,无疑是个珍贵的梦想。

拍摄者:P. Calcidese–Fondazione C. Fillietroz, ONLUS/ESO

拍摄者:P. Calcidese–Fondazione C. Fillietroz, ONLUS/ESO

但13岁时的一场意外,夺去了他的左臂。

在信息技术发达的今天,天文学家的工作几乎完全在计算机上进行,而各种各样的辅助设施更是让几乎所有人都能便利地使用计算机。但在波斯特的年代,天文观测仍然处于完全机械化的时期,许多观测任务都需要天文学家亲力亲为,曝光、校准、调整,这并不是按几个按钮就能完成的工作,需要捋起袖子动手做。只有一只手,连调整镜筒方向都做不到。尽管残疾的大天文学家并非没有先例,比如说开普勒,但这是例外,并非常态。

年少的波斯特为此曾写信到哈佛天文台与美国海军天文台。面对少年的来信,两个天文台给出了不同的回复。哈佛天文台的回复像是一种鼓励和安慰:“没有什么理由会阻止你在天文学中出人头地”;而美国海军天文台的回复更加务实直白:“依我之见,失去左臂是你成为职业天文学家的一大障碍。在这个天文台,用仪器观测时必须用到双手”。两种意见都非常合乎情理:少年的梦想应该呵护,但冰冷的现实也不能忽视。选择的权利,仍然掌握在波斯特的手心上。

他选择了放弃。

梦想是可贵的,更是昂贵的,尤其在波斯特的时代。放弃未必是错误的选择,关键是放弃之后如何选择。波斯特选择了数学,并且走了下去,走得很远。


初试身手

在完成高中与大学学业之后,在1917年,波斯特成为了哥伦比亚大学的一名博士生,跟随卡修斯·凯泽(Cassius Keyser)学习。这位凯泽也有过人之处,在当时美国数学界普遍偏向实用的氛围下,他却十分关心欧洲大陆关于数理逻辑的研究,这样的人在当时并不多。这大概因为凯泽自身非常关心哲学,甚至在哲学上也有不少的著作,于是他对于数学哲学与数理逻辑也是爱屋及乌。

凯泽对数理逻辑的热忱对波斯特影响很大,而那种更广泛的对数学与哲学的热情,可以在波斯特的师兄埃里克·贝尔(Eric Bell)身上看到。贝尔在数学研究上的贡献不大不小,在组合数学中,含有n个元素的集合拆分成子集的方法数被称为贝尔数,也有对应的贝尔多项式,这也许就是他最为人知的数学贡献了。但贝尔对数学的贡献远远超出了他的研究。他写了一本叫《Men of Mathematics》(中文译本叫《数学精英》或者《数学大师》)的书,讲述了众多知名数学家的故事。虽然这本书的描写过分夸张,而且过于关注数学家生活中的戏剧性,因而常常为数学家与数学史研究者所诟病,但这种写法同时也吸引了一代又一代的数学爱好者,有许多著名的数学家在少年时都深受这本书的影响。贝尔给少年带来了数学的梦想,这项贡献甚至比他的研究更重要。

出处:http://angelustenebrae.livejournal.com/15908.html

出处:http://angelustenebrae.livejournal.com/15908.html

在凯泽的指引下,波斯特在哥伦比亚大学简直如鱼得水。凯泽开设了一门研讨班,专门研究当时刚刚出版没几年的《数学原理》。这是一套厚厚的三卷本,但对于作者罗素(Bertrand Russell)与怀特黑德(Alfred North Whitehead)的宏大目标——将数学建立在毫无疑义的符号推演的基础上——来说,三卷实在有点薄。证据就是,他们等到第二卷,才证明了“1+1=2”,并且加上了评注:“以上命题有时会有用”(The above proposition is occasionally useful)。

这本数理逻辑的开山之作,不仅第一次展现了数学家追求确切无误的决心,也是类型论的首次登场。类型论不单是避免矛盾的工具,它触碰了计算的某些本质。那将是一个更颠覆常识的故事,但我们暂且按下不表。波斯特于是也开始研究《数学原理》的内容,作为博士论文的题目。

可以说,在数理逻辑这条道路上,波斯特一开始几乎是在独自前行。导师凯泽虽然对数理逻辑很有兴趣,但算是半路出家,除此之外,《数学原理》就是波斯特唯一的参照物。可以说,波斯特与丘奇一样,是美国土生土长的数理逻辑学家,他甚至比丘奇早几年进入这个领域,算是前辈。

三年如白驹过隙,但足以让波斯特深入当时数理逻辑的前沿。在他的博士论文中,他证明了《数学原理》中的命题演算是完备的,也就是说,在该系统内,真等价于可证明。作为逻辑系统,命题演算从属于一阶逻辑,所以波斯特的结果可以说是十年后的哥德尔完备性定理的前奏。

但波斯特的博士论文,价值远不止于此。

在《数学原理》中,罗素和怀特黑德殚精竭力建立了一个逻辑体系,这是他们的智力结晶,他们相信这是唯一的体系,所有其他数学都能奠基于此。但作为局外人的波斯特却看不到这种“唯一性”到底从何而来。在他眼中,逻辑体系可以是任意的,不一定要符合什么规则,可以拥有或多或少的代表不同意义的符号,甚至连“真”与“假”的二元对立都可以放弃。在论文的后半段,他研究了这一类“任意的”命题演算甚至是多值逻辑的一致性与完备性。虽然在现代,这种逻辑的自由观念已经深深融入了数理逻辑研究的精神,但在当时,这种想法可以说是开风气之先。

也许是因为这篇高质量的博士论文,刚毕业的波斯特获得了普林斯顿的垂青。图灵申请了两次才成功的同一份奖学金,波斯特甫一毕业就拿到了手。

接下来这博士后的一年硕果累累。


符号的框架

到了普林斯顿,波斯特继续研究一般的逻辑体系。追寻着希尔伯特的想法,他问了相同的问题:对于任意的逻辑体系,我们能否判定某个命题是否这个体系的定理呢?

要回答这个问题,就要先做定义:什么是“逻辑体系”?

出处:http://www.cs.nott.ac.uk/~txa/g53cfr/

出处:http://www.cs.nott.ac.uk/~txa/g53cfr/

要知道,逻辑体系种类繁多,从弗雷格电路图一般的“概念文字”,到罗素和怀特黑德的《数学原理》中略显奇异的近代逻辑符号,再到现代一般使用的一阶逻辑,又到更复杂的模态逻辑与线性逻辑,甚至到现代如雨后春笋层出不穷的新逻辑体系,它们无论是符号、意义还是表达范围都千奇百怪,要找到一个能囊括过去、现在甚至未来出现的定义,这无疑是个令人挠头的工作。如果考虑到波斯特当年见过的逻辑体系并没有现在那么多种多样,要去定义“逻辑体系”这个概念,无疑难上加难。

但数学工作者都习惯了推广各种概念,波斯特也不例外。他的任务,就是从一阶逻辑这个范本出发,找到一种能涵盖一切“逻辑体系”的定义。那么,一个自然的问题就是,当我们在用逻辑体系做推理或者证明的时候,我们到底在干什么?

我们先从比较简单的系统开始。所谓“一阶直觉主义命题演算”,可能是最简单而有实际意义的逻辑系统。虽然名字的长度和内容都很吓人,但实际上它非常简单。除了表示不同命题的变量之外,它只有三个符号(合取号\land  ,析取号 \lor  与蕴涵号\to  ,算上括号就是五个),加上仅仅8条“不言自明”的公理,还有单单一条推理规则:肯定前件规则(Modus ponens)。那些公理并不是什么复杂的东西,不过是将合取(家鸡不是野生动物而且炸鸡很好吃)、析取(我想吃云吞或者面条,当然云吞面也可以)和蕴涵(要是我今晚叫外卖,那么晚上就不用洗碗了)这些日常生活中的概念,在符号世界中的表达而已,实际上的确不言自明。而“肯定前件规则”虽然名字同样吓人,但意思很简单:如果我们能推演出命题P  与命题P \to Q  (读作“P推出Q”或者“P蕴涵Q”),那么我们就能据此推演出命题Q  。这也是显然的:要是我今晚叫外卖,那么晚上就不用洗碗;我今晚的确叫了外卖(是云吞面);从此可以推出,我今晚显然不用洗碗了。可以说,“一阶直觉主义希尔伯特命题演算”这个逻辑系统,其实就是一些日常的概念和规则的一种完全符号化、形式化的表达。

那么,当我们在使用这个逻辑体系进行数学推理的时候,我们在做什么?如果我们用这个体系证明了某个命题,这个“证明”到底又是什么?

正如初中几何证明一样,任何证明都要先列出它使用的公理,也就是说,它默认了什么是“真”的命题。然后,我们知道在肯定前件规则中,如果P  P \to Q  都是真的,那么Q也是真的,所以我们可以推出Q。那么,只要从公理出发,不停地应用这个规则,因为我们的出发点都是“真命题”,我们通过规则得到的命题也必然是真命题。从真理走向真理,这就是证明,难道不是吗?

的确,一个证明,就是一个从真理走向真理的过程,但这建立于符号的意义之上。如果我们不知道这些符号的意义的话,一个证明又是什么?因为我们已经知道一阶直觉主义命题演算实际上只是日常生活的形式化,所以我们能堂堂正正地说那些公理都是真的。但对于一个从来不知道这些符号的意义的人,甚至是几分钟前的我们来说,这些符号、命题、规则又是什么?当我们遇到一个全新的逻辑体系的时候,我们不知道新体系中的符号、命题、规则到底有着什么意义,这时我们又应该如何看待新体系中的一个证明呢?

不同的逻辑体系有着不同的符号,即使是相同的符号,在不同的体系中也不一定有着相同的意义。如果我们希望找到一个能囊括所有逻辑体系的定义,那么,这个定义中显然不能包含“意义”。但一个剥除了意义的形式体系到底是什么?当“P  P \to Q  可以推演出Q  ”的这个规则剥除了它的意义,剩下的又是什么?一个证明,如果剥去它“证明某项真的陈述”的这一重意义,它又是什么?

但如果将形式证明的意义剥除,剩下的不就仅仅是一些无意义的、盲目的符号推演么?当我们看到P  P \to Q  ,我们就能写出Q  ,仅此而已。本来这个逻辑体系是为了将日常生活中的推理形式化、精确化而存在的,现在要将“日常生活推理”这一意义抽去,只剩下符号搭成的框架,这不是舍本逐末吗?

的确,符号搭成的框架本身没有任何意义。但也正因如此,它可以承载任何意义。已有的逻辑体系蕴含着形形色色的意义,未有的逻辑体系可能蕴含着我们现在无法想象的意义。它们唯一的共同点,就是那个符号搭成的框架。公理就是作为起点的,由符号组成的公式;推理规则就是将一些符号串写成另一些符号串的机械规则;证明就是从公理出发,通过推理规则的不断改写,得到一个新公式的过程。如果有P  P \to Q  ,就写出Q  ,丝毫不需要思考意义。而在另外一个逻辑体系,如果有P  P \to Q  ,就写出Q \to P  ,这又有何不可?

这就是波斯特的答案:逻辑体系,不过是由一些符号、变量、起始符号串(公理)以及将这些符号串不断改写的规则(推理规则)。它们没有意义,但可以承载任何意义。通过对它们的研究,即使我们完全不知道某个逻辑体系的意义,也能通过对这些符号以及变换的研究,来得到关于这个逻辑体系的一些结论,比如它的一致性(是否存在一些不能写出的符号串),还有它的完备性(是否存在一个符号串,将它添加到起始符号串中就能改写出所有符号串)。只要研究这种完全形式化的符号系统,就能得出关于最广泛、最一般的逻辑体系的结论,无论它们的意义是什么。

作者David Rosenthal,来自http://facpub.stjohns.edu/~rosenthd/

作者David Rosenthal,来自http://facpub.stjohns.edu/~rosenthd/


形式的迷宫

波斯特这么想了,也这么做了。他将这种符号改写的规则构成的系统称为“规范形式A”(canonical form A,涵盖了现代所谓的“字符串重写系统”),然后证明了所有取规范形式A的系统都能写成另一种包含更多约束的“规范形式B”。规范形式B允许的改写规则更简单也更弱,但它的“表达能力”与更强大的规范形式A相同。然后,波斯特证明了《数学原理》中的逻辑系统,实际上也能用这个弱得多的规范形式B表达出来,是规范形式B的一个特例。这意味着,做数学需要的推理规则,实际上要比罗素与怀特黑德想象的要简单得多。

虽然规范形式B很简单,但波斯特觉得它还不够简单,因为它仍然需要有无穷个表示变量的符号。他又定义了另一个“规范形式C”,它只需要有限个符号,但却能表达出规范形式B所表达的一切逻辑体系。在规范形式C中,波斯特又定义了所谓“正则形式”,在正则形式表达的逻辑体系中,只允许一种改写规则:如果符号串的开头是某一串特定的符号,那么将这些符号删去,然后在末尾添加另外一串符号。同样,所有能用规范形式C表达的逻辑体系,都能转化为正则形式。

我们来看一个正则形式的例子。符号有三个:a和b;起始符号串只有一条:“bb”;而规则仅仅有三条:

(1) a$ -> $a
(2) b$ -> $aba
(3) b$ -> $b

这里,$的意思是剩下的符号串,比如说a$ -> $a,就是说如果开头读到一个a,那么就去掉这个a,然后在符号串末尾加上一个a。如果开头是b,我们可以选择应用第二或者第三条规则,去掉b,然后续上aba或者b。很简单吧?

那么,通过这些规则,从公理开始,能改写出来的字符串又有哪些呢?

我们来看一个改写的例子:

bb -> baba (2)
-> abaaba (2)
-> baabaa (1)
-> aabaab (3)
-> abaaba (1)
-> baabaa (1)
-> aabaaaba (2)
-> abaaabaa (1)

也许你已经察觉到了这个简单的规律。我们注意到,每一条规则左右两边b的数量是相同的,因为公理只有“bb”,所以所有改写得到的符号串必然有两个符号b,它们将其余的a分成了扇段。再仔细观察上面的例子,容易发现两头a的数目加起来恰好是中间一段的a的数目。不难证明,所有可以写出来的符号串,恰好是形如a^m b a^{m+n} b a^{n}  的符号串,其中m与n都是正整数。或者可以说,这个形式系统表达了正整数的加法。很简单吧?

正则形式也许已经简单得不能再简单了,波斯特认为,这么简单的系统,要判断某个符号串是否能够写出来,看来也不是什么难事吧?但不要忘记,《数学原理》这本三卷本的巨著,它使用的逻辑体系也能归化为正则形式。就像图灵机一样,正则形式看似简单,但能力惊人。

波斯特甚至猜测,一切能用一个本质上有限的系统生成的符号串组成的集合,必定可以用一个正则形式体系生成;也就是说,正则形式体系涵盖了一切有限的符号生成系统,无论是已知的、未知的、过去的、未来的。这个猜测被称为“波斯特论题”(Post’s thesis)。这是一个大胆的猜测,要知道,数学家日常使用的逻辑,也只是一种有限的符号生成系统,只不过我们将这个系统生成的符号串称为“定理”,并且能给它们赋予“真”的意义而已。波斯特的猜测,实际上说的是正则形式体系覆盖了所有可能的数学推理体系。

这么大胆的猜测,难道不会隐藏着显而易见的问题吗?

我们可以假定所有考虑的正则形式系统都只有两个符号,因为通过两个符号的二进制组合我们可以表达别的符号。因为正则形式体系非常简单,我们能很容易地用自然数给它们编号,从1、2到无穷。给定某个编号,我们能机械地写出对应的正则形式体系。考虑一个集合D,它的元素是这样的符号串:用二进制的眼光来看,这个符号串对应一个自然数n,而编号为n的正则形式系统无法写出这个符号串。那么,是否存在一个正则形式体系T,它能写出的符号串的集合恰好就是D呢?

如果这样的T存在的话,它必定对应着一个编号n,而这个编号对应一个符号串S。S不可能属于D,否则按照D的定义,当S属于D时,对应的正则形式体系T必定无法生成S,而T应该写出D中的所有符号串,包括S,矛盾;而S又一定属于D,否则按照D的定义,当S不属于D时,T必定可以写出S,但T不应该写出D以外的任何符号串,包括S,矛盾。无论S是否属于D,引出的都是矛盾。于是,错误必定出现在一开始的假定上,也就是说,必然不存在这样的T,它恰好生成集合D。

来自Wikipedia

来自Wikipedia

记忆力好的读者一定察觉到了,这就是康托尔的对角线法,与图灵所用的如出一辙!

但如果对于任意的正则形式体系T与字符串S,我们都能证明T能否写出S的话,那么集合D必定可以用一个有限的系统生成,我们只需要针对所有自然数n,考察编号n的正则形式体系是否能写出n对应的字符串,这可以在有限的体系与有限的时间内做到。这又是一对矛盾。我们的论证中,必定有什么地方出了问题。

我们回过头来看看,这个矛盾用到了什么假设。仔细察看之后,我们能找到两个没有证明的假设:

假设一:一切本质上有限的系统生成的符号串集合,必定能用某个正则形式体系生成。

假设二:对于任意的正则形式体系T与符号串S,我们都能在有限时间内知道T能否写出S。

假设一是波斯特论题,假设二则源于因为我们认为正则形式非常简单。两个假设看上去都很有道理,假设一甚至更大胆一些。但如果将这两个假设放在一起,则不可避免地会导致矛盾。数学是不应该有矛盾的,二者必须择其一,甚至两者都可能是错的。那么,应该先放弃哪一个呢?

正则形式系统看上去是这么简单,毕竟眼见为实,要证明某个符号串能否写出来,似乎不是什么难事。但“本质上有限的系统”,涵盖的范围非常广阔,而正则形式看上去又那么简单,谁知道会不会有别的什么系统能做到正则形式做不到的事情呢?保险的做法,大概是放弃假设一,保留假设二。

但波斯特却反其道而行之。在此前对另一种同样简单的符号重写系统——所谓的“标记系统”(tag system)——的研究中,他发现对于很多看上去简单的问题,要找到答案不是那么容易的事。他猜想对于正则形式系统,也许我们原本认为的“简单问题”,实际上非常难解决。这些形式系统,并不像草原那样一览无遗,而更像是由形式操作构成的迷宫。他认为,实际上要放弃的应该是假设二,要保留的反而是他的假设一。

事实证明,他的选择是正确的。如果你对放弃假设二还有疑问的话,不妨试试以下的正则形式系统:

aa$ -> $bc
ab$ -> $bc
bc$ -> $a
ca$ -> $aaa
cb$ -> $aaa

如果你能找到一个起始符号串,使得这个形式系统可以写出无穷个不同的符号串的话,我可以保证,你的大名将会留在数学史上。

但放弃假设二也就相当于断言:存在某个正则形式体系T与符号串S,我们无法在有限时间内证明T能否写出S。可以说,这就是正则形式体系中的某种哥德尔不完备性定理:有些东西,我们不可能知道。

这是一个伟大的成就,波斯特在哥德尔之前10年就预见到了相似的结论。如果说哥德尔开创了一个新时代,那么波斯特当时则远远超越了时代。

可惜这个成就,于他而言过于沉重。

The Scream