关于二维170规则元胞自动机的研究

摘要

元胞自动机（cellular automata,简称CA）是一类特殊的无输出有限自动机，它是由规则排列的元胞组成的离散动力系统，任一个元胞都可被赋值。近年来，元胞自动机在生物学、物理学、密码学等方面都得到了广泛的应用，具有非常强的研究价值。许多国内外学者借助不同的工具对其进行了研究，其中代数工具是当中重要的一个分支。 本文简单介绍了元胞自动机的起源、发展过程、研究方向等基础知识，并对几类二维170规则元胞自动机进行了讨论，用矩阵方法研究它们的一些特性。 本文内容分为四部分，每个部分为一章。 第一章是引言.这部分简单介绍了元胞自动机的基础知识，以及国内外学者利用代数工具对元胞自动机进行研究的一些内容，并给出元胞自动机的基本概念和记号。 第二章是关于零边界条件下170规则（简称170N规则）元胞自动机的研究.这部分利用矩阵的方法对二维170N规则CA的GOE进行讨论，得到一个求它的GOE个数的步骤，并将一维线性元胞自动机的相关理论推广到二维中来，得到一个求二维170N规则CA的瞬时长度和极大圈长的算法。 主要结果： 定理2.1.2 设是一个二维170N规则元胞自动机，是它的任一个位形，若存在可逆矩阵、，使得为对角型矩阵，则是的GOE的充分必要条件是，其中求二维170N规则元胞自动机的GOE个数的步骤： 步骤1 给定 . 算出 . 步骤2 计算，其中是位形通式，记乘积结果为 . 步骤3 对作行、列的初等变换化为对角型，对作相同的行初等变换得 . 步骤4 算出满足条件“，”的的组合数，|GOE|就等于所求得的组合数. 推论2.1.3 设是一个二维170N规则元胞自动机，是非负整数，为正整数（1）当时，若 |GOE|若 |GOE|（2）当时，若 |GOE|若 |GOE|给定、，求二维170N规则元胞自动机的算法为： （1） 对进行标准化，化为标准型（2） 就是的极小多项式，令的最低次数，（3） 若，则，否则（4） （5） 令中系数不为0的项的第二低的次数（6） 若，跳到第（9）步，否则（7） （8） 返回到第（5）步（9） （10） 停止第三章是关于周期边界条件下170规则（简称170P规则）元胞自动机的研究.这部分内容与第二章类似，同样是利用矩阵的方法对170P规则元胞自动机进行讨论，得到相应的结论。 主要结果： 求二维170P规则元胞自动机的GOE个数的步骤： 步骤1 给定，有位形通式，记，其中为阶列矩阵， . 步骤2 当时若为偶数在中，对进行对角化，对作相应的行变换，直到具有下列形式则|GOE|=“使至少有一个的组合数”. 若为奇数在中，对进行对角化，对作相应的行变换，直到具有下列形式则|GOE|=“使的组合数” . 当时 在中，对进行对角化，对作相应的行变换，直到具有下列形式记这一矩阵为则|GOE|=“使的组合数”. 当时 若为偶数 计算出记为①式其中在①式中，对进行对角化，对做相应的行变换，直到变为下列形式记这一矩阵为则|GOE|=“使的组合数”. 若为奇数 计算出记为②式其中在②式中，对进行对角化，对做相应的行变换，直到具有下列形式记这一矩阵为则|GOE|=“使的组合数” . 当给定，求170P规则元胞自动机的的算法与170N规则元胞自动机的类似，只需将其中的步骤（1）换成（1’）： （1’）当时，直接对进行标准化，化为标准型当时，对进行标准化，化为标准型，其中 . 第四章是关于170N和171N混合规则元胞自动机的研究。这部分与第二章类似，同样是利用矩阵的方法对170N和171N混合规则元胞自动机进行讨论，得到相应的结论。 主要结果： 注：此章的矩阵多项式的定义遵循定义4.1.1。 定理4.1.2 设是一个二维170N和171N混合规则元胞自动机，是它的任意一个位形，则E是的GOE ，其中、、、、的定义在预备知识中给出，当为偶数时（即为奇数时） 当为奇数时（即为偶数时） 求170N和171N混合规则元胞自动机的GOE个数的步骤： 步骤1 根据给定 .有位形通式，求出 . 步骤2 算出步骤3 将通过初等变换化成对角形，对实施相同的行初等变换化为 . 步骤4 算出满足条件“”的的组合数，这个组合数就是所要求的GOE的个数. 当给定，求170和171混合规则元胞自动机的的算法与170N规则元胞自动机的类似，只需将其中的步骤（1）换成（1’’）： （1’’）对进行标准化，化为标准型其中 。