虽然这类图形和上一个复杂混乱的模型很相似,但是,它们是分属两种现象的。至此,我们就分析出了一维细胞自动机的四种现象,也就是沃夫拉姆拉姆所提出的四种分类。
1 CA在有限的时间内从初始状态演化到一个均质的状态,不管是什么初始值,细胞会收敛到一个稳定的模式。如果我们从程序上面观察,就会发现,每一行的细胞状态都是一样的,或者是生或者是死。
2 这类的CA通常会演化到周期性的循环模式。周期有长有短,2个交互的模式出现的的频率较大。
3 这类细胞自动机从任何初始状态开始,都会出现一种非周期的模式,或者叫做”混沌”模式。它的特点是,没有均质的状态出现,也没有明显的周期性呈现。看起来他的后续状态都是随机的。但是,只要时间足够多,我们就可以发现,他的统计特性非常相似。
4 这种类型的细胞自动机呈现出一种奇异的复杂的模式,但它不像第三种类型,它能呈现局部的稳定结构和有规律变化的结构。更为值得关注的是,它能够产生能在一维或者二维空间上持续转播的结构。
基于上面的分析,我们知道,第一和第二种类型的CA模式过于单一和稳定而失去了研究的价值。第三种类型我们也能高度的预测它的后续模式。所以,在这四种状态中,最值得我们研究的,就是第三种CA。
沃夫拉姆指出,和其他领域的分类一样,每一个类别都存在边界的情况。有一些CA,它既能分都某一类,同时也能划分为另外一类。但是这种CA的数量很少,为了简单起见,我们的研究不涉及到这一类的CA。
通过反复的运行初等细胞自动机的程序我们不难发现,所有的这256种细胞自动机都能被归为这四类。
如果我们做更深一步的思考,这所谓的混沌型和复杂型,虽然表面上看起来没有周期。但是,何以料定经过成千上万个时间步之后,不会变得有周期呢?其实,有这样一个事实:如果细胞空间是有限的,细胞状态数为2,那么细胞自动机演化必然呈现周期型变化。证明如下:
我们假设初始行的细胞的数量是有限的,比如说5个。那么这个行能演化达到的状态数最多只有2的5次方也就是32个。即使它的前32步演化得到的32个构型各不相同,但是它在演化的第33步,必然回到了一个在前32步里以前曾经到达过的状态,比如说第6步。一旦回到这个状态,那么它的下一步演化的结果必然也和第7步一样。以此类推,它就变成周期型了。因此得出结论,任何一个细胞空间有限的细胞自动机都会穷尽其所有可能而回到循环状态。实际上,这个结论也适用于任何有限的离散动力系统。
但是,我们在程序中进行模拟,画布的宽度不可能取无限大,也就是细胞空间总是有限的,所以我们可以说实际上,在模拟结果中,不存在真正的混沌型和复杂型。
然而为什么又要把混沌型和复杂型单独归纳出来呢?因为在实际中,有限细胞自动机的可能性空间随着细胞空间的扩大呈指数增长。比如100个网格的细胞自动机要穷尽一遍可能性需要2^100步骤,大概是1后面跟30个0,对于这种大数目的可能状态,虽然它肯定是有限的,然而我们已经可以认为穷尽可能性不可能了。在用程序进行模拟的时候,只要初始个数达到一定大小,我们就认为已经足够模拟真实世界了。从而我们说,混沌型和复杂型,是相对于那种少量几步就开始循环的周期型来说的。
还有一点要说明的是,我们的程序设置了初始构型是随机生成的。在某些特殊的初始构型下,有可能110号规则也得不到第4类的行为。沃夫拉姆用实验验证了这一点。总之,初始构型也对细胞自动机的行为有一定影响。实际上,对于第4类细胞自动机来说,通过适当的构造初始构型,它可以模仿其它几类行为。
虽然当时沃夫拉姆已经把CA分成了这四类,但是,他并不清楚这四类的CA之间的关联是什么。是什么决定了某一个特定的规则属于某个类别。
我们现在虽然不能证明沃夫拉姆的分类是否合理、正确。至少,我们可以用一维细胞自动机的模型做实验,证实了确实有这四种类型的存在。下面,再对兰顿提出的复杂系统相变的调节参数进行分析和实验。
3.2 复杂系统相变的调节参数
在许多真正的非线性系统中,运动的方程式中包含了很多的参数。这些参数起着调节的作用。就是这些参数决定了系统的状态,也就是”混沌”的程度。比如,如果这个系统是个滴水的龙头,其参数就是水流的流速。或者,如果这个系统是兔群,其参数就会是兔子的出生率和因繁殖过多而造成的死亡率之间的比值。一般来说,小参数值通常导致稳定的行为:均速水滴、不变的兔群规模,等等。这与沃夫拉姆的第一和第二等级的停滞行为非常相似。但当参数越变越大时,这个系统的行为就会变得越来越复杂——不同大小的水滴、波动的兔群规模,等等——一直到最后变得完全混乱。到这个时候,这个系统的行为就是沃夫拉姆的第三等级。这些非线性连续系统中却没有第四等级。尽管如此,这些非线性系统与沃夫拉姆的等级之间的却如此类似,这就促使很多学者开始沿着这一思路,试图寻找到这一参数。最终,当时还在密歇根大学攻读博士学位的美国学者兰顿(Christopher Langton)如愿以偿,并以此成果作为其博士范文。
对于一维细胞自动机,他找到的参数如下:
现假设每个细胞具有k种状态(状态集为Σ),每个细胞的邻域集合的元素个数为n,则共存在kn种邻域状态,如一维细胞自动机,当某个细胞只能有两种状态且它的邻居是2时,它自身和邻居(邻域)就有23 种状态。选择k种状态中任意一种s∈Σ并称之为静态sq,静态状态可任意选择,如100或者101。假设对转换函数而言,共有nq种变换将邻域映射为该静态,剩下的kn-nq种状态被随机地、均匀地映射为Σ-{sq} 中的每一个状态,则可定义:
这样,对任意一个转换函数,定义了一个对应的参数值λ。
为了理解兰顿的思路,进一步弄清楚λ这个参数的含义,我们先来了解一下基本的CA概念,使用最熟悉的二维细胞自动机来说明。假设每一个细胞允许的状态是K,他有N个邻近的细胞(注意,N包括这个细胞自身)。那么,我们可以得到K=2,N=9;那么在我们的二维细胞自动机中,每一个细胞都处于2的9次方也就是512个状态当中的一个。但是,生命游戏中每一个细胞的转换规则只依赖他邻居的状态的个数,而对位置不敏感,所以,我们的规则远比512这个数目要少的多。极端的,可以定义512条规则对细胞自动机进行约束。
对于生命游戏,假设当前的细胞是活的,如果它具有2到3个活的邻居,那么,在下一代,他就能继续存活。由于它有8个邻居,所以一共存在C+C=84种情况。假设当前的细胞是死的,如果他周围有三个活的邻居,下一代就能产生一个细胞。这种情况是C=56种,因此,上一代的两种概率加在一起,从特定的一代到达下一代,细胞是活状态的情况一共有84+56=140(上一代的细胞有生和死两种状态,这两种状态下产生活的下一代细胞的概率应分别计算,然后加在一起。
)种。我们就可以得出生命游戏的λ值是140/512=0.273.
兰顿用不同的λ值做了一系列的实验,发现,沃夫拉姆的四种