图1：由志愿者March提供的元胞自动机示例生命游戏

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

今天分享复杂性科学领域里面一个典型而有趣的模型：元胞自动机。本文将介绍元胞自动机的基本概念，有哪些好玩的游戏，知名的研究者、机构以及一些入门的学习资料。

1.什么是元胞自动机？

元胞自动机（Cellular Automata，或翻译为细胞自动机、点格自动机）是一种在空间和时间上都离散的演化动力系统。系统由正方形、三角形或者立方体等基本几何元素的元胞（Cell）组成，这些元胞按照一定规则排列可以形成一个空间区域，然后每个元胞之上都有若干种离散或者连续的状态，这些状态在每一个时间步都会按照相同的规则发生变化，于是形成了整个元胞自动机的演化过程。

人们通常通过元胞自动机来研究从局部简单的规则到整体复杂动态的涌现过程。元胞自动机自产生以来，被应用在社会、经济、军事等各个研究领域，也有相关的扩展模型，比如沙堆模型、投票模型等。

图2：Sparr Risher制作的物理模拟元胞自动机

2. 相关概念介绍

康威的生命游戏 Conway's Game of Life

生命游戏是一个零玩家参与的游戏，由英国数学家约翰·康威（John Conway）在1970年发明的元胞自动机，刊登在当年的《科学美国人》上。

在一个无数格子的网格（元胞）中，每个元胞有两种状态：死（白格）或活（黑格），而下一回合的状态完全受它周围8个元胞的状态而定。按照以下三条规则进行演化：

a. 活元胞（黑格）周围的细胞数如果小于2个或多于3个则会死亡；（离群或过度竞争导致死亡）

b. 活元胞（黑格）周围如果有2或3个细胞可以继续存活；（正常生存）

c. 死细胞（白格）周围如果恰好有3个细胞则会诞生新的活细胞。（繁殖）

给定初始状态（通常称为种子），根据简单的规则，就能演化出复杂的生命现象。

效果如下：

图3：康威生命游戏中的一种可持续繁殖模式

布莱恩的大脑 Brain's Brain

布莱恩·西尔弗曼（Brian Silverman）是加拿大计算机科学家,他设计了很多有趣的元胞自动机规则，其中经典的是Brain’s Brain和The WireWorld。Brain’s Brain是由一个无线的二维细胞网格组成，每个细胞处于3种状态，类比大脑，可以把细胞现象成是神经元，三种状态对应的是：开（刺激）、关（关闭但是准备好刺激）、死（刺激但是没有反应），同时该细胞受周围8个细胞的影响，从而发生演化。

图4：一个典型的混沌的Brain’s Brain模式，展示了各种形状：宇宙飞船、耙、和对角线波。在这个动画中，处

朗顿的蚂蚁 Langton's ant

朗顿的蚂蚁是元胞自动机一个经典的示例。它由克里斯托夫·兰顿在1986年提出，它是一个由黑白格子和一只”蚂蚁”构成的二维图灵机。设置具体规则如下：

如果蚂蚁位于白色方块，则向右旋转 90°，反转方块的颜色，然后向前移动一步。
如果蚂蚁位于黑色方块，则向左旋转 90°，反转方块的颜色，然后向前移动一步。

效果如下：

图5：朗顿蚂蚁前200步动画演示

图6：当朗顿蚂蚁程序进行到10000步时，它会自动生成路线进行繁衍

除了颜色反转，还可以让蚂蚁调整方向或者定义多种颜色进行循环，从而产生更加复杂的图案。

图7：L2NNL1L2L1: 六边形循环生长

冯·诺依曼元胞自动机von Neumann cellular automaton

冯·诺依曼元胞自动机是元胞自动机最原始的表达方式。在冯 · 诺依曼的细胞自动机中，有限状态机（或细胞）被安排在一个二维的笛卡尔网格中，并与周围的4个元胞作用。因为冯 · 诺依曼的细胞自动机是第一个使用这种安排的例子，被称为冯·诺依曼邻居（von Neumann neighbourhood）。与此相对的是，摩尔邻居（Moore neighborhood），是指元胞受到周围的8个相邻元胞的共同作用。

图8：一个简单的冯·诺依曼元胞自动机的配置。

3. 知名学者简介

冯·诺依曼 von Neumann

图9：冯·诺依曼 von Neumann

元胞自动机的理论最早由冯·诺依曼（ von Neumann）创立，他用这种工具研究机器人自我复制的可能性。其出版的《自复制自动机理论》（Theory of Self-reproducing Automata）的五个章节讨论到元胞自动机。

集智俱乐部也编写过文章以供大家更充分的探索冯·诺依曼的思想：

引言：

冯·诺依曼：探寻计算的“原力”
冯·诺依曼的遗产：寻找人工生命的理论根源

文摘部分：

1.一般意义的计算机：神经网络与图灵机的复杂度博弈
2.控制与信息理论：人工智能如何掷骰子——三种概率理论
3.信息的统计理论：复杂度阈值与概率论中“漏洞”
4.大数之道：人脑与电脑的对比
5.复杂自动机的一些考量——关于层次与进化的问题自指机器的奥秘

在文内预测了复杂性科学未来100年的发展方向，而且还指出了生命逻辑最核心的奥秘：热力学、信息论与自指之间的深刻联系。

克里斯托弗·朗顿 Christopher Langton

图10：克里斯托弗·朗顿（Christopher Langton ）

克里斯托弗·朗顿（Christopher Langton ），美国计算机科学家，人工生命领域的创始人之一。在密歇根大学读研究生的时候，创建了朗顿蚂蚁和朗顿循环。同时他在20世纪80年代末创造了人工生命这个术语，当时他于1987年在洛斯阿拉莫斯国家实验室组织了第一次“生命系统的合成和模拟研讨会”。在洛斯阿拉莫斯任职之后，朗顿加入了圣塔菲研究所（SFI)，继续他的人工生命研究。

约翰·何顿·康威（John Horton Conway）

图11：约翰·何顿·康威（John Horton Conway）

英国数学家约翰·何顿·康威（John Horton Conway）坚称，他从来没有认真工作过一天，他一直在玩”游戏“。Conway先后任职于剑桥大学和普林斯顿大学，担任过普林斯顿的应用和计算数学教授，被誉为是一位天才，他最为人所知的贡献是名为“ Game of Life”的元胞自动机，生命游戏被《科学美国人》的专栏作家Martin Gardner称为“Conway最著名的创意”。严格来说，Game of Life不是真的游戏，Conway称它是一个“零玩家无结局”游戏。

史蒂芬·沃尔夫勒姆（Stephen Wolfram）

图12：史蒂芬·沃尔夫勒姆（Stephen Wolfram）

史蒂芬·沃尔夫勒姆（Stephen Wolfram）是数学软件Mathematica的创始人，同时是沃尔夫勒姆研究公司的创立者和首席执行官。在学术上，他以粒子物理学、元胞自动机、宇宙学、复杂性理论、计算机代数系统上的研究成果闻名于世。

同时他对初等元胞机256种规则所产生的模型进行了深入研究，并用熵来描述其演化行为，在他的著作《A New Kind of Science》中详细地介绍了元胞自动机，讨论了元胞自动机的类型：平稳型、周期型、混沌型和复杂型，并且介绍了元胞自动机在各个系统中的应用。

4.学习资源（书籍与课程）

书籍

1.《一种新的科学》 A New Kind of Science

本书是史蒂芬·沃尔夫勒姆（Stephen Wolfram）于2002年出版的一本畅销书，颇具争议。它的主要内容是对像元胞自动机这样的计算系统经验化和系统化的研究。沃尔夫勒姆称这些系统为简单的程序，并认为适合研究简单程序的科学哲学和方法与其他科学领域有关。整本书很少看见数学公式，全部用图形进行科学推理甚至证明，没有参考文献，所有的历史相关工作介绍都放到了批注中；书中提出了很多大胆的猜想，如：我们生活的世界就是一个被计算机模拟出来的世界等等。

释放比特自由——Wolfram的“一种新科学”介绍：http://rrd.me/fXUfT

2.《元胞自动机与复杂性论文集》 Cellular Automata and Complexity: Collected Papers

这本书是一个论文合集，主要收集了Wolfram关于元胞自动机和复杂性研究的原始论文，有一些是科学界广为人知的论文，有一些也从来没有发表过。

元胞自动机已经成为了一个新的研究领域，在物理学、经济学和计算机科学许多影响具有非常重要的影响。

元胞自动机与复杂性论文集 Cellular Automata and Complexity: Collected Papers：

http://rrd.me/gcq4W

3.《元胞自动机: 理论与实验》 Cellular automata: Theory and experiment

这本书涵盖了当代研究元胞自动机的很多资源，包括综述、研究报告、近期的文献指南和可用软件等。每个章节涵盖数学分析、关于元胞自动机的空间结构，特定性质的学习规则，元胞自动机在生物、物理、化学、计算机科学中的应用，以及在神经网络、布尔网络和耦合晶格网络（coupled map lattices）上的概述。

元胞自动机: 理论与实验 Cellular automata: Theory and experiment：

http://rrd.me/gcq8X

4. 《自复制自动机理论》 Theory of Self-reproducing Automata

该书由人工智能先驱 Arthur Burks 整理自冯·诺依曼的手稿《自复制自动机理论》。集智俱乐部资深成员“东方和尚”将全书第一部分翻译成中文，张江做了详细点评。这五篇文章不仅仅预测了复杂性科学未来100年的发展方向（事实上很多领域已经验证了冯·诺依曼的预言），而且还指出了生命逻辑最核心的奥秘：热力学、信息论与自指之间的深刻联系。

《自复制自动机理论》中文版译稿整理集：

http://url.cn/53ztts

5. 《元胞自动机：一个离散的宇宙》Cellular Automata: A Discrete Universe

这本书总结了元胞自动机的基本性质，并且，深入地探索了许多和元胞自动机相关的其他领域，包括人工生命、混沌、涌现、分形、非线性动力系统和自组织。这本书适合于想要学习了解秩序、混沌和复杂性涌现学生、老师或者研究者。它涵盖了一个广泛的参考书目，以及在网络上可以找到的关于元胞自动机的资源清单。

元胞自动机：一个离散的宇宙 Cellular Automata: A Discrete Universe

http://rrd.me/gcqBH

课程

NetLogo多主体建模

课程链接：

https://campus.swarma.org/play/coursedetail?id=429

上述元胞自动机的示例你是否也想动手操作？其实，最好的入门手段就是自己亲手在计算机中搭建一个复杂系统。

NetLogo就是一个非常好的入门工具，它可以让你通过简单的设置和代码编写就能搭建出一个超酷炫的多主体仿真（模拟）程序。而我们推荐由北京师范大学系统科学学院教授张江老师的《NetLogo多主体建模》课程为你的探索之旅提供资源。