1 概念

元胞自动机的定义

元胞自动机（Cellular Automata，简称CA）是一种应用比较广泛的模型理论，由冯·诺依曼创始，经数学家Conway、物理学家Wolfram等人的贡献后迅速发展。在物理学定义上，元胞自动机指的是，定义在一个由具有离散、有限状态的元胞组成的元胞空间上，按照一定的局部规则，在离散的时间维度上演化的动力学系统。在数学定义上，从不同的角度有着基于集合论的定义和拓扑学的定义，简单起见，在此不做阐述。

元胞自动机的组成

元胞：又称细胞、单元或者基元，是元胞自动机最基本的组成部分。元胞分布在离散的欧几里得空间位置上，每个时刻有着离散的状态，如{0,1}等。

元胞空间：元胞所分布在欧几里得空间上的网格点的集合。最常见的为二维元胞空间，通常可按三角形、四边形和六边形三种网格排列。

邻居：元胞自动机的演化规则是局部的，对于指定元胞的状态进行更新时只需要知道其临近元胞的状态。某一元胞状态更新时要搜索的空间域叫做该元胞的邻居。

邻居的划分：在四方网格划分下的二维元胞自动机的邻居通常有以下几种形式： Von Neuman型： Moore型：扩展的Moore型：边界条件：实际模拟元胞自动机的演化时不可能处理无限网络，系统必须是有边界的。处理边界格点时，可以为边界的信息进行编码，由此选择不同的演化规则。另一种方法是在边界处扩展，以满足边界有与内部类似的邻居。

周期型边界：周期型是指相对边界连接起来的元胞空间。这种空间与无限空间最为接近，进行理论探讨时，常以此类空间作为实验进行模拟。 b - a --------- b 固定边界：所有边界外元胞均取某一固定常量。 1 - a --------- b 绝热边界：边界外元胞的状态始终和边界元胞的状态保持一致。 a - a --------- b

演化规则：根据元胞当前状态及其邻居状态确定下一时刻该元胞状态的动力学函数。 元胞自动机的特征：标准的元胞自动机具有以下几个特征：（1）同质性、齐性：同质性反映在元胞空间内的每个元胞都服从相同的规则；齐性指的是元胞的分布方式相同，大小形状相同，空间分布整齐。（2）空间离散：元胞分布在按一定规则划分的离散的元胞空间上。（3）时间离散：系统的演化是按等时间间隔分步进行的。t时刻的状态只对t+1时刻的状态产生影响。（4）状态离散、有限：元胞自动机的状态参量只能取有限个离散值。（5）同步计算（并行性）：元胞自动机的处理是同步进行的。（6）时空局域性：每个元胞在t+1时刻的状态，取决于其邻居的元胞在t时刻的状态。（7）维数高：动力系统中一般将变量的个数成为维数。任何完备元胞自动机的元胞空间是在空间上的无穷集，每个元胞的状态是这个动力学系统的变量，因此元胞自动机是一类无穷维动力系统。

2 Conway的生命游戏

在20世纪60年代末，Conway设计出了一种神奇的数学游戏，后来被人们称为“生命游戏”。该生命游戏有一些基于简单数学规则的元胞组成，它能模拟出元胞的生、死以及繁殖的过程。“生命游戏”的基本思想是给定一个初始构型，然后观察该构型按照Conway的基因定律（genetic laws）进行的演化。1970年Conway的朋友Garnder在《科学美国人》上发表了第一篇关于生命游戏的文章，此后生命游戏广为流传。Gardner曾经写道：“生命游戏不仅仅使Conway成为一个家喻户晓的人物，而且开创了一个全新的数学研究领域——元胞自动机”。

生命游戏的构成： （1）元胞分布在规则划分的二维方形网格上；（2）元胞具有0、1两种状态，0代表“死”，1代表“生”；（3）元胞采用Moore邻居形式；（4）一个元胞下一个时刻的生死由本时刻本身的生死状态和周围8个邻居的状态决定。

生命游戏的演化规则：

对于活的元胞：

（1）生存：如果该元胞的邻居中有2个或者3个元胞是活的，那么它将继续生存下去；

（2）死亡：如果它的邻居有4个及以上元胞是活的，那么它将死去；如果它的邻居只有一个或者没有活的元胞，那么它将死去。

对于死的元胞：

（3）繁殖：如果它的邻居有3个元胞是活的，那么它将变成活的元胞。

演化规则的数学表达形式如下：

i f (S_{i}^{t} = 1) t h e n S_{i}^{t + 1} = ⎩ ⎨ ⎧ 1, 0, i f \sum S_{N}^{t} = 2 or 3 i f \sum S_{N}^{t} < 2 or S_{N}^{t} > 3

i f (S_{i}^{t} = 0) t h e n S_{i}^{t + 1} = ⎩ ⎨ ⎧ 1, 0, i f \sum S_{N}^{t} = 3 i f \sum S_{N}^{t}! = 3

生命游戏的一些演化形态

TYPE 1 固定不变型：构型的状态不会随时间变化。 TYPE 2 振荡型：经过一段时间后回到初始形态，而且位置不会发生变化、 TYPE 3 宇宙飞船型：经过一段时间后回到初始形态，但已经沿着某一方向产生了位移，而且方向固定。 TYPE 4 生命数量以某一常量不断增加的构型，又可分为：大炮（每个循环周期内不断发射出“宇宙飞船”型的振荡型构型）、吹嘘者（移动过程中不断留下固定不变型、振荡型或（和）宇宙飞船型的构型）、饲养员（生命数量呈二次方速度增长）。

TYPE 5 不稳定型：经过一系列演化过程，不会恢复到初始状态。

3 Wolfram的初等元胞自动机

从斯坦福线性加速器中心退休的物理学家斯坦利·鲁比曾说过：“这家伙（Wolfram）是350年来和牛顿最接近的人”。Stephen Wolfram于1959年出生于英国，15岁时就发表了第一篇论文。后来他领导开发著名数学软件Mathematica，该软件在工程和数学领域的广泛应用让Wolfram成为了千万富翁。

从1981年起，Wolfram开始致力于探索自然界中存在的复杂性的根源问题，他的一个关键思想就是用数值实验来研究元胞自动机。在1981年至1986年的短短几年之内，Wolfram发表了关于元胞自动机理论的一系列重要论文，一举奠定元胞自动机的理论基础。

初等元胞自动机

初等元胞自动机是状态集 $S$ 只有两个元素 $S_{1}, S_{2}$ ，即状态个数 $K = 2$ ，邻居半径 $r = 1$ 的一维元胞自动机。假设一个元胞所具有的状态数为 $k$ ，所采用的的邻居半径为 $r$ （邻域内含 $2 r + 1$ 个元胞），这样可能的输入条件的个数就是 $k_{2 r + 1}$ ，总的规则数为 $k^{k^{2 r + 1}}$ 。对于初等元胞自动机，邻居个数为 $N = 2$ 。这样的局部规则的映射函数可以写为如下形式：

S_{i}^{t + 1} = f (S_{i - 1}^{t}, S_{i}^{t}, S_{i + 1}^{t})

映射函数中含有三个状态变量，每个状态变量有 2 种状态，输入状态一共有如下8种组合方式。 CA/8 种组合方式.webp 每一个输入条件都对应着两种输出状态 0 或 1 ，一共存在 $2^{8} = 256$ 种状态组合。也就是说，对于一维初等元胞自动机而言，总共存在256种规则。Wolfram在研究这些元胞自动机的时候对他们进行了标号，即将每种输入条件的输出0或1排列看成一个8位2进制数。

例如对于Wolfram的110号规则 CA/110 规则.webp 典型的Wolfram规则还有；254/250/90/30

这里介绍一个相对简单，应用比较广泛的元胞自动机——Wolfram的184号规则：如果在t时刻一个元胞及其右侧邻居是黑色的，或者该元胞是白色且其左边邻居是黑色的，那么该元胞在t+1时刻是黑色的，否则取白色。该模型常常被用来研究车辆交通问题。如果对184号规则赋予车辆交通的含义，黑色表示该元胞被一辆车占据，白色表明该元胞上没有车辆。当t时刻一个元胞是空的，而其左边元胞有车时，t+1时刻其左侧车辆向右行驶，并占据该元胞；如果一个元胞上有车，而其右侧元胞上也有车时，该元胞上的车辆因为前方没有行驶空间而停留在原地不动。 CA/184 规则.webp