二维元胞自动机模型的精确解

王玉芬，汤建钢，唐娜娜

（伊犁师范大学数学与统计学院，新疆伊宁 835000）

0 引言

元胞自动机（Cellular Automata，以下简称CA）是为模拟包括自组织结构在内的复杂现象提供的一个强有力的方法，也称为细胞自动机.据文献［1］，J.Von Neuman n为早期CA的发展作出了很大的贡献，他的这个思想来源于Staislaw Ulam.其目标是设计一个具有通用图灵机那样自我繁殖的人工系统可计算的模型.Staislaw Ulam给出建议后，J.Von Neuman n采用二维元胞空间即CA结构，使用具有29个状态的二维元胞自动机（以下简称2D-CA）建立了一个具有通用计算能力和自我复制特性的CA 模型.后来，Codd 对2D-CA进行简化，使用具有8个状态的2D-CA建立了CA模型［2］.但是，需要庞大数量的元胞单元才能实现这些CA模型，因此难以完成物理实现［3］.后来，由A.W.Burks 完成和扩展了J.Von Neuman n 的研究，完成了物理实现［1］.20世纪80年代初，S.Wolfram提出对CA进行简化，简化后的CA不仅具有复杂的动力学特征，而且还具有能够适合VLSI层次的简单规则结构、信息并行处理的局部互联结构［4］.S.Wolfram对CA的简化极大地推动了CA理论和应用研究的发展.现在CA模型在各个领域的应用和研究都比较广泛.

1 概念

幺正矩阵：如果1个n阶方阵，它的行向量或列向量构成1组标准正交基，那么这个矩阵就是幺正矩阵.

埃尔米特矩阵：埃尔米特矩阵是共轭对称的方阵，矩阵中每一个第i行第j列的元素都与第j行第i列的元素的共轭相等，即矩阵A=[aij]∈Mn称为埃尔米特矩阵，是指A=AT.

自动机：具有离散输入输出的数学模型.

自动机的本质：根据状态、输入和规则决定下一个状态.

元胞自动机模型的关联函数为

2 二维元胞自动机模型的精确解

3 主要结论