陈关荣 | 他自己的生命游戏结束了,留给后人的数学游戏长存

陈关荣 | 他自己的生命游戏结束了,留给后人的数学游戏长存

首页休闲益智帕特森的发明3更新时间:2024-04-16

作者 | 陈关荣

来源 | 华院计算

【一】

让我们从一个简单的游戏开始。

在一个很大(理论上无穷大)的围棋棋盘上,让黑子代表“生”而空格(称为白子)代表“死”。在棋盘上的任何9个格子组成的正方形区域里(见图1),对处于中心位置的黑子或白子来说,它上下左右和两对角线外的黑子(如果存在)都是它的邻居。游戏只有4条规则,在过程中的每一步都同时应用于棋盘上所有的黑子和白子上。规则如下:

(1)如果一个黑子只有1个或者没有黑子邻居的话,它在下一步就会死去,如图1(a) 所示。这操作表示该黑子在社会里太孤单了,它生存不下去。

(2)如果一个黑子有2个或者3个黑子邻居的话,它在下一步就继续生存,如图1(b) 的第一步所示。这操作表示该黑子有合适的社会环境,它可以生存下去。

(3)如果一个黑子有4个或者更多的黑子邻居的话,它在下一步也会死去,如图1(c) 的中心黑子(为了不影响这一说明,其它黑子和白子的变化暂不表示出来)。这操作表示该黑子所在的社会环境太拥挤了,它生存不下去。

(4)如果一个白子有恰好3个黑子邻居的话,它在下一步就会变成黑子,如图1(d) 所示。这操作表示该白子具有合适的社会环境,可以诞生或复活。

明白了这几条简单规则之后,你就可以开始玩这个游戏了。当然你会有个感觉,开始的时候放入多少个黑子以及怎样放置它们,这对于游戏如何一步一步地发展下去会有决定性的影响。例如,图1(d)中四个黑子处于稳定状态,它们永远都不会死去,也就是会“长生不老”永不消失,而其它初始放置方式(图1(a)、(b)、(c))则会让黑子在若干步之内全部死光。

你这个感觉是对的:游戏的初始条件(即放入多少个黑子以及怎样放置它们)的确很重要,它们会生成各式各样、丰富多彩的黑子组合斑图以及许多不同的最终结果。例如,图1(d) 就生成永远不变的斑图,称为“静物”(still life)。图2(a) 则生成周期-2的“振荡”(oscillator),而图2(b) 却生成一种会移动的周期“宇航船”(spaceship)。这种情形特别有趣,它在一步一步演变的过程中,初始的5个黑子不会减少也不会增多,但会频繁改变位置,像一艘不断变形的宇航船一直往右方和下方移动。第四步时,它变回初始状态了,不过整个斑图的位置向右方和下方各移动了一格。之后,它继续往前走,斑图的变化不断重复前面的移动过程。这是一艘会移动的周期-4振荡宇航船,称为“滑翔机”(glider),它将永远不停地向右下方滑翔前进。

图1 游戏4条规则

图2 “振荡”和“滑翔机”例子

你看,这个滑翔机会永远无休止地生存并移动下去,期间代表“生”和“死”的黑子和白子交替出没,整个族群在发展和演变过程中就像有“生命”一样,对吧?

事实上,这个游戏的规则是固定的,但初始条件(黑子的个数和位置)可以有许许多多的选择。因此,容易想象,会有各种各样的“最终趋于死亡”、“不同周期振荡”和“永远变动生存”等斑图。显然,这个游戏可以用来描绘一些社会生命现象,因此设计师把它叫做“生命游戏”(Game of Life)。

这个有趣生命游戏的设计师是数学家约翰·康威(John Horton Conway,1937年12月26日-2020年4月8日)。康威在开发这个有趣的生命游戏时是英国剑桥大学的一位数学讲师,时年33岁。这个生命游戏最初于1970年10月由科普作家马丁·加德纳(Martin Gardner,1914-2010)在《科学美国人》杂志的“数学游戏”专栏作了详细介绍,从此激发了学界和民间的广泛兴趣和热情关注。据说在那个生命游戏风靡世界的年代,全球有1/4 的电脑都在玩这个游戏。

【二】

在详细介绍本文的主人公康威之前,我们先来说说“生命游戏” 的前世今生。

康威并不是构思出这类具有深远哲学和数学意义的生命游戏的第一人。游戏的基本思想和概念要追溯到两位美国数学家:波兰裔的斯塔尼斯拉夫·烏拉姆(Stanislaw Ulam,1909-1984)和匈牙利裔的约翰·冯·诺伊曼(John von Neumann,1903-1957),他们在上世纪40–50年代为模拟生物细胞的自我复制提出了“元胞自动机理论”(Cellular Automata)的雏形。当年,由于没有大型高速的复杂计算能力,他们的构想并未受到学术界的重视。1970年,马丁·加德纳在科普杂志《科学美国人》介绍了康威的生命游戏之后,元胞自动机理论才受到了越来越广泛的关注。

图3 Stephen Wolfram(1959- )

在众多卓有成效的元胞自动机理论研究者中,特别值得提及的是计算机科学家史蒂芬·沃尔夫勒姆(Stephen Wolfram,1959- )。沃尔夫勒姆在1983年进入普林斯顿大学自然科学学院工作时,对元胞自动机发生了极大兴趣并致力于其研究。当年他使用计算机模拟对基本元胞自动机的类别进行了系统性的分析,对一维基本元胞自动机的256种规则所产生的模型进行了深入的研究,并用熵(entropy)的概念来描述其演化行为,还指出了第110号规则对应的元胞自动机具有图灵完备性(Turing completeness)。这里,图灵完备性指的是具有无限存储能力的通用编程语言,它可以通过一系列操作数据规则来模拟图灵数学逻辑机。沃尔夫勒姆发现,凡是可以通过编写程序去计算的,都可以用元胞自动机来实现。沃尔夫勒姆根据复杂性理论将元胞自动机大致分为平稳型、周期型、混沌型和复杂型。从几乎所有的随机初始模式开始,平稳型将演化为稳定静止状态,周期型将演化为稳定振荡状态,混沌型将演化为伪随机混沌状态,复杂型将变化为相互作用繁复状态且其局部结构会在长时间内甚至永远地存在。他还发现,绝大多数的生命游戏演化是无法决定的(undecidable):即使给定了初始模式和后续模式,依然找不到或者根本就不存在一个算法可以用来判断后续模式是否会出现和何时出现。值得一提的是,沃尔夫勒姆从分类开始时就已经看到了元胞自动机理论和史蒂芬·斯梅尔(Stephen Smale,1930- )的艰深混沌数学理论的内在联系,因为生命游戏的无法决定性和混沌的长期不可预测性是类似的。

上面说的是平面上的元胞自动机理论和生命游戏。对于一条规则来说,每个格点的黑子和白子邻居的组合共有9=512种,而每种组合都可以用二进制的0–1序列来表示并且是各自独立变化的,于是总共有512种可能。即便排除了那些没有静止、旋转和反射对称可能的不重要情形,剩下来的依然是一个天文数字。至于三维和更高维的元胞自动机理论及生命游戏,那就复杂得无法操控了,只能用几个文字来概括:超乎想象的丰富多彩!

沃尔夫勒姆是个很有故事的人物。他1959年出生于伦敦,12岁编写了一部关于物理学的词典草稿,13-14岁间写了三本关于粒子物理的手稿,15岁发表了第一篇学术论文。接下来,他17岁进入牛津大学,20岁取得加州理工学院理论物理博士学位,其答辩委员会成员包括有诺贝尔物理奖得主理查德·费曼(Richard P. Feynman,1918-1988)。之后,他22岁获得MacArthur奖,23岁开始推动并主导了关于“复杂系统”的科学研究,27岁时开发了Mathematica软件并创立了自己的Stephen Wolfram公司,从事数学软件和电脑软件的开发获得巨大成功。还有值得一提的是,他43岁时出版了一部名著《一种新科学》(A New Kind of Science),代表了一条与圣塔菲研究所(Santa Fe Institute)不一样的复杂性科学研究路线。

【三】

现在,是时候来介绍本文的主人公约翰·康威了。

图4 John H. Conway(1937–2020)

1937年12月26日,康威出生于英国利物浦(Liverpool)。父亲Cyril Horton Conway(1903-1963)是一间中学的实验室助理,母亲名叫 Agnes Boyce(1904-1972)。在家中他有两个姐姐,Sylvia和Joan。

康威小时候性格内向,但喜欢数学。他是在二战时期物资短缺的环境下长大的,儿时岁月相当艰辛。康威在小学表现甚为出色,各门功课都名列前茅。他十一岁升读中学面试时被问及长大后想干什么,他回答说想在剑桥大学里当一名数学家。

果不其然,作为一名高中生,康威“发现”了一个拓扑结(knot)的分类方式,完成了一个近乎完整的最多具有11个交叉点的结的表列,并在1900年起就被数学书一直沿用的分类表中发现了一些重复和遗漏。

康威中学毕业后进入了剑桥大学,在Gonville and Caius College学习数学。他于1959年获得学士学位,并开始在数学家哈罗德·达文波特(Harold Davenport,1907-1969)的指导下从事数论研究。达文波特是约翰·李特尔伍德(John E. Littlewood,1885-1977)的博士生,研究领域在丢番图近似和数字几何方面,致力于探讨黎曼猜想及相关问题,1957-1959年担任伦敦数学会主席,期间开始任职剑桥Rouse Ball数学讲座教授至离世。

康威在读研究生期间,证明了导师达文波特介绍的一个数论公开问题:任何一个正整数可以写成最多37个正整数的5次方的和。这是一个有二百年历史的著名“华林问题”的特别情形。具体地说,英国数学家爱德华·华林(Edward Waring,1736-1798)在1770年发表的《代数沉思录》(Meditationes Algebraicae)中提出了一个猜想,用现在比较系统完整的表述就是:对除了1之外的每个正整数k ,都存在一个正整数g(k),使得任何正整数都能表示为最多g(k) 个正整数的k次幂之和。华林自己找到了开头的三个例子:g(2)=4,g(3)=9,g(4)=19。多年之后,大卫·希尔伯特(David Hilbert,1862-1943)证明了g(k) 的存在性,但不清楚它们的具体数值。康威则证明了接下来的一个:g(5)=37。今天知道, 前面的数字是:4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055, ……。

康威在证明华林猜想的努力中意外和陈景润(1933-1996)撞了车。这使他懊丧,但让他从此对各种无限序列产生了极大兴趣。这方面的强烈好奇心成为了他后来研究和发展元胞自动机理论特别是生命游戏的主要动力。

动脑筋的游戏对年轻数学家来说一般都极具吸引力。康威对各种游戏的兴趣始于他在剑桥读书时期。在那里,他成为一名狂热的西洋双陆棋(backgammon)玩家,常常在公共休息室里泡上几个小时玩这个游戏。期间,康威和计算机科学家迈克尔·帕特森(Michael S. Paterson,1942- )发明了二人博弈的数学游戏Sprouts。

康威于1964年获得数学博士学位,随后留校任职讲师并被选为 Sidney Sussex College 的 Fellow。后来他对人说,剑桥除了教会他数学,还把他“变得外向”了。

康威刚出道时尝试开展数理逻辑方面的研究,但不成功。他后来回忆道:“[那时]我非常沮丧。我觉得自己不是在做真正的数学。我没有文章可以发表,感到很苦恼。”

但是常言道,是金子总会发光。很快,康威人生转折的机会来了。1965年,英国数论和几何学家约翰·里奇(John Leech,1926-1992)发现了24维球体的密集堆积方法,其结构后来被称为“里奇晶格”(Leech lattice)。但是,里奇知道自己并不具备证明一般猜想所必需的群论技巧,于是到处演讲宣传,试图引起其他数学家的关注。他后来打趣地说:“是康威第一个吞下了我的诱饵。”

康威证明了,里奇晶格的对称群被两个二阶中心子群分解之后是一个前所未知的、8315553613086720000 阶的有限单群。这个数值有多大呢?打个比方吧,我们的银河系有大约四千亿颗恒星,而里奇晶格的阶数相当于二千万个银河系里所有恒星的总数。康威还发现了这个单群的很多有趣性质。1969年,康威把他的惊人发现发表在《伦敦数学会通报》(Bulletin of the London Mathematical Society)。那是康威的开山之作,让他从此“开始做真正的数学”。他研究了有限单群的分类,发现了三个零散单群,其中最大的一个后来被称为“康威群”(Conway group)。那是一个24维的对称群。要是在24维空间中堆积球体的话, 每个球都与其它196560个球相切触。

1969年,康威构造了几何拓扑中表示不同纽结(tangle)的“亚历山大–康威多项式”(Alexander-Conway polynomials),可以用来构作幻方游戏。他还引进了用于几何表示的“康威多面体符号”(Conway polyhedron notation)。

1970年,康威发明了一种无需计算器或日历便可以快速推算出任何给定日期是星期几的Doomsday算法。如前所述,这一年康威最大的成功是发明了“生命游戏”,让他声名大噪。他还因此获得了伦敦数学会颁发的1971年度Berwick Prize。

图5 康威正在运行生命游戏(1970年,Kelvin Brodie摄)

生命游戏并非一种博弈游戏。但康威也热衷博弈游戏,他在1972年设计了二人博弈游戏 Hackenbush,1974年又设计了二人博弈游戏Angel and Devil。

就数学理论而言,康威还是组合博弈论的开创者之一。在剑桥,康威一直沉迷于二人博弈的围棋并成为国际级水平的棋手。他注意到在围棋对抗接近尾声时,棋盘上的棋子分布看起来像是许多不同策略小游戏的总和。作为数学家,康威把这些小游戏用一个数字系统表示出来。康威的数字系统引起了计算机科学家唐纳德·克努特(Donald E. Knuth,中文名高德纳,1938- )的极大兴趣。高德纳因他的四卷本《计算机程序设计艺术》闻名天下。1974年,高德纳为了向学生们介绍康威的数字系统及其在计算机编程上的应用,专门以小说的形式编写了一本《超实数》(Surreal Numbers)讲义。后来,康威在这个“超实数”的数字系统中还设计了一种名为Domineering 的游戏,记载在他1976年出版的名著《数字与游戏》(On Numbers and Games)里。在该书中康威指出:这个超实数系统的本质是博弈游戏。

1973年,康威在剑桥晋升为 Reader(准教授)。

1975年,前面提到的那位科普作家马丁·加德纳在《科学美国人》杂志的“数学游戏”专栏介绍了康威在平面几何图形镶嵌中的“康威标准”(Conway criterion),还展示了一个用108片七连块瓷砖无缝铺满地面的美妙设计。

1979年,康威和数学家西蒙·诺顿(Simon P. Norton,1952-2019)在一篇发表于《伦敦数学会通报》的题为“魔群月光”(Monstrous moonshine)的论文中提出了一个猜想:存在一个基于魔群的无限维代数结构,通过魔群的不可约线性表示,它恰好给出了菲利克斯·克莱因(C. Felix Klein,1849-1925)的J函数傅立叶展开的所有系数,而魔群中每一个元素在这个代数结构中的作用都自然地给出了与某个群相关的模式。这里,魔群(monster group)是包含元素数目超过1053的群,这个数字比地球上所有原子总数的一千倍还要多。他们用“魔群月光猜想”的称谓,不但意指这个猜想内容极其丰富浪漫,而且表示其证明可望而不可及。不过,1992年,加州大学伯克利分校年轻数学家理查德·博赫兹(Richard Borcherds,1959-)证明了这个猜想,并因此获得了1998年度菲尔兹奖。这个定理让数学家们发现了魔群、模函数和弦理论之间千丝万缕的联系,以至被认为提供了宇宙终极的对称性。

1981年,康威被选为英国皇家学会院士。提名表描述他是“一位多才多艺的数学家,他将深刻的组合洞察力与精湛的代数技巧相结合。特别是,在构建和操控‘另类’代数结构方面,他利用这些结构以完全出乎意料的方式阐明了各种各样的问题。……他对有限群论、结理论、数理逻辑(集合论和元胞自动机论)以及博弈论(及其实践)都做出了杰出贡献”。

1982年,康威和埃尔温·伯利坎普(Elwyn R. Berlekamp,1940-2019)及理查德·盖伊(Richard K. Guy 1916-2020)一起出版了《数学游戏的制胜之道》(Winning Ways for Your Mathematical Plays)一书,介绍了许多新颖的数学游戏,还详细分析了一些他人设计的游戏,如索玛立方块(又名立体七巧板,Soma cube),Peg solitaire,Phutball,Conway's soldiers,Two wizards puzzle等等。

1983年,康威在剑桥晋升为数学教授。

1986年,他离开剑桥,接受了普林斯顿大学的约翰·冯·诺依曼数学讲座教授职位,在那里工作至离世。在普林斯顿,他的主要数学研究集中在几何学,特别是晶格的对称性分析。

1986年,康威作为主要作者出版了《有限群图集》(ATLAS of Finite Groups)一书。这本巨著历时15年完成,提供了关于单群性质的全部基本信息。

1987年,康威荣获伦敦数学会第一次颁发的Pólya Prize。

1988,康威和 AT&T 实验室的数学家尼尔·斯隆(Neil J. A. Sloane,1939- )合作,出版了一本约700页的大书《球堆积、格子和群》(Sphere Packing,Lattices and Groups),通过不同维度的球体去处理空间的密集包装。他俩的方法不但能解决立体几何镶嵌中的许多问题,后来还发现可以应用于通信技术中的纠错码设计。两人以之申请并获得了美国4507648号专利:“用于多维代码的解码技术”。该技术报告还获得了IEEE信息理论学会的优秀论文奖。

1992年,康威被选为美国艺术与科学院院士。

1993年,康威与他的在读博士生威廉·施尼伯格(William A. Schneeberger)一起,证明了一条被称为“15定理”的惊人结果:如果一个正定二次型及其关联的整数对称矩阵可以表示所有 15以内的正整数,那么它就能够表示所有的正整数。这个优秀学生曾在1987年国际奥林匹克数学竞赛中获得银牌。2000年,印度裔的美国数学博士生曼朱尔·巴伽瓦(Manjul Bhargava,1974- )给出了一个大大简化了的证明,并因之获得2005年度拉马努金奖(SASTRA Ramanujan Prize)。接下来,他和1999年普林斯顿数学博士毕业的学友Jonathan P. Hanke一起,把这个系数15 扩展到了290,建立了一条“290定理”。巴伽瓦后来获得2014年度菲尔兹奖。

康威于1997年获美国西北大学Nemmers Prize,2000年获美国数学会Nemmers Prize和Steele Prize,2001年获美国Dickinson College授予Joseph Priestley Award,还获英国University of Liverpool颁发荣誉科学博士学位。

2006年,康威和普林斯顿数学家西蒙·科钦(Simon B. Kochen,1934- )花了十年时间之后整理出一条“自由意志定理”(Free Will Theorem),发表在《物理学基础》(Foundations of Physics)杂志,其加强版于2009年发表在《美国数学会通告》(Notices of the American Mathematical Society)。这条定理的字面叙述是:如果物理学家在做实验时有自由意志,那么在一定条件下基本粒子本身也有自由意志。而定理的科学含义是:量子力学的测量结果无法通过实验之前的任何预选方法来确定。

康威于2014年获罗马利亚Alexandru Ioan Cuza University颁发荣誉科学博士学位,2017年成为英国数学联盟(British Mathematical Association)终生荣誉会员。

图6 《天才在玩:康威的好奇思想》

加拿大女科学记者和传记作家西沃恩·罗伯茨(Siobhan Roberts)于2015年出版了一部关于康威的传记《天才在玩:康威的好奇思想》(Genius at Play: The Curious Mind of John Horton Conway),赞扬他“是一位奇异的数学家,拥有可爱活泼的大脑。他是阿基米德[古希腊百科全书式科学家]、米克·贾格尔[英国摇滚乐手]、萨尔瓦多·达利[西班牙画家]和理查德·费曼[美国物理学家、诺贝尔奖得主]的集合体——他拥有摇滚明星的魅力、狡黠的幽默感、博学多才的好奇心,以及企图向所有人解释世界一切的永无休止的热情。”

【四】

我们的天才数学家康威爱玩游戏,生活上不修边幅。他几十年里甚至在严冬都经常穿着凉鞋。他留着乱蓬蓬的头发, 偶尔自己修剪一下发梢。他办公桌上堆放着好几年前的信件,其中很多从未拆封。他在接受美国艺术与科学院颁发院士证书时,穿着一件绿色运动T恤上台。他的生活极其简朴,家中甚至没有电视机。他除了玩游戏之外的唯一爱好就是看书。但是, 他经常对一些小问题好奇不已,比如如何更改一下象棋规则让大家玩得更有趣?2222年2月2日是星期几?据说他还能背出圆周率π 值的前1111位数字。

传闻康威最喜欢的一个单词是拉丁文“Floccinaucinihilipilification”,其大意是:总把身外事物看得毫无价值。

有个朋友开玩笑画了一幅描绘康威的漫画,让他的头上长出了“角球”(horned sphere),那是用作病态示例(pathological example)的拓扑实体,把他违反直觉的糟糕行为形象化了。这幅有趣的漫画今天成了康威众多老朋友的珍藏纪念品。

图7 头上长着“角球”的康威(Simon J. Fraser 绘)

康威在1986年到了普林斯顿之后,作为成功的游戏玩家他扮演了一个出色的数学魔术师角色。他常常“利用卡片、绳索、骰子、衣架,甚至是奇怪的slinky弹簧玩具作为道具,以扩展他自身的想象力,并通过签名传播方式去分享他对数学的痴迷。”

康威即使在退休后依然沉迷各种数学游戏。他与计算机科学家亚历克斯·瑞巴(Alex Ryba)写了关于幻方(magic squares)和迷魂六角形(hexagrammum mysticum)的帕斯卡定理以及超斐波那契级数和帝国大厦问题(The extra Fibonacci series and the empire state building)等有趣数学游戏论文。

康威曾经戏说自己“每天都在玩, 从来没有工作过”。他说: “新概念的产生不是很容易的事,大约每年只产生一个新的并且成功的概念。当我提出一些有用的概念时,学生们只当我在卖弄,因为我常常在一些浅显的课题上做文章。我喜欢在咖啡店内思索,因为这样比较容易体验真理。这确实不是卖弄行为以示与众不同。在那里,通过分析一些数学游戏,我写了一篇又一篇的论文。”

最后,说到康威的人生,他貌似极为乐观开朗,但其实人生颇为跌宕不安。

2006年,尚未到70岁的康威中风,结果虽然没有影响智力,却让他右腿瘫拐,从此拄着手杖走路。

康威与第二任妻子Larissa养育有两个儿子,但两人后来经历了一场艰难的离婚。他因此在一段时间里患上了抑郁症并面临财务危机,随后又心脏病发作。他在与 Larissa及其律师为离婚谈判而共进午餐时,像吃配菜一样吞下了一大把安眠药。自*未遂之后,他天天穿着印有“SUICIDE rock”(自*摇滚者)字样的T恤,甚至还穿去学校工作。

2020年4月8日,康威感染了第一波新冠肺炎。他发烧三天之后,在新泽西州New Brunswick家中去世,享年83岁。康威自己的“生命游戏”结束了,但他留给后人的数学游戏则将永远流传。

图8 晚年康威

数学家丘成桐(Shing-tung Yau)在纪念康威的短文中评价说:“他是数学界公认的奇才,想法杰出而与众不同。他创作的数学游戏,不单单是有意思的玩具,也富有理论数学的内容”。

数学家陶哲轩(Terence Tao)在悼念康威的文章中说:“康威可以说是所有数学家构成的凸包中的一个极点”。

* 注:本文所有图片均来源于自网络

查看全文
大家还看了
也许喜欢
更多游戏

Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved