零边界条件下二维元胞自动机矩阵可逆性分析
Vol, 32，No, 4杭州电子科技大学学报 第 32 卷第 4 期
2012 08 年 月 Journal of Hangzhou Dianzi University Aug, 2012 do: 10, 3969 / , ssn, 1001 , 9146, 2012, 04 , 036iji 零边界条件下二维元胞自动机矩阵可逆性分析 ，刘碧川吴秋轩
( )，310018杭州电子科技大学自动化研究所浙江 杭州
: ，摘要该文介绍了二维元胞自动机的典型邻域结构对多状态二维元胞自动机的矩阵描述进行了
。，拓展通过对零边界条件下元胞自动机的状态转移矩阵的块矩阵的分析得出矩阵的可逆性与元
。胞自动机冯诺依曼型邻域之间的联系
: ; ; ?关键词二维元胞自动机冯诺依曼型邻域可逆性
: TP301, 1: A: 1001 , 9146( 2012) 04 , 0137 , 03中图分类号文献标识码文章编号
0 引言
、，，元胞自动机是定义在一个由具有离散有限状态的元胞组成的元胞空间上并按照一定局部规则
。，在离散的时间维上演化的动力学系统元胞自动机理论自提出以来得到了长足的发展开始只是对元,1,，胞自动机进行了探索性的研究逐步将建立在矩阵代数中的一维元胞自动机扩展到二维元胞自动 ,2,,3,，9 ，机而后对 邻域结构的二维元胞自动机进行了研究并且对二维元胞自动机的等效转移矩阵特 ,4,。，性进行了
初步的分析本文在其研究基础上对矩阵的可逆性研究进行一些探索在一定程度上增进
。了二维元胞自动机的矩阵特性的理论发展 1 二维元胞自动机
，二维元胞自动机的元胞分布在二维网格中元胞下一时步的状态取决于当前元胞和其相邻元胞的
( ，) t + 1 q q( t + 1)( t) ，。9 ，i j= f,q状态对于 相邻元胞结构第个元胞在 时步的状态 可表述为 i，j i , 1，j , 1
q( t) ，q( t) ，q( t) ，q( t) ，q( t ) ，q( t ) ，q( t ) ，
q( t ) ,，f 其中 表示局部 i , 1，j i , 1，j + 1 i，j , 1 i，j i，j + 1 i + 1，j , 1 i + 1，j i + 1，j + 1
。规则
，，，元胞自动机中演化规则是定义在空间局部范围内的因而在指定规则之前必须定义一定的邻域 。Von ，Moore 规则以最常用的规则四方网格划分为例二维元胞自动机的常用的邻域结构主要有 型和
Neumann ，1( a) 、( b) 。型分别如图 所示
，。Moore 8 中心元胞表示当前元胞周围元胞表示其相邻元胞型邻域结构由当前元胞和 个相邻元 ，Von Neumann 5 。胞组成型邻域结构由当前元胞和其上下左右共计 个元胞构成网格中的数字则表示
，Rue 1 ，Rue 32 ll其规则号如 表示当前元胞只受其本身的影响则表示当前元胞只受到其左边元胞的影 。( a) 9 。1，响图 中这 个规则称为基础规则若当前元胞受到两个或多个元胞的影响则规则号表示为几
( ) ，Rue 170 ( 128 + 32 + 8 + 2 ) l个基础规则号的代数和只考虑线性规则如常用的 表示当前元胞受到上 4 。下左右 个相邻元胞的影响
: 2010 , 06 , 10收稿日期
: ( Y1090353)基金项目浙江省自然科学基金资助项目
: ( 1990 ,) ，，，，,作者简介刘碧川男河南驻马店人在读研究生自重构机器人
1 图 二维元胞自动机邻域结构 2 二维元胞自动机的描述矩阵
×n 。m ，二维元胞自动机在任一时步的状态均可用 阶位信息矩阵来表示为便于分析将转移规则
3，5 mn ×m n M，X，按文献 中所述等效为 阶矩阵 初始状态中每一行进行转置成 则下一时步状态 mn × 1 Y= MX。{ 0，1} ，MX 2，3 …，若元胞仅有两个状态但 会产生不属于这个状态集中的 状态这是 mn × 1 mn × 1
，，由于实际中当前元胞的状态是由其相邻元胞状态异或得到的而在数学表达式中却是简单的相加故准
，Y = MX mod 2。{ 0，1，2，…，k ,1 } ，k ，确来讲下一状态 由此可推得对于 个有限状态的元胞自动机其
Y = MX mod k，X ，M 。下一状态 其中 为当前状态为元胞规则的等效矩阵 M = ，M ，在零 边 界 条 件 下二维元胞自动机的等效转移矩阵 为 三 对 角 矩 阵即U 0 0 0 0 0 D ，， , , L D U 0 …0 0 0 , , L D U 0 0 0
零边界条件下二维元胞自动机矩阵可逆性分析
