一维细胞自动机探索

运行左边的程序 其中Stop按钮暂停 Restart按钮重新开始 状态数：每个细胞有多少个状态 半径：每个细胞的邻居半径 编码：当前细胞自动机的规则编码 类型：编码的类型，长编码还是短编码，具体的说明看下面的内容

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

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

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

（2）规则与编号
    下面考虑规则。假设当前考虑的细胞为c_i，他在t时刻的状态为s_i,t，而它的两个邻居状态为s_i-1,t，s_i+1,t，则c_i在下一时刻的状态为s_i,t+1，则转换规则用函数表示为：

s_i,t+1=f(s_i-1,t,s_i,t,s_i+1,t)

其中，s_i,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个方格，那么下一时刻是白色”可以表示成下面的函数表：

s_i,t+1=1 ，如果s_i-1,t+s_i,t+s_i+1,t=1
s_i,t+1=0 ，如果s_i-1,t+s_i,t+s_i+1,t=2
s_i,t+1=1 ，如果s_i-1,t+s_i,t+s_i+1,t=3
s_i,t+1=0 ，如果s_i-1,t+s_i,t+s_i+1,t=0

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

    这种情况下，输入就仅仅有4种情况，因此可以得到下面的表：

输入	0	1	2	3
输出	0	1	0	1

    同样的道理，我们可以对它进行编码为：0101，表示为十进制就是5。显然，这种编码方式比前一种短，但是这种编码方法不能反映所有的细胞自动机。

（4）最简一维细胞自动机的动态行为
    对于一维的情况，我们假设所有的方格都分布在一条直线上，并且直线的长度为我们动画区域的宽度，比如说是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种。只有复杂的类型才会给我们带来永恒的新奇。
    下面我们自然会思考一个问题，为什么细胞自动机会有这几种类型？它们之间有没有什么联系呢？

混沌的边缘

    运行上面的程序，观察λ的不同，细胞自动机产生的动态行为如何变化。拖动中间的滑块可以更改λ的数值。右边New按钮可以在当前的λ下随机产生新的规则，底下的几个选择框分别更改状态个数、邻居模板个数（注意这个数字包括该细胞自己，比如N=5，那么左边两个细胞，右边两个细胞，再加上中间的细胞，所以邻居半径是2），Isotropic表示规则是不区分左右对称的方格状态的，Anisotropic则是区分的，因此Anisotropic产生的编码比较长，下面的Random Start表示从一个随机的状态开始，Random Clump表示从一个随机的小块开始演化。One Dot Start表示从一个点的初始状态开始演化。下面的文本框里面显示的是当前规则的编码。下面将具体说明其中的原理。

    为了更好的看清楚细胞自动机的动态行为，我们选用4个状态{0,1,2,3}，邻居半径为2（一共4个邻居）的一维细胞自动机来讨论，因为这种细胞自动机包含了所有的四种类别。
    我们知道，在给定了状态集{0,1,2,3}，邻居半径2的一维情况下，细胞自动机的规则集决定了它们的不同。每一个细胞自动机的规则集都可以看成是一张大的转换表，形如：

输入	01203	03120	12231	……
输出	0	1	2	……

    其中每个输入的5位数字串中，中间的一个表示当前细胞的t时刻的状态，两边的数字都是它的邻居状态，而输出则对应当前细胞在t+1时刻的状态。表中一共有4⁵=1024项，这其中有些输出项为0状态，有些不为0，我们把所有输出项为0的个数记为n_q。那么我们可以定义参数：

λ=(4⁵-n_q)/4⁵

    这个参数反映了一组规则中转换成非0状态的比例。显然，根据给定的λ我们可以得到很多的规则表，因此我们可以随机的在这些规则表中选择一个。比如令λ=0.5，那么我们可以随机的生成一个规则组转换表，表的输出部分0状态占据了一半的比例，其他的位置由1,2,3这几个数随机的填充。
    下面看看根据参数λ的取值不同，细胞自动机的动态行为如何变化。请运行上面的程序，让λ在0到1之间变化。

I->II->IV->III，即：固定点->周期->复杂->混沌

    因此我们说，复杂的结构诞生于混沌的边缘。混沌的边缘是什么东西？它是一种处于凝固的周期状态与活跃的混沌之间的一种过渡过程，或者我们称其为“相变过程”。所谓的“相变”就是指系统从量变到质变的飞跃。就像煮开水，当温度达到100度左右的时候，水会突然沸腾，这种状态就是相变，因为从此水由液态变成了气态。
    细胞自动机系统的连续变化过程就好像水的固、液以及固态到液态之间的的变化过程。如下：

I&II->IV->III
固体->相变->液体

    I和II两种状态可以被看作是固态，就像冰一样凝固在一起非常有秩序但同时也没有活性。细胞自动机的第III类型就象是液态的水：完全的流动、随机，没有一个时刻能停留下来，然而由于这类系统过于松散，它也不可能产生有价值的结构。第IV类细胞自动机就刚好存在于从固态的冰到液态的水转变的瞬息之间这么一个狭小的空间里。在这里，复杂的结构形成了神奇的王国，你会不断地看到若干水分子结合成有趣的结构与秩序，但同时这些结构和秩序永远不会被冻结，它们会偶尔被破坏，但新的结构马上又会生成。这样的状态被“人工生命”之父郎顿称为混沌与秩序的边缘。科学家们已经对固体、液体的性质研究的比较清楚了，然而对于固体到液体转变这样一种相变的过程则仍然没有认识足够清楚，原因就在于这样的状态具有太多复杂的结构，我们很难预言它的具体性质。第IV类细胞自动机也是这样，下一时刻细胞自动机会是怎样的情况？我们除了按照它的“物理规律”运行它外别无它法，因为复杂的细胞自动机的行为不能预言。

    我们可以把混沌边缘的概念推广，也就是把秩序、周期这些动态的情况看作是一种凝固的吸引力，它保证了系统能够固定于某一种结构；而另一方面，随机、混沌则形成了另一种张力，它使得系统趋于不稳定，但同时为系统提供了创新的动力。那么仅仅当这两种力处于一种恰到好处的平衡态的时候，也就是系统处于混沌的边缘条件下，该系统才会更加有活力，并且演变得越来越复杂。
    生命从何处来？智能如何产生？人们为什么会创造有组织的同时又具有创新性的社会结构？答案是这些复杂的系统、复杂的结构来自于混沌的边缘。只有当生命所处的环境既不太“热”，即没有太大的动荡产生完全随机的混沌状态，同时又不能太“冷”，以至于所有活动都过于死板，这样才能孕育真正的生命。因此地球上的生命正是诞生于混沌的边缘这条狭窄的夹缝中。再考虑一个人的发展。如果一个人每天都在做同样的事情，从不尝试新鲜的生活，那么这个人所处的环境就过于死板最后将陷于一种机械循环的状态（第I、II类细胞自动机）。反过来，如果这个人过于涣散，总在尝试不同的新鲜事情，从来不会停下来静静的思考和沉淀，那么这个人就会过于灵活而也会一事无成。一个人只有处在“混沌边缘”的状态才能既产生学习、进化的动力，又会静下心来让所学的东西凝固成有价值的知识，从而创造辉煌的成果。再考虑一个国家，闭关锁国肯定不能发展，系统将会变成一潭死水，反过来过于开放则根本不会形成这个国家这个民族的凝聚力也就失去了它们的个性，所以社会也要不停地把自己推向混沌边缘的状态才能不断的发展下去。
    系统为什么总要处于“混沌边缘”的状态呢？比如生命吧，静止于某种固定的状态不是挺好的么？为了适应多变的环境，生命必须不断的进化而变得复杂，而要想变得复杂就必须让自己处于混沌边缘的状态。按照达尔文进化论的观点，不适应环境的生命体就会被大自然淘汰了，并不是每个生命体都有意识的要让自己越来越复杂，而是因为过于简单的生命不能适应环境了，于是它们被淘汰掉了，所以剩下来的仅有那些相对复杂的生命体。科学家曾用一批细胞自动机当作生命体在一个虚拟的自然环境中不断的进化，结果发现，仅有那些不断的趋于混沌边缘的细胞自动机留下来，而其他的细胞自动机逐渐被淘汰出局了。
    对于细胞自动机的分类以及混沌边缘的概念不仅仅适用于一维细胞自动机，对于二维甚至多维的细胞自动机仍然适用。显然我们熟悉的“生命游戏”也正是处于一种“混沌边缘”的状态。经计算，“生命游戏”对应的λ=0.25。

程序及源代码下载：OnedimCA.zip    Edgeofchoas.zip