元胞自动机基础 元胞自动机（cellular automaton, CA）是最近一个比较热门的研究课题，其是物理、数学、计算机和生物等学科的交叉产物
在计算机领域中，CA 在人工智能、计算复杂性分析以及加密等多个领域中有着较大的用途
特别是在大约十年前，密码学家H
Gutowitz根据 CA 的基本原理，提出了分块加密算法CA-1
1，使得 CA 在密码学中真正的迈出了第一步，也使得越来越多的密码学家开始了对 CA 的研究
最近，我也开始对这个方面产生了浓厚的兴趣，并开始了一些学习，就先来简单的说说什么是CA 吧
简单的说，元胞自动机是一个空间、时间和状态上都离散的动态系统
构成CA 的基本单位成为元胞（cellular），规则的分布在元胞空间（spatial lattice）的格点上，且各自的状态随着时间按照一定的局部规则变化
也就是说，元胞的状态只能从一个有限的状态集中取值，每个时刻元胞的状态仅与其自身和邻居在上一时刻的状态有关，并且，所有的元胞在每个时刻均是同时更新的
以上即是对 CA 的一个定性的描述，下面给出一个基于集合论的定量描述（L
Hurd 等）： 设 d 为 CA 空间的维数，k 代表元胞的状态，集合 S 表示 CA 的整体状态，r 表示元胞的邻居半径
为了简单起见，我们在d=1，即一维空间上对 CA 进行讨论
CA 的动态性可以由一个全局函数F: St→St+1 决定，并且，每个元胞的状态可以由一个局部函数 f:kt→kt+1 决定
由于多维空间的CA 具有很强的复杂性，故目前对CA 的研究主要集中在一维和二维空间
就一维空间而言，CA 的结构显然只有可能是线性结构
在二维空间，CA 的结构可能有三角、四边或多边等构成方式
显然，结构上的差异会对其在计算机表示及其他部分特性上带来一定的差异
而 CA的邻居结构也通常包括Von
Neumann、
