| （1）最简一维细胞自动机
最简单的一维细胞自动机的状态集合为两个元素{0,1}。邻居是一个半径为1的区域，也就是每一个方格的左、右两个方格是它的邻居，这样每一个方格单元和它的邻居可以表示如下：
黑色的方格是当前细胞，两边的灰色方格是它的邻居。由于状态集只有{0，1}两个状态，也就是说方格只能有黑、白两种颜色，那么任意的一个方格加上它的两个邻居，这3个方格的状态组合一共就有8种。这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。这样，任何一个规则就是一个或者一组转换，比如下图表示的就是一个规则：
这个规则也可以列为下面的表：
| 输入 |
111 |
110 |
101 |
100 |
011 |
010 |
001 |
000 |
| 输出 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
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种。只有复杂的类型才会给我们带来永恒的新奇。
|
