元胞自动机理论基础 3

森之张卫东

Chapter3

尽管元胞自动机有着较为宽松，甚至近乎模糊的构成条件。但作为一个数理模型，元胞自动机有着严格的科学定义。同时，元胞自动机是一个地地道道的"混血儿"。是物理学家、数学家，计算机科学家和生物学家共同工作的结晶。因此，元胞自动机的含义也存在不同的解释，物理学家将其视为离散的、无穷维的动力学系统;数学家将其视为描述连续现象的偏微分方程的对立体，是一个时空离散的数学模型;计算机科学家将其视为新兴的人工智能、人工生命的分支;而生物学家则将其视为生命现象的一种抽象。下面给出几种常见的定义:

1.元胞自动机的物理学定义

元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。

具体讲,构成元胞自动机的部件被称为"元胞"，每个元胞具有一个状态。这个状态只取决有限状态集中的一个，例如或"生"或"死"，或者是256中颜色中的一种，等等;这些元胞规则地排列在被你为"元胞空间"的空间格网上;它们各自的状态随着时间变化。而根据一个局部规则来进行更新，也就是说，一个元胞在某时刻的状态取决于、而且仅仅取决于上一时刻该元胞的状态以及该元胞的所有邻居元胞的状态;元胞空间内的元胞依照这样的局部规则进行同步的状态更新，整个元胞空间则表现为在离散的时间维上的变化。

2.元胞自动机的数学定义

美国数学家L.P.Hurd和K·Culik等人在90年代初，对元胞自动机分别从集合论和拓扑学等角度进行了严格地描述和定义(谢惠民，1994; Culik,II K，1990;李才伟,1997)

1)基于集合论的定义

设d代表空间维数，k代表元胞的状态，并在一个有限集合S中取值，r表元胞的邻居半径。Z是整数集，表示一维空间，t代表时间。

为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d=1。那么整个元胞空间就是在一维空间，将整数集Z上的状态集S的分布，记为SZ。元胞自动机的动态演化就是在时间上状态组合的变化，可以记为:

file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png

这个动态演化又由各个元胞的局部演化规则f所决定的。这个局部函数f通常又常常被称为局部规则对于一维空间，元胞及其邻居可以记为S2r+1，局部函数则可以记为:

file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image004.png

对于局部规则f来讲，函数的输入、输出集均为有限集合，实际上。它是一个有限的参照表。例如，r=1，f的形式则形似如下:[0,0,0]->O; [0,0,1]->0;[0,1,0]->1; [1,0,0]->0; [0,1,1]->1; [1,0,1]->0; [1,1,0]->0;[1,1,1]->0对元胞空间内的元胞，独立施加上述局部函数，则可得到全局的演化:

file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image006.png

cit表示在位置i处的元胞，至此，我们就得到了一个元胞自动机模型。

2)元胞自动机的拓扑学定义

为描述和理解方便。同样假定维数d为1。设S为k个符号约有限集。Z为整数全体的集台，称Z到S的映射的全体SZ为构形空间。显然SZ就是用S中的符号组成的双侧无限的符号序列的全体，即一维元胞自动机的所有构形的集合。称a=(…a-1a0a1,...)为构形空间中的点。

在SZ中引进任意两点x和y之间的距离

file:///C:/Users/lx/AppData/Local/Temp/msohtmlclip1/01/clip_image008.png

其中当xi=yi时δ(xi,yi)=0，当xi≠yi时δ(xi,yi)=1。然后。在SZ中可以建立起开、闭、紧等拓扑概念。

在SZ中定义移位算子δ为δ(xi)=xi-1，i∈Z。若连续映射F:SZ->SZ产与δ可交换，即Fδ=δF。或对任意的x∈SZ有F((δ(x))=δ(F(x))，则称F为元胞自动机 (谢惠民，1994)。

对于以上定义，我们很容易将它扩展到一个任意维空间，所要做的工作只是将SZ记为SZ^d，S2r+1记为S(2r+1)^d等，同时对一些描述作相应改变即可。