Hero Image
周游世界游戏与哈密顿回路

1856 年,仍在研究非交换代数的哈密顿发明了二十面体演算:三个符号 $\iota$、$\kappa$ 和 $\lambda$,服从规则 $$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$今天我们会说,它们生成了正二十面体(有二十个三角形面的立体)的旋转群。1857 年,哈密顿在英国科学促进会于都柏林举行的会议上介绍了这种演算,并注意到它描述的是沿正十二面体(有十二个五边形面和二十个顶点的立体)的棱行走的路径。 谜题 为了让这个想法流行起来,哈密顿把十二面体压平画在一块板上,在二十个顶点处开了孔,每个孔标上一个城市的名字,另配二十个编了号的木钉。挑战是:从一个城市出发,只沿着棱走,把其他每个城市恰好访问一次,再回到出发点。1859 年,他以 25 英镑把版权卖给了伦敦的游戏制造商约翰·贾克斯父子公司。这个游戏以“周游世界游戏”(The Icosian Game)的名字出售,还有一个叫“旅行者的十二面体”的袖珍版,但在商业上失败了:只要有点耐心,基本的挑战几分钟就能解决。 圣保罗大学数学与统计研究所 Matemateca 收藏的周游世界游戏复制品。编号的木钉标出了经过二十个顶点的顺序。Estes Objethos Atelier,Alisson Ricardo 摄 · Wikimedia Commons · CC BY-SA 4.0 试一试。字母是哈密顿用来给城市命名的辅音字母: 请启用 JavaScript 以使用这个交互图形。完整的推理见正文。 欧拉解决了,哈密顿没有 每个顶点恰好经过一次再回到起点的路线,今天称为哈密顿回路。这个问题看起来像是柯尼斯堡七桥问题的表亲,在那个问题里欧拉想把每条边恰好走一次。但两者非常不同。对于边,欧拉在 1736 年给出了一个简单的判据:只要看每个顶点连出多少条边。对于顶点,没有人知道简单的判据。1972 年,理查德·卡普把哈密顿回路问题列入他的 NP 完全问题清单:谁能为它找到一个快速方法,谁就有了解决成千上万其他难题的快速方法,还能从克莱研究所赢得一百万美元。 它最著名的亲戚是旅行商问题:在一张地图的所有哈密顿回路中,哪一条最短?它出现在送货路线、电路板钻孔和 DNA 测序中。 柯克曼抢先了一步 1855 年,比哈密顿早两年,英国牧师兼数学家托马斯·柯克曼就已经问过:哪些多面体存在一条经过每个顶点恰好一次的回路?他还给出了一个不可能做到的例子。名字却归了哈密顿,他名气更大,还有一个在售的游戏。 练习:数一数棱在正十二面体中,20 个顶点中的每一个都连着 3 条棱。共有多少条棱?一条哈密顿回路用了其中多少条? 按顶点数,共有 $20 \times 3 = 60$ 个棱端,每条棱有两个端点:$60 / 2 = 30$ 条棱。一条哈密顿回路经过 20 个顶点再回来,用了 20 条棱;其余 10 条没有用到。

Hero Image
自我复制的自动机

在生命的最后几年,冯·诺依曼问了自己一个听起来像哲学的问题:机器能造出自己的副本吗?困难在于逻辑。要造出副本,机器需要一份关于自己的描述;可描述又是机器的一部分,于是它还得描述这份描述,如此下去,陷入无穷倒退。 描述、构造器和复制器 冯·诺依曼在 1948 年起的讲座中提出的出路,是把三个部分分开: 构造器 $A$,读取任意机器 $X$ 的描述 $D(X)$,并造出 $X$; 复制器 $B$,复制任何描述,而不需要理解它; 控制器 $C$,把两者连接起来。 现在把机器 $A + B + C$ 自己的描述 $D(A + B + C)$ 交给它。构造器读取描述,造出一台新的机器 $A + B + C$;复制器把描述复制一份,交给新机器。结果是一个完整的副本,带着它自己的描述。倒退之所以终止,是因为描述被以两种方式使用:一次作为要执行的指令,一次作为不加阅读就复制的文本。 在 DNA 之前 1953 年,詹姆斯·沃森和弗朗西斯·克里克描述了 DNA 的双螺旋。细胞所做的恰恰是冯·诺依曼预言的事:DNA 被核糖体读取以制造蛋白质(构造器),在细胞分裂时又被逐个字母地复制而不加解释(复制器)。冯·诺依曼通过思考机器得出了复制的逻辑结构,而那时生物学还没有揭示生命是怎样实现它的。 格子网格 为了让这个想法变得严格,冯·诺依曼需要一个可以在其中搭建机器的简单“宇宙”。在乌拉姆的建议下,他使用了一个由小方格组成的无穷网格,每个方格处于 29 种状态之一,所有方格在每一步同时根据四个邻居的状态而改变。他在这个网格中设计了一个巨大的构型,包含数量极其庞大的格子,能够读取一条带子、造出自己的副本并复制这条带子。这项工作在他去世时尚未完成,由他的合作者阿瑟·伯克斯补全,并于 1966 年以《自我复制自动机理论》为题出版。 斯坦尼斯瓦夫·乌拉姆在洛斯阿拉莫斯的证件。正是乌拉姆向冯·诺依曼建议用格子网格作为机器的宇宙。Los Alamos National Laboratory · Wikimedia Commons · 公有领域 这样的网格今天称为元胞自动机。1970 年,英国人约翰·康威发明了一个只有两种状态(活和死)的元胞自动机,规则只有一行:有 2 个或 3 个活邻居(算上对角线)的活格存活;恰好有 3 个活邻居的死格诞生;其余的死亡或保持死亡。康威称之为生命游戏,它丰富到在其中也能搭建计算机和自我复制的机器。 练习:闪烁器在生命游戏中,横排的三个活格构成“闪烁器”。证明下一步它们会变成竖排。 中间的格子有 2 个活邻居,存活。两端的格子只有 1 个活邻居,死亡。中间格子正上方和正下方的两个格子恰好有 3 个活邻居(横排的三个),诞生。结果:竖排的三个。同样的推理表明,再下一步它又变回横排,这个图案永远闪烁下去。

Hero Image
约翰·冯·诺依曼的遗产

我有时会想,像冯·诺依曼这样的大脑,是否意味着一个比人类更高级的物种。 — 诺贝尔物理学奖得主汉斯·贝特,据诺曼·麦克雷转述 这一系列中的八篇文章只展示了冯·诺依曼所做工作的一部分。完整的清单装满了六卷文集,几乎遍及他那个时代数学的每一个分支。 纯数学 算子代数。 1929 年到 1943 年间,他部分与弗朗西斯·默里合作,创立了今天称为冯·诺依曼代数的算子代数理论,这是分析学和数学物理中最活跃的领域之一。 遍历定理。 1932 年,他证明了一个版本的定理,为统计物理的一条原理提供了依据:一个量对时间的平均等于对所有可能状态的平均。 希尔伯特第五问题。 1933 年,他解决了希尔伯特在 1900 年提出的问题之一的紧致情形,这个问题问的是连续群何时自动是“光滑”的。 经济、天气与战略 经济增长。 在一篇 1937 年发表、几年前已在普林斯顿的一个研讨会上报告过的论文中,他构建了一个扩张经济的模型,并用与极小极大相同的数学证明了均衡的存在。这是数理经济学的奠基文献之一。 天气预报。 1950 年,由朱尔·查尼领导、冯·诺依曼参与的小组在 ENIAC 上做出了第一次数值天气预报:24 小时的预报花了大约 24 小时来计算。今天预报天气和气候的模型都是那次实验的后代。 核战略。 冷战中,博弈论被用来思考军备竞赛,冯·诺依曼参与了洲际导弹的规划。与这种推理相联系的“相互确保摧毁”一语,至今仍概括着一个时代。 “奇点”这个词 1958 年,斯坦尼斯瓦夫·乌拉姆写了一篇纪念他朋友的文章。文中他回忆起一次谈话,谈到技术进步不断加速,似乎正在接近“人类历史上某个本质性的奇点,越过它,我们所知的人类事务就无法继续下去”。这是这个词在这一意义上有记录的首次使用,几十年后它成了关于人工智能讨论的主题。 约翰·冯·诺依曼在洛斯阿拉莫斯的证件照,摄于 1940 年代。Los Alamos National Laboratory · Wikimedia Commons · 须署名 怎样评价他 冯·诺依曼既是本世纪最抽象的数学家之一,又是最深入参与科学军事应用的人之一,这两者在他的故事里密不可分。他帮助创造的计算机是为计算炸弹而诞生的,很快又转去计算天气、市场和蛋白质。博弈论诞生于一篇关于室内游戏的论文,最后进入了核战略手册和手机频段的拍卖。 他留下的启示,是一位不尊重学科边界的数学家的启示。他把物理学、经济学和计算机都当作数学可以派上用场的地方,而数学几乎总是派上了用场。 IAS 的存储器能装下多少 1952 年的高等研究院计算机有一个由 1024 个“字”组成的存储器,每个字 40 位二进制数字,存放在阴极射线管中。也就是 $1024 \times 40 = 40\,960$ 比特,或 $5\,120$ 字节:比这一段文字在你手机上占的空间还少。就是用这样的存储器,运行了氢弹的计算、天气预报和生物进化的模拟。 练习:IAS 的存储器一张 1 GB($10^9$ 字节)的存储卡能装下多少个 IAS 存储器? 每个 IAS 存储器有 $5\,120$ 字节。$\frac{10^9}{5\,120} \approx 195\,000$。今天的一张小卡片能装下冯·诺依曼那台计算机近二十万倍的存储器。

Hero Image
艾伦·图灵的遗产

图灵相信机器会思考。图灵和男人睡觉。所以机器不会思考。 — 艾伦·图灵,致诺曼·劳特利奇的信(1952) 这个苦涩的三段论,是图灵在被定罪后不久写给一位朋友的,它概括了他的一生:一个用逻辑思考的人,被不理解他的人审判。然而,他留下的成果无处不在。 在计算机科学中 图灵机仍然是“计算”的正式定义。当计算机科学家说一个问题“没有算法”时,意思是没有图灵机能解决它;当他们说一个问题“难”时,数的是图灵机需要走多少步。 从这种计数中产生了这个领域最著名的问题——P 与 NP:每个解很容易验证的问题,是否也都很容易找到解?拼一幅拼图很难;检查一幅拼好的拼图很容易。没有人知道这种差别是真实存在的,还是只是我们不够聪明。克雷研究所悬赏一百万美元,奖给回答这个问题的人。 自 1966 年起,美国计算机协会每年颁发图灵奖,它被视为计算机领域的诺贝尔奖。 在密码学和统计学中 对恩尼格玛的战争表明,一种密码的安全不在于密钥的数量,而在于没有能一下子排除大部分密钥的缺陷。现代密码学就诞生于这个教训。而分班经由 I. J. 古德,帮助把贝叶斯统计带回了科学的中心。 在生物学和人工智能中 形态发生的方程是一整个领域——图案的数学生物学——的基础。而模仿游戏在机器已经能够对话的今天,仍是任何关于机器能否思考的讨论的参照。 曼彻斯特萨克维尔公园里的图灵雕像,2001 年揭幕。他坐在长椅上,手里拿着一个苹果。David Dixon · Wikimedia Commons · CC BY-SA 2.0 补偿 几十年里,图灵在战争中的工作是国家机密,他的定罪则是不被提起的话题。1983 年,数学家安德鲁·霍奇斯写的传记出版,情况开始改变。随后有了: 2001 年,在大学旁边的一座公园里,竖起了曼彻斯特的雕像; 2009 年,英国政府的道歉; 2013 年的王室赦免,以及 2017 年赦免其他被定罪者的法律; 印有他头像的 50 英镑纸币,于 2021 年 6 月 23 日——他的生日——发行。 要记住的 1936 年:图灵机定义了什么是计算,通用机预示了存储程序计算机。 1936 年:停机问题表明有些问题没有机器能回答,可计算数表明几乎每个实数都遥不可及。 1939–1945 年:恩尼格玛的计数与缺陷、炸弹机,以及带着分班的班伯里法。 1950 年:模仿游戏用一个测试取代了“机器会思考吗?”这个问题。 1952 年:形态发生解释了扩散如何产生图案。 练习:验证很容易有人说 $8633=89\cdot97$。验证它要花多少功夫?如果没有提示,要找到这两个因数又要花多少功夫? 验证只需一次乘法:$89\cdot97=89\cdot100-89\cdot3=8900-267=8633$。寻找则要试除到 $\sqrt{8633}\approx93$ 为止:从 2 到 89 一共 24 个素数,只有最后一个成功。对于几百位长的数,验证仍然瞬间完成,寻找却变得不可行。互联网的密码学就建立在这种不对称上。

Hero Image
写给机器的记号:由计算机核验的证明

两千年来,数学证明一直是写给人读的文本。它可以跳过“显然”的步骤,可以借助图形,可以使用群体内部的约定。其余的由读者补全。近五十年来,出现了一位什么都不补全的读者:计算机。 四种颜色 给任意一张地图着色,使相邻的国家颜色不同,需要几种颜色就够了?答案是四种,这一猜想于 1852 年提出,抵抗了一个多世纪。1976 年,伊利诺伊大学的肯尼斯·阿佩尔和沃尔夫冈·哈肯证明了它:他们把问题化为将近两千种情形,由计算机逐一检验,用了一千多个小时的机时。 一张用四种颜色着色的地图,任何两个相邻的区域颜色都不相同。Inductiveload · 维基共享资源 · CC BY-SA 3.0 学界产生了分歧。一个没有人能够完整读完的证明,还算是证明吗?支持者提醒说,许多很长的证明也没有人完整读过;批评者说,程序可能有错误。2005 年,法国人乔治·贡蒂耶把整个证明,包括计算机的部分,写进了一个名为 Coq 的证明助手,它从公理出发检验每一个逻辑步骤。疑问换了地方:不再是“程序对吗?”,而是“检验器对吗?”——那是一个小得多、也容易审查得多的程序。 开普勒猜想 1611 年,开普勒断言,堆放橙子最密的方式就是水果摊上的金字塔。1998 年,美国人托马斯·黑尔斯宣布了一个证明,它把几百页的论证与大量计算机计算结合在一起。一组审稿人工作了四年,宣布他们对其正确性有“99% 的把握”。黑尔斯不满足于那 1%,启动了 Flyspeck 项目,用形式语言写出整个证明。2014 年,在几十位合作者的参与下,项目完成:机器检验了每一步。 Lean 如今数学家用得最多的证明助手是 Lean,由巴西人莱昂纳多·德·莫拉于 2013 年在微软研究院创造。围绕它形成了 mathlib,一个集体编写的库,收录了数十万条形式化的定理,作者有数百人。2020 年,德国菲尔兹奖得主彼得·舒尔茨向学界发起挑战,请大家把他的一个结果形式化,因为他自己也不确定是否核对过所有细节。“液态张量实验”(Liquid Tensor Experiment)于 2022 年完成:结果是对的,而且形式化过程还发现了证明中可以简化的地方。 Lean 的一行代码是这样的: theorem soma_comuta (a b : ℕ) : a + b = b + a := Nat.add_comm a b “对任意自然数 $a$ 和 $b$,$a + b = b + a$,证明就是库中的交换律定理。”什么都不省略:每个字母的类型,每一步的出处。这是把第7章的线性书写推向了极端,是把第4章中用文字写的证明译成了一种机器能够检验的语法。 改变群体的记号 形式化正在改变工作方式。像英国人凯文·巴扎德在 2024 年发起的费马大定理形式化这样的项目,聚集了几十位从未谋面的合作者,每人形式化一个引理,并确信各个部分能拼合在一起,因为接缝由机器来检验。记号再一次决定了谁能参与、怎样参与。

Hero Image
作为思维工具的记号:艾弗森

1962 年,曾在哈佛任教、当时在 IBM 工作的加拿大人肯尼斯·艾弗森出版了一本名为《一种编程语言》(A Programming Language)的书。尽管书名如此,它其实是一本讲数学记号的书:一种简洁而精确地书写算法的方法,用新的符号表示对整个数列和数表的运算。几年后,IBM 自己把这套记号变成了计算机可以执行的语言,并以书名为它命名:APL。 下取整、上取整与括号 艾弗森的一些符号离开了 APL,进入了普通数学。最著名的是下取整与上取整这一对: $$\lfloor x \rfloor = \text{不大于 } x \text{ 的最大整数}, \qquad \lceil x \rceil = \text{不小于 } x \text{ 的最小整数}.$$在他之前,人们写 $[x]$ 或“$x$ 的整数部分”,而上取整没有符号。有了这两个符号,需要分几种情况的计算可以写在一行里:$1$ 到 $100$ 之间 $7$ 的倍数有 $\lfloor 100/7 \rfloor = 14$ 个。 另一个符号,艾弗森括号,把一个命题变成一个数: $$[P] = \begin{cases} 1, & P \text{ 为真}, \\ 0, & P \text{ 为假}. \end{cases}$$有了它,“数一数 $1$ 到 $n$ 之间的偶数”就成了一个普通的和 $\sum_{k=1}^{n} [k \text{ 是偶数}]$,而这个和可以用通常的规则来处理。高德纳在 1992 年一篇名为《关于记号的两则札记》(Two notes on notation)的文章中为这种括号辩护,并在与罗纳德·格雷厄姆、奥伦·帕塔什尼克合写的《具体数学》一书中通篇使用它。上一篇中的克罗内克 δ 只是一个特例:$\delta_{ij} = [i = j]$。