论文部分内容阅读
【摘 要】本文总结了经典元胞自动机模型理论，并在此基础上定义了初等元胞自动机的减法规则，引入代数方法探讨了初等元胞自动机在其中一种减法规则下的演化性质，由此推出了一些相关性的结论。这些性质结论是初等元胞自动机在其减法规则下所特有的，使其在模拟事物时更具有方向性，不但丰富了初等元胞自动机的理论，而且为我们研究元胞自动机的理论提供了可行的方案。为了便于直观的验证某些结论，我们利用了初等元胞自动机的状态迁移图来加以描述它的演化过程。初等元胞自动机在其它减法规则下的演化可以用类似的手段来研究。
【关键词】元胞自动机；演化规则；邻居；状态
1.引言
元胞自动机（又称细胞自动机，点格自动机，简记为CA）是一种有自组织行为的时空离散、状态离散的并行数学模型，即使从无序的状态开始，它也可以演化出有序的结构。经典的元胞自动机理论由Von Neumann在上世纪五十年代中期建立[1]，后来又由Stephen Wolfram发展了这一理论[2，3]。它作为一种数学模型可以对许多行为进行仿真。元胞自动机理论的主要目的是根据现实世界中的真实行为建立CA模型，根据CA的演化结果，给出要解决问题的定性分析。从八十年代开始，研究工作的主要特点是对CA模拟的近似分析。目前，元胞自动机理论已经被广泛的应用到许多学科，如生物仿真，灾害模拟，交通控制与管理，地理信息系统，信号处理和图像处理等[4， 5， 6]。
其中初等元胞自动机是结构最简单的元胞自动机，它是我们研究其它元胞自动机模型的基础。在本文我们定义了初等元胞自动机的减法规则，并用代数方法来研究其演化过程，导致由其所引发的性质结论产生，丰富了初等元胞自动机的演化方法和结果。第二部分介绍了经典的元胞自動机模型，第三部分给出了初等元胞自动机在减法规则下的代数演化方法和相关性的结论，第四部分是本文的结论。
2.元胞自动机模型
2.2对于减法规则150的讨论
表2对应着规则150，那么用语言描述如下：元胞自动机在下一个时间步中的每个元胞是其上一个时间步中它本身与其左右两个邻居元胞代数差的绝对值，若用ai（t）表示在时间步t中的元胞值，那么规则150就可以由
3.结束语
在这里所探讨的规则150只是减法规则其中的一种，其它减法规则我们也可以采用类似的研究方法进行探讨。每种减法规则的前四个字符与后四个字符不是相同就是相反。所谓的相同就是不变，相反就是指0→1；1→0。初等元胞自动机及其减法规则的多项式表示法所揭示出的规律是外部的，通过本文我们可以发现应用代数手段来研究元胞自动机不但直观而且方便。我们已经在元胞自动机和多项式之间建立起了联系，能够通过和利用我们所熟知的多项式性质来分析元胞自动机的相关演化性质。通过本文的讨论我们已经清楚的认识到了初等元胞自动机在减法规则的演化下所展示出的其它普通规则所不具备的复杂特点，为元胞自动机模型的构造及演化提供了好的方法。
参考文献：
[1]Wolfram， S.： Statistical mechanics of cellular automate. Rev. Mod. Phys. 55，601（1983）.
[2]S.Wolfram，O.Martin，and A.M.Odlyzko：Algebraic Properties of Cellular Automate（1984）.
[3]Wolfram，S.： Computation Theory of Cellular Automata. Commun. Math. Phys. 96. 15-57 （1984）
[4]Knuth， D.： Fundamental algorithms， A. W. Burks. Univ. of numbers. Oxford： Oxford University. Press （1968）
[5]Griffiths ，P.， Harris，J.： Principles of algebraic geometry. New York： Willy （1978）.
[6]Harao， M. and Noguchi， S.： On some dynamical properties of finite cellular automaton.IEEE Trans. Comp. C-27，42 （1978）.
【关键词】元胞自动机；演化规则；邻居；状态
1.引言
元胞自动机（又称细胞自动机，点格自动机，简记为CA）是一种有自组织行为的时空离散、状态离散的并行数学模型，即使从无序的状态开始，它也可以演化出有序的结构。经典的元胞自动机理论由Von Neumann在上世纪五十年代中期建立[1]，后来又由Stephen Wolfram发展了这一理论[2，3]。它作为一种数学模型可以对许多行为进行仿真。元胞自动机理论的主要目的是根据现实世界中的真实行为建立CA模型，根据CA的演化结果，给出要解决问题的定性分析。从八十年代开始，研究工作的主要特点是对CA模拟的近似分析。目前，元胞自动机理论已经被广泛的应用到许多学科，如生物仿真，灾害模拟，交通控制与管理，地理信息系统，信号处理和图像处理等[4， 5， 6]。
其中初等元胞自动机是结构最简单的元胞自动机，它是我们研究其它元胞自动机模型的基础。在本文我们定义了初等元胞自动机的减法规则，并用代数方法来研究其演化过程，导致由其所引发的性质结论产生，丰富了初等元胞自动机的演化方法和结果。第二部分介绍了经典的元胞自動机模型，第三部分给出了初等元胞自动机在减法规则下的代数演化方法和相关性的结论，第四部分是本文的结论。
2.元胞自动机模型
2.2对于减法规则150的讨论
表2对应着规则150，那么用语言描述如下：元胞自动机在下一个时间步中的每个元胞是其上一个时间步中它本身与其左右两个邻居元胞代数差的绝对值，若用ai（t）表示在时间步t中的元胞值，那么规则150就可以由
3.结束语
在这里所探讨的规则150只是减法规则其中的一种，其它减法规则我们也可以采用类似的研究方法进行探讨。每种减法规则的前四个字符与后四个字符不是相同就是相反。所谓的相同就是不变，相反就是指0→1；1→0。初等元胞自动机及其减法规则的多项式表示法所揭示出的规律是外部的，通过本文我们可以发现应用代数手段来研究元胞自动机不但直观而且方便。我们已经在元胞自动机和多项式之间建立起了联系，能够通过和利用我们所熟知的多项式性质来分析元胞自动机的相关演化性质。通过本文的讨论我们已经清楚的认识到了初等元胞自动机在减法规则的演化下所展示出的其它普通规则所不具备的复杂特点，为元胞自动机模型的构造及演化提供了好的方法。
参考文献：
[1]Wolfram， S.： Statistical mechanics of cellular automate. Rev. Mod. Phys. 55，601（1983）.
[2]S.Wolfram，O.Martin，and A.M.Odlyzko：Algebraic Properties of Cellular Automate（1984）.
[3]Wolfram，S.： Computation Theory of Cellular Automata. Commun. Math. Phys. 96. 15-57 （1984）
[4]Knuth， D.： Fundamental algorithms， A. W. Burks. Univ. of numbers. Oxford： Oxford University. Press （1968）
[5]Griffiths ，P.， Harris，J.： Principles of algebraic geometry. New York： Willy （1978）.
[6]Harao， M. and Noguchi， S.： On some dynamical properties of finite cellular automaton.IEEE Trans. Comp. C-27，42 （1978）.