细胞自动机查看源代码讨论查看历史

原图链接来自 知乎 的图片

细胞自动机（cellular automata）是为模拟包括自组织结构在内的复杂现象提供的一个强有力的方法，也称为元胞自动机（Cellular Automaton）。细胞自动机模型的基本思想是：自然界里许多复杂结构和过程，归根到底只是由大量基本组成单元的简单相互作用所引起。细胞自动机主要研究由小的计算机或部件，按邻域连接方式连接成较大的、并行工作的计算机或部件的理论模型。它分为固定值型、周期型、混沌型以及复杂型。

相关内容

为了理解细胞自动机，可看一个简单例子：找一张画有许多格子的图纸，用铅笔涂黑其中一些格子就可得到一个图案（样式）。第一排也许有一个或几个格子被涂黑了，而一个简单的细胞自动机是确定某种简单的规则，从第二排开始往下画出新图案来。具体到每一行中的每一个格子，要观察其上一行的对应格子及该对应格子两边的情况，然后根据这三个格子是否被涂黑，以及黑白格子如何相邻的已定规则（比如，当这三个格子从左至右分别为黑、黑、白时，其正下面的格子为白，否则为黑），确定当前的格子是涂黑还是留白。如此反复进行下去。一条或一组这样的简单规则及简单的初始条件就构成了一个细胞自动机。

细胞自动机论主要研究由小的计算机或部件，按邻域连接方式连接成较大的、并行工作的计算机或部件的理论模型。

诺伊曼细胞空间的所有细胞都在整数网格的结点上，细胞个数为无限。它满足下列条件：各个细胞都是确定的摩尔型有限自动机；采取五邻域一致连接模式（所有细胞有同样形状的邻域）；不带外部输入，不向外部输出；并且是静态的（邻域不随时间改变）。一般的细胞空间不必要这些条件限制，故此外还有非确定型细胞空间、米雷型细胞空间、连接模式非一致的细胞空间、带外部输入的细胞空间以及动态的细胞空间等。

棋盘格空间是细胞空间的一个直接推广。它有分配到各个细胞的统一的外部输入。或者说，棋盘格空间是一个程序控制的细胞空间。棋盘格空间里的每一个细胞能够被想象为有一个局部转移函数的有限集合。因此，棋盘格空间有一个全局转移函数的有限集合。程序中的各个“指令”选择在该时刻的转移中所使用的全局转移函数。

绝大多数细胞自动机产生的都不过是乏味的单调图案，但有一些却大出人们的意料之外。

分类

（1）最简一维细胞自动机

最简单的一维细胞自动机的状态集合为两个元素{0，1}。邻居是一个半径为1的区域，也就是每一个方格的左、右两个方格是它的邻居，这样每一个方格单元和它的邻居可以表示如下：

黑色的方格是当前细胞，两边的灰色方格是它的邻居。由于状态集只有{0，1}两个状态，也就是说方格只能有黑、白两种颜色，那么任意的一个方格加上它的两个邻居，这3个方格的状态组合一共就有8种。

他们表示的状态分别是：111，110，101，100，011，010，001，000。也就是说对于状态数为2，邻居半径为1的所有一维细胞自动机的邻居和其自身的状态组合就这8种。

（2）规则与编号

下面考虑规则。假设当前考虑的细胞为ci，他在t时刻的状态为si，t，而它的两个邻居状态为si-1，t，si+1，t，则ci在下一时刻的状态为si，t+1，则转换规则用函数表示为：

si，t+1=f(si-1，t，si，t，si+1，t)

其中，si，t∈{0，1}，对于任意的i和t

由于在我们这个最简单的细胞自动机中每个细胞和它的邻居状态的所有可能组合就上面列出来的8种，所以它的输入就是上面列出的8种组合之一，输出表示的是每个细胞下一时刻的状态，而状态只可能有0、1两种，则规则的输出要么是0，要么是1。这样，任何一个规则就是一个或者一组转换，

那么这组规则就对应着编码：10100011，也就是把八个位置上的方格进行一个排列。我们可以把输出部分的二进制编码转换成十进制数的形式：163，这就是该细胞自动机的编码。当状态数增多，半径增大的时候，这种编码方式就不实用了，我们需要用另一种方式来编码。考虑下面这样的规则若有一个规则是：“如果输入的三个方格中黑色方格只有1个，那么下一时刻当前方格就是黑色；如果有两个黑色方格，则下时刻是白色，如果有三个方格，则下时刻是黑色，如果有4个方格，那么下一时刻是白色”可以表示成下面的函数表：

si，t+1=1 ，如果si-1，t+si，t+si+1，t=1

si，t+1=0 ，如果si-1，t+si，t+si+1，t=2

si，t+1=1 ，如果si-1，t+si，t+si+1，t=3

si，t+1=0 ，如果si-1，t+si，t+si+1，t=0

其中，si，t∈{0，1}，对于任意的i和t 这种情况下，输入就仅仅有4种情况，因此可以得到下面的表：同样的道理，我们可以对它进行编码为：0101，表示为十进制就是5。显然，这种编码方式比前一种短，但是这种编码方法不能反映所有的细胞自动机。

（3）最简一维细胞自动机的动态行为

对于一维的情况，我们假设所有的方格都分布在一条直线上，并且直线的长度为我们动画区域的宽度，比如说是400，也就是说有400个方格在这条直线上。我们用黑色的格表示直线上1状态的方格，用白色的格表示0状态的方格。那么一条断续的横线就是当前所有细胞状态的一种分布。这些方格随着时间变化，就形成了不同的横线。我们把这些随着时间变化的线纵向拼在一起形成了一个网格区域。其中纵轴表示时间的流逝（往下为正），横轴为细胞自动机在对应时刻的状态，就能得到一幅图像。这就是上面的示例程序所表演的，变换不同的编码参数，你会看到，观察它们的动态行为。

在最简细胞自动机的情况下（状态数是2，半径是1），这些细胞自动机分成3类。观察224号（长编码）细胞自动机，从上而下出现了一些细胞，之后就逐渐变成了全白色，也就是说经过几个时间步的运行后，细胞自动机全部变为了固定状态0（也就是白色的方格），并再也不变化了。而132号和203号细胞自动机都是变成了几个竖线。不要忘了每一行就是某一时刻细胞自动机的一个状态，因此在竖向上能够形成一条竖线就说明这个细胞的状态在时间轴上没有变化。所以132号、203号与224号它们被吸引到了一个固定的状态。

再看208号细胞自动机，它是若干条斜的线。由于我们的边界是循环的，因此可以预言，经过若干个时间周期的运行以后，细胞自动机又回复到了原来的状态，因而这样的细胞自动机是循环的。两个相同状态之间经历的时间步长为这种细胞自动机的周期。再看150号和151号细胞自动机，他们显然既没有固定的周期也没有被吸引到一个点，它们是出于一种混乱的、无序的状态，我们称这种状态为混沌状态。通过反复的运行最简细胞自动机程序我们不难发现，所有的256种细胞自动机都能被归为这三类：固定值、周期循环、混沌之一。

我们可以猜想，是不是所有的细胞自动机的动态行为就这三种类型呢？让我们把探索的疆域扩大到稍微复杂一点的情况，我们考虑状态数为2，邻居半径为2（也就是说每个细胞都有4个邻居，左右两边各两个），仍然是一维的情况。在这样的细胞自动机中除了上面叙述的三种类别依然存在外，我们还发现了另一种类型，请看20号（按照短编码方案）和52号（按照短编码方案）这两个细胞自动机的动态运行图竟然如此怪异，就好像一棵倒挂的葡萄藤。这种葡萄藤是一种复杂的结构，它既不等同于完全的随机，又没有固定的循环的迹象。这种复杂结构正是我们感兴趣的一种类型，因为它既没有被吸引到固定的点或周期状态而变得死板，又没有因为随机而过于活跃；它既保证了一定的流动活性，同时又能产生具有“记忆性”的结构。该运行情况显然不同于前面叙述的三种类别，所以我们称其为复杂型。继续运行各种参数的一维细胞自动机，我们发现几乎所有的一维细胞自动机运行的动态行为都能被划分为这四类情况。

综合上面的讨论，我们把细胞自动机归为四种类别，它们分别是：

I、 固定值型：细胞自动机经过若干步运算便停留在一个固定的状态；

II、 周期型：细胞自动机在几种状态之间周期循环；

III、 混沌型：细胞自动机处于一种完全无序随机的状态，几乎找不到任何规律；

IV、 复杂型：细胞自动机在运行的过程中可能产生复杂的结构，这种结构既不是完全的随机混乱，又没有固定的周期和状态。

上面我们仅仅就一维细胞自动机的情况作了介绍，二维细胞自动机也无非就是这4种情况之一。其实我们想一下，前面介绍的“生命游戏”属于哪种类型呢？当然应该是第IV种。只有复杂的类型才会给我们带来永恒的新奇。

意义

细胞自动机不仅可以在形式上作为并行计算机的理论模型来研究，而且还可以作为语言（被机器接受的输入字的集合）识别器。一个语言被某种识别器所识别是指：识别器不仅接受该语言中的字，而且拒绝不属于该语言中的字。在维数高于1时，语言识别有时被看作模式识别。对于迭合自动机，如果每一时间步只输入一个字母，当字全部输完之后，如果输入输出细胞进入一个特别设计的接受状态，就认为它接受了这个字。语言的所有的字都被接受时就称为迭合自动机语言。类似地，棋盘格自动机和一维细胞自动机也可以用作语言接受器。

用细胞自动机的并行计算方式可实现一些并行计算机和识别器的设计。细胞自动机对于集成电路的设计方法具有重要意义。大规模集成电路采用细胞阵列形式具有明显的优点。生物学推动了有关自动机的理论研究。反过来，有关自动机理论的发展为生物发育学提供了一种数学模型和方法。细胞自动机论的研究与形式语言的研究更是息息相关，各种细胞自动机的识别能力，以及它们所能识别的各种语言类与各类形式语言之间的关系都还处于探讨中。另外，各种类型细胞自动机的性质，以及它们彼此之间的关系也都是人们关心的课题

视频

细胞自动机 相关视频

生命游戏、细胞自动机 C/C++游戏开发教程：生命游戏（细胞自动机）！黑暗森林法则实战