陈关荣 | 简单而复杂的“生命游戏”
企业
科学
2024-05-23 12:32
上海
人类是社会动物，而人类的社会活动则既简单又复杂。长期以来，数学家、计算机科学家和社会学家们一直试图用简单明了的方式方法去刻画错综复杂的社会现象，其中“生命游戏”提供了一个“寓科学于娱乐”的活动框架。在一个充分大的围棋棋盘上，为简单起见每个空格表示已经放有一个白子（而白子就不标画出来了）。如果空格内出现一个黑子，就表示黑子取代了原有的白子。现在，让黑子表示“生”而白子表示“死”。另外，在棋盘上的任何9个格子组成的正方形区域里（见图1），对处于中心位置的黑子或白子来说，它上下左右和两对角线外的8个黑子（如果它们存在的话）都称为是它的邻居。我们的棋子游戏有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），它永远不停地向右下方滑翔前进。你看，这个滑翔机会永远无休止地生存并移动下去，期间代表“生”和“死”的黑子和白子交替出没，整个族群在发展和演变过程中就像有“生命”一样，对吧？图2 “振荡器”和“滑翔机”例子
至此，你看到了，这个棋子游戏的规则是固定的，但初始条件（黑子的个数和位置）可以有许多不同的选择。因此，容易想象，你能够尝试着去生成多种多样的“最终趋于死亡”、“不同周期振荡”和“永远变化生存”斑图。由于这个游戏可以用来描绘一些社会生命现象，故此设计师把它叫做“生命游戏”（Game of Life）。上面介绍的这个趣味横生的生命游戏简单而复杂，它的设计师是数学家约翰·康威（John Horton Conway，1937-2020）。关于康威的生平和贡献，笔者曾有过简单介绍[1]。康威在开发这个有趣的生命游戏时是英国剑桥大学数学讲师。1970年10月，科普作家马丁·加德纳（Martin Gardner，1914-2010）在《科学美国人》杂志的“数学游戏”专栏对这个生命游戏作了详细介绍。从此，学界和民间对游戏的兴趣和热情一发而不可收拾。据说，在那个生命游戏风靡世界的年代，全球有四分之一的电脑都在玩这个游戏。2010年，物理学家史蒂芬·霍金（Stephen W. Hawking，1942-2018）在他的科普著作《大设计》（The Grand Design）中写道：“我们可以想象，像‘生命游戏’这样的玩儿，它只有一些基本规则，便可以产生高度复杂的功能，甚至智慧。当然它可能需要包含数十亿个正方形的网格。但这并不困难，我们大脑中就有数千亿个细胞。”康威并不是构思出这类具有深刻数学原理和社会学意义的生命游戏的第一人。游戏的基本思想要追溯到两位美国数学家：波兰裔的斯塔尼斯拉夫·烏拉姆（Stanislaw Ulam，1909-1984）和匈牙利裔的约翰·冯·诺伊曼（John von Neumann，1903-1957），他们在上世纪40-50年代为模拟生物细胞的自我复制提出了“元胞自动机理论”（Cellular Automata）的雏形。当年，由于没有高速大型电脑，他们的构想没有得到验证因而未受学术界的重视。1970年，马丁·加德纳在《科学美国人》杂志介绍了康威的生命游戏之后，元胞自动机理论才受到了越来越广泛的关注。在众多卓有成效的元胞自动机理论研究者中，特别值得提及的是美国电脑科学家史蒂芬·沃尔夫勒姆（Stephen Wolfram，1959-）。沃尔夫勒姆是个很有故事的人物。他1959年出生于伦敦，12岁编写了一部关于物理学的词典草稿，13-14岁间写了三本关于粒子物理的手稿，15岁发表了第一篇学术论文，17岁进入了牛津大学。1978年，19岁的沃尔夫勒姆接到美国物理学家默里·盖尔曼（Murray Gell-Mann，1929-2019）的电话邀请，来到了加州理工学院就读研究生。盖尔曼因发现基本粒子夸克在1969年获诺贝尔物理学奖，他是圣塔菲研究所首任所长。1979年，在加州理工学院读书期间，沃尔夫勒姆便开创了自己的第一个大型电脑语言SMP，用以辅助物理学研究。该语言是后来著名数学软件Mathematica和电脑Wolfram语言的前身。1980年，21岁的沃尔夫勒姆获得了理论物理学博士学位，其答辩委员会成员包括有诺贝尔物理奖得主理查德·费曼（Richard P. Feynman，1918-1988）。之后，沃尔夫勒姆留校任教，随即获得MacArthur奖。接下来，23岁的他开始推动并主导了关于“复杂系统”的科学研究，并在27岁时创立了自己的Stephen Wolfram公司，从事数学软件和电脑软件开发。如所周知，他获得了巨大成功，不过那是后话了。1983年，由于知识产权纠纷，沃尔夫勒姆离开了加州理工学院，到了普林斯顿大学自然科学学院工作。没过多久，他就发明了元胞自动机的计算程序。沃尔夫勒姆后来回忆说：“我开始时并不觉得简单的元胞自动机有什么有趣之处，不过还是利用电脑试着对它们做了些试验。令我十分惊讶的是，就算是构造极为简单的元胞自动机，它们仍然有着极其复杂的行为，这对传统的科学教条是个莫大的冲击。过了些日子，我才意识到它的巨大潜力。那是我写这本《一种新科学》（A New Kind of Science）的最早动机。”我们知道，该书实际上代表了一条与圣塔菲研究所不一样的复杂性科学研究路线。当年，沃尔夫勒姆使用电脑模拟对基本元胞自动机的类别进行了系统性的分析，对一维基本元胞自动机的256种规则所产生的模型进行了深入的研究，并用熵（entropy）的概念来描述元胞自动机的演化行为。他根据复杂性理论将元胞自动机大致分为平稳型、周期型、混沌型和复杂型。从几乎所有的随机初始模式开始，平稳型将演化为稳定静止状态，周期型将演化为稳定振荡状态，混沌型将演化为伪随机混沌状态，复杂型将变化为相互作用繁复状态且其局部结构会在长时间内甚至永远地存在。沃尔夫勒姆发现，绝大多数的生命游戏演化是无法被决定的（undecidable）：即使给定了初始模式，依然找不到或者根本就不存在一个算法可以用来判断后续模式是否会出现和何时会出现。沃尔夫勒姆指出110号规则对应的元胞自动机具有图灵完备性（Turing completeness）。在电脑科学中，图灵完备性是指具有无限存储能力的通用编程语言，它可以通过一系列数据操作规则来模拟图灵数学逻辑机。沃尔夫勒姆发现，凡是可以通过编写程序去计算的复杂系统演化行为，都可以用元胞自动机来实现。顺便提及，沃尔夫勒姆从分类开始时就已经看到了元胞自动机理论和美国数学家史蒂芬·斯梅尔（Stephen Smale，1930–）的艰深混沌数学理论的内在联系，因为生命游戏的无法决定性和混沌的长期不可预测性[2]是类似的。上面讨论的只是平面上的生命游戏和元胞自动机理论。对于任意一条游戏规则，每个格点的黑子和白子邻居的组合共有29=512种，而每种组合都可以用二进制的0–1序列来表示并且是各自独立变化的，于是总共有2512种可能。即便排除了那些没有静止、旋转和反射对称可能的不重要情形，剩下来的依然是一个天文数字。至于三维和更高维数的生命游戏和元胞自动机理论，那就复杂得无法描述了，只能用几个简单文字来概括：超乎想象的丰富多彩！故事讲到这里，你一定会好奇，这迷人的元胞自动机理论及其计算程序会有什么实际应用呢？作为回应，我们简单地介绍一下元胞自动机技术在电脑科学、生物学、化学、物理学和音乐艺术方面的几个具体应用或潜在应用[3]。图3 芋螺贝壳和Wolfram 30号规则生成的班图[4]
（1）电脑科学：
元胞自动机处理器是该概念的物理实现，它通过计算方式来处理信息。元胞的状态仅通过与相邻邻居元胞的相互作用来确定，而不需要也不存在与更远的元胞进行直接通信。一种典型的元胞自动机处理器具有脉动阵列配置，其中元胞相互作用通过电荷、磁性、振动或其他物理手段来实现。Wolfram 30号规则最初被建议作为一种可能的分组密码用于密码学。二维元胞自动机可用于构建伪随机数发生器，而且元胞自动机的演化是单向函数，其逆很难破解，即容易计算未来状态，但回算先前的状态却异常困难。元胞自动机后来也被提议用于公钥密码学并用来设计各种纠错码。一些漂亮的海螺贝壳图案可以用元胞自动机生成，例如分布广泛的芋螺纤维（conus textile）具有类似于 Wolfram 30号规则的班图（图3），因而元胞自动机理论能够用来解释和研究贝壳的颜色细胞自然生长内在规律。动物体内的成纤维细胞（fibroblast）与元胞自动机有很多相似之处，例如每个成纤维细胞只与其邻居相互发生作用。植物调节气体吸入和呼出的机制类似于元胞自动机的演化过程，例如树叶上的每个气孔有呼和吸两个动作，对应于一个元胞的两种状态。头足类（cephalopod）动物例如乌贼的皮肤班图中，每个状态对应于色素细胞的展开和收缩，可以用二维元胞自动机进行模拟和解释。生物神经元的活动甚至动物识别和学习等复杂行为都可以用阈值自动机来模拟。化学中的Belousov–Zhabotinsky反应是一种时空化学振荡过程，它可以通过元胞自动机来进行模拟和分析。例如一层单薄而均匀的丙二酸、酸化溴酸盐和高铈盐混合在一起时，迷人的几何图案如同心圆和螺旋曲线便在介质中传播，所产生的波形与某种元胞自动机生成的图案非常相似。概率元胞自动机可用于统计学和凝聚态物理学的研究中，去分析流体动力学和相变等现象。伊辛（Ising）模型是一个典型的例子，其中每个单元格可以处于“向上”或“向下”状态，从而用于理想化地表示磁铁。通过调整元胞自动机模型参数，可以改变处于相同状态的元胞比例，解释了为何对铁磁体加热可以消磁。物理学中还有一种格子气体元胞自动机，可以用来模拟液体流动并对之给予合理解释。元胞自动机可用来生成一些新颖动听的音乐作品和设计电子游戏。某些类型的元胞自动机还可用于生成各种迷宫。两个著名的元胞自动机迷宫Maze和Mazectric类似于前面介绍的“生命游戏”，复杂而有趣。此外，元胞自动机还能生成丰富多彩的图案用于艺术设计。今天，元胞自动机理论及各种数学游戏的研究仍在继续。我们期待在不久的将来会得到更丰富更有趣的成果。注：原文发表在《复杂学》2024年第2卷第2期45-52页，经作者授权转载[1] 陈关荣（2023），爱玩的天才数学家康威，《数学文化》第14卷第4 期，36-46页https://www.global-sci.com/intro/article_detail/mc/22165. html[2] 陈关荣（2022 年），这门复杂性科学有个别致的名称―混沌，《复杂学》第1 卷第1 期，69-75页[3] Wikipedia: Cellular automaton，https://en.wikipedia.org/wiki/Cellular_automaton[4] Stephen Wolfram (2019), Announcing the rule 30 prizes, https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/
