元胞自动机

浅蓝爱

元胞自动机的原理及其应用

空空火柴盒

　　元胞自动机是一个空间、时间和状态上都离散的动态系统。构成CA的基本单位成为元胞（cellular），规则的分布在元胞空间（spatial lattice）的格点上，且各自的状态随着时间按照一定的局部规则变化。也就是说，元胞的状态只能从一个有限的状态集中取值，每个时刻元胞的状态仅与其自身和邻居在上一时刻的状态有关，并且，所有的元胞在每个时刻均是同时更新的。大量元胞通过简单的相互作用而构成动态系统的演化。
　　下面给出一个基于集合论的定量描述（L. Hurd等）：
 设d为CA空间的维数，k代表元胞的状态，集合S表示CA的整体状态，r表示元胞的邻居半径。为了简单起见，我们在d=1，即一维空间上对CA进行讨论。CA的动态性可以由一个全局函数F: St→St+1决定，并且，每个元胞的状态可以由一个局部函数f:kt→kt+1决定。
 由于多维空间的CA具有很强的复杂性，故目前对CA的研究主要集中在一维和二维空间。就一维空间而言，CA的结构显然只有可能是线性结构。在二维空间，CA的结构可能有三角、四边或多边等构成方式。