复杂Bernoul1i移位细胞自动机的动力学研究
|
摘要
细胞自动机作为一种特殊的数学模型，其实质是一类时间、空间和状态都离散的复杂系统。二十世纪四、五十年代John von Neumann和Stanislaw Ulam在研究生命系统的自我复制现象时推断局部迭代简单动力系统有可能产生非常复杂的动力学现象，从此细胞自动机及其相关理论受到许多学者的潜心研究。其中包括细胞自动机复杂性的内在机理，在不同意义下的分类，以及与其他相关学科的联系等。二十世纪八十年代初，S. Wolfram针对细胞自动机具备规则简单性、局部互连性以及信息处理的高度并行性等优点，提出并号召人们研究结构最为简单的具有两个状态、邻域半径为一的基本细胞自动机(ECA)。在S.Wolfram针对256个基本细胞自动机模拟结果的基础上，L.O.Chua等结合细胞神经网络和非线性电路的研究成果对其进行了一系列非线性动力学的刻画。
符号动力系统是研究细胞自动机的一个重要工具。根据不同的细胞自动机，设计其相关的局部规则，均可以诱导出双边无穷序列所组成的构型空间上相应的拓扑动力系统。借助计算机模拟将发现，细胞自动机呈现丰富的动力学行为。此外，细胞自动机也具有适合在超大规模集成器上实现的并行信息处理结构。1986年，C. Langton提出细胞自动机可以为信息传递、存储和修改等操作提供最基本的条件支持。另外，细胞自动机的一种特殊的时空周期演化结构--滑翔机，及其相关动力学性质也得到了广泛的关注。大量的理论研究成果为细胞自动机的应用领域奠定了基础，尤其是在自然现象模拟、密码学、复杂工业系统和并行计算等方面有广泛的应用。
本文第二、三章以符号动力系统为主要工具，利用周期边界条件借助计算机进行模拟，在双边无穷符号序列空间中对复杂Bernoulli移位细胞自动机规则73的拓扑动力学和滑翔动力学行为进行了分析。第二章得到73号细胞自动机规则的8个具有Bernoulli移位性质的不变子系统及其相关决定系统，并给出这8个子系统之间的关系，最后通过分析全局映射f 73在每个子系统上的动力学行为，证明其具有拓扑传递性，拓扑混合性，正拓扑熵等动力学性质。基于得到的不变子系统，第三章系统地研究了规则73中滑翔机、滑翔碰撞等滑翔动力学行为。借助De Bruijn图对滑翔机在不同以太背景下进行分类，并给出每一类的基本滑翔机及其相关的基本滑翔因子。同时发现，不同滑翔机之间相互组合之后会产生的多种不同的碰撞现象。结合分布式计算可以看到，ECA规则73的任意Bernoulli移位子系统提供了信息存储或者信息传递的基本条件，并且在特定的以太背景下可以设计速度不同的滑翔因子以实现信息的修改。
一直以来，对细胞自动机进行更加完整和精确的分类是一项极具挑战又颇有意义的理论任务。诸多学者尝试从不同的角度进行讨论，但是由于受到许多条件的限制，分类结果缺乏一般性。最初，Wolfram通过大量的计算机实验将所有的细胞自动机分成四个大类。随后，L.O.Chua等通过三个几何变换，将所有的基本细胞自动机规则分成88个全局等价类。在L.O.Chua等对细胞自动机分类的基础之上，本文第四章针对其中3个全局等价类进行研究，通过构造相应的同胚映射将此3类细胞自动机与单边无穷符号序列空间上的移位映射建立拓扑共轭关系，进而将它们规结为同一类，记作PECA。此外，容易证明由这些具有特殊性质的规则诱导出的乘积动力系统与移位系统仍然保持等价关系，即二者具有等价的拓扑动力学性质，如正拓扑熵、拓扑混合、拓扑传递和拓扑正合等，从而是Devaney意义上和Li-Yorke意义上的混沌。
文章最后对本文主要工作进行总结，根据研究中发现的问题与困难，提出对进一步研究的展望。
Cellular automata, as a special kind of mathematical model, actually are a class of spatially andtemporally discrete complex systems. In the 1940s ~ 1950s, John von Neumann and StanislawUlam conjectured that simple dynamical systems interacting locally can generate complexdynamics during the self-replicating phenomenon research of living system. The theory of cellularautomata has been extensively studied ever since by many scholars, including the inner mechanismof the complexity of cellular automata, classification of cellular automata in different sense, andother related disciplines, etc. In the early 1980s, in order to obtain cellular automata having specificadvantages such as simple rules for component unit of structure, local interconnection between unitsand embarrassing parallelism in information processing, S. Wolfram introduced the elementarycellular automata (ECA), each cell of which takes two states and updates its state in discrete timedepending on its own state and states of its two closest neighbors. Based on Wolfram's work,L.O.Chua et al. provided a rigorous nonlinear dynamical approach to ECA rules combined withcellular neural network and nonlinear circuits.
It is well known that the theory of symbolic dynamical system is an important tool for cellularautomata research. According to the local rule of different CA, a topologically dynamical system ofthe configuration space composed of all bilateral infinite configurations could be induced. Throughcomputer simulation, it is easy to find that CA presents rich dynamical behaviors. In addition,cellular automata have parallel information processing structures, which are very suitable to berealized in VLSI. In 1986, C. Langton put forward that CA can be used as the basic conditions tosupport information transmission, storage and modify. Besides, as a special kind of circularstructure, the glider and its related dynamic properties has been widely studied. Based on abundanttheoretical research achievements, cellular automata have extensive application, especially in thefield of natural phenomena simulation, cryptography, complex industrial system and parallelcomputation, etc.
The symbolic dynamical system is used as the main tool for studying rule 73 in Chapter 2 and3. And with computer simulation based on cycle boundary conditions, the topological and gliderdynamics of rule 73 are investigated in the framework of bi-infinite symbolic sequence space. Firstof all, eight subsystems of rule 73 with the Bernoulli shift property are obtained and therelationships between them are given. Through the dynamical analysis of global mappingf 73ineach subsystem, the dynamical characters such as topological transitive, topological mixing andpositive topological entropy are received. Based on the subsystems obtained, the gliders and glidercollisions in rule 73 are discussed in Chapter 3. Firstly, we classify the gliders under different ethers by using the de bruijn diagram, and give the basic gliders and gliding factors in each class. It is easyto find various glider collisions caused by the combination between different gliders. Combinedwith distributed computing one can find that any Bernoulli shift subsystem of ECA rule 73 couldprovide the basis of information storage or transmission, and under etheric background one candesign gliding factors with different speed to realize information changes.
Researchers have been striving for decades hoping to obtain the more precise classification ofCA. Many attempts to classify CA suffer the loss of generality due to many restricted conditionseither because of finite lattices or some other premise assumptions. Since the 1980s, S. Wolframfocused on the analysis of dynamical systems and studied CA in detail. In his book A New Kind ofScience S. Wolfram classified CA into four classes based on extensive computer simulations. Basedon this work, L. O. Chua et al. provided a nonlinear dynamical research to Wolfram’s empiricalobservations from the viewpoint of mathematical analysis. The total number of 256 ECA rules wasgrouped into the 88 global equivalence classes by three delicate transforms, namely, negative,reflective and composite negative reflective transforms. Based on the above results, we discussedthree of the 88 global equivalence classes in Chapter 4. Firstly, we defined a large class ofpermutive elementary CA based on the permutivity of the local rule, and it was proved that eachECA of this class is topologically conjugate to a one-sided full shift. Furthermore, the Cartesianproduct systems induced by the permutive cellular automata are also topologically conjugate to theshift map on one-sided symbolic space. It is easily to find that the Cartesian product maps of thisclass are topologically exact, topologically mixing, and has positive topological entropy. Andhenceforth, the dynamical systems generated by the global map and its product maps of this classare chaotic in the sense of both Devaney and Li-Yorke.
Finally, we give a brief summary of the work, and according to the questions and difficultiesfound in research, prospects for future studies are given in last Chapter.
符号动力系统是研究细胞自动机的一个重要工具。根据不同的细胞自动机，设计其相关的局部规则，均可以诱导出双边无穷序列所组成的构型空间上相应的拓扑动力系统。借助计算机模拟将发现，细胞自动机呈现丰富的动力学行为。此外，细胞自动机也具有适合在超大规模集成器上实现的并行信息处理结构。1986年，C. Langton提出细胞自动机可以为信息传递、存储和修改等操作提供最基本的条件支持。另外，细胞自动机的一种特殊的时空周期演化结构--滑翔机，及其相关动力学性质也得到了广泛的关注。大量的理论研究成果为细胞自动机的应用领域奠定了基础，尤其是在自然现象模拟、密码学、复杂工业系统和并行计算等方面有广泛的应用。
本文第二、三章以符号动力系统为主要工具，利用周期边界条件借助计算机进行模拟，在双边无穷符号序列空间中对复杂Bernoulli移位细胞自动机规则73的拓扑动力学和滑翔动力学行为进行了分析。第二章得到73号细胞自动机规则的8个具有Bernoulli移位性质的不变子系统及其相关决定系统，并给出这8个子系统之间的关系，最后通过分析全局映射f 73在每个子系统上的动力学行为，证明其具有拓扑传递性，拓扑混合性，正拓扑熵等动力学性质。基于得到的不变子系统，第三章系统地研究了规则73中滑翔机、滑翔碰撞等滑翔动力学行为。借助De Bruijn图对滑翔机在不同以太背景下进行分类，并给出每一类的基本滑翔机及其相关的基本滑翔因子。同时发现，不同滑翔机之间相互组合之后会产生的多种不同的碰撞现象。结合分布式计算可以看到，ECA规则73的任意Bernoulli移位子系统提供了信息存储或者信息传递的基本条件，并且在特定的以太背景下可以设计速度不同的滑翔因子以实现信息的修改。
一直以来，对细胞自动机进行更加完整和精确的分类是一项极具挑战又颇有意义的理论任务。诸多学者尝试从不同的角度进行讨论，但是由于受到许多条件的限制，分类结果缺乏一般性。最初，Wolfram通过大量的计算机实验将所有的细胞自动机分成四个大类。随后，L.O.Chua等通过三个几何变换，将所有的基本细胞自动机规则分成88个全局等价类。在L.O.Chua等对细胞自动机分类的基础之上，本文第四章针对其中3个全局等价类进行研究，通过构造相应的同胚映射将此3类细胞自动机与单边无穷符号序列空间上的移位映射建立拓扑共轭关系，进而将它们规结为同一类，记作PECA。此外，容易证明由这些具有特殊性质的规则诱导出的乘积动力系统与移位系统仍然保持等价关系，即二者具有等价的拓扑动力学性质，如正拓扑熵、拓扑混合、拓扑传递和拓扑正合等，从而是Devaney意义上和Li-Yorke意义上的混沌。
文章最后对本文主要工作进行总结，根据研究中发现的问题与困难，提出对进一步研究的展望。
Cellular automata, as a special kind of mathematical model, actually are a class of spatially andtemporally discrete complex systems. In the 1940s ~ 1950s, John von Neumann and StanislawUlam conjectured that simple dynamical systems interacting locally can generate complexdynamics during the self-replicating phenomenon research of living system. The theory of cellularautomata has been extensively studied ever since by many scholars, including the inner mechanismof the complexity of cellular automata, classification of cellular automata in different sense, andother related disciplines, etc. In the early 1980s, in order to obtain cellular automata having specificadvantages such as simple rules for component unit of structure, local interconnection between unitsand embarrassing parallelism in information processing, S. Wolfram introduced the elementarycellular automata (ECA), each cell of which takes two states and updates its state in discrete timedepending on its own state and states of its two closest neighbors. Based on Wolfram's work,L.O.Chua et al. provided a rigorous nonlinear dynamical approach to ECA rules combined withcellular neural network and nonlinear circuits.
It is well known that the theory of symbolic dynamical system is an important tool for cellularautomata research. According to the local rule of different CA, a topologically dynamical system ofthe configuration space composed of all bilateral infinite configurations could be induced. Throughcomputer simulation, it is easy to find that CA presents rich dynamical behaviors. In addition,cellular automata have parallel information processing structures, which are very suitable to berealized in VLSI. In 1986, C. Langton put forward that CA can be used as the basic conditions tosupport information transmission, storage and modify. Besides, as a special kind of circularstructure, the glider and its related dynamic properties has been widely studied. Based on abundanttheoretical research achievements, cellular automata have extensive application, especially in thefield of natural phenomena simulation, cryptography, complex industrial system and parallelcomputation, etc.
The symbolic dynamical system is used as the main tool for studying rule 73 in Chapter 2 and3. And with computer simulation based on cycle boundary conditions, the topological and gliderdynamics of rule 73 are investigated in the framework of bi-infinite symbolic sequence space. Firstof all, eight subsystems of rule 73 with the Bernoulli shift property are obtained and therelationships between them are given. Through the dynamical analysis of global mappingf 73ineach subsystem, the dynamical characters such as topological transitive, topological mixing andpositive topological entropy are received. Based on the subsystems obtained, the gliders and glidercollisions in rule 73 are discussed in Chapter 3. Firstly, we classify the gliders under different ethers by using the de bruijn diagram, and give the basic gliders and gliding factors in each class. It is easyto find various glider collisions caused by the combination between different gliders. Combinedwith distributed computing one can find that any Bernoulli shift subsystem of ECA rule 73 couldprovide the basis of information storage or transmission, and under etheric background one candesign gliding factors with different speed to realize information changes.
Researchers have been striving for decades hoping to obtain the more precise classification ofCA. Many attempts to classify CA suffer the loss of generality due to many restricted conditionseither because of finite lattices or some other premise assumptions. Since the 1980s, S. Wolframfocused on the analysis of dynamical systems and studied CA in detail. In his book A New Kind ofScience S. Wolfram classified CA into four classes based on extensive computer simulations. Basedon this work, L. O. Chua et al. provided a nonlinear dynamical research to Wolfram’s empiricalobservations from the viewpoint of mathematical analysis. The total number of 256 ECA rules wasgrouped into the 88 global equivalence classes by three delicate transforms, namely, negative,reflective and composite negative reflective transforms. Based on the above results, we discussedthree of the 88 global equivalence classes in Chapter 4. Firstly, we defined a large class ofpermutive elementary CA based on the permutivity of the local rule, and it was proved that eachECA of this class is topologically conjugate to a one-sided full shift. Furthermore, the Cartesianproduct systems induced by the permutive cellular automata are also topologically conjugate to theshift map on one-sided symbolic space. It is easily to find that the Cartesian product maps of thisclass are topologically exact, topologically mixing, and has positive topological entropy. Andhenceforth, the dynamical systems generated by the global map and its product maps of this classare chaotic in the sense of both Devaney and Li-Yorke.
Finally, we give a brief summary of the work, and according to the questions and difficultiesfound in research, prospects for future studies are given in last Chapter.
引文
[1] Hedlund G. A., Endomorphisms and automorphisms of the shift dynamical system [J]. Math.Sys. Theo., 1969, 3(4): 320-375.
[2] Neumann J. V., Theory of self-reproducing automata [M]. Edited and completed by Burks A. W. Burks, University of Illinois press, Champaign, 1966.
[3] Berlekamp E. R., Conway J. H., Guy H. K. Winnning Ways for Your Mathematical Plays [M]. New York: Acadamic Press, 1982.
[4] Wolfram S., Statistical mechanics of cellular automata [J]. Review modern physics, 1983, 55(3):601-644.
[5] Wolfram S., Universality and complexity in cellular automata [J]. Physica D, 1984, 10(1): 1-35.
[6] Wolfram S., Computation theory of cellular automata [J]. Comm. Math. Phys., 1984, 96:15-57.
[7] Wolfram S., Theory and Application of Cellular Automata [M]. Singapore: word scientific,1986.
[8]周作领.符号动力系统[M].上海:上海科技教育出版社, 1997.
[9] Wolfram S., A new kind of science [M]. Wolfram media, inc., Champaign, illinois, 2002.
[10] Langton C. G., Studying artificial life with cellular automata [J]. Physica D, 1986, 22:120-149.
[11] Langton C. G., Computation at the edge of chaos: phase transitions and emergent computation[J]. Physica D, 1990, 42: 12-37.
[12] Cook M., Universality in elementary cellular automata [J]. Complex system, 2004, 15: 1-40.
[13] Chua L. O., Yoon S., Dogaru R., A nonlinear dynamics perspective of Wolfram's new kind of science. Part I: Threshold of complexity [J]. International journal of bifurcation and chaos,2002, 12(12): 2655-2766.
[14] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part II: Universal neuron [J]. International journal of bifurcation and chaos, 2003,13(9): 2377-2491.
[15] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part III: Predicting the unpredictable [J]. International journal of bifurcation and chaos,2004, 14(11): 3689-3820.
[16] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part IV: From Bernoulli shift to 1/f spectrum [J]. International journal of bifurcation and chaos, 2005, 15(4): 1045-1183.
[17] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part V: Fractals everywhere [J]. International journal of bifurcation and chaos, 2005,15(12): 3701-3849.
[18] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part VI: From time-reversible attractors to the arrows of time [J]. International journal of bifurcation and chaos, 2006, 16(5): 1097-1373.
[19] Chua L. O., Guan J. B., Valery I. S., et al., A nonlinear dynamics perspective of Wolfram's new kind of science. Part VII: Isle of Eden [J]. International journal of bifurcation and chaos, 2007a,17(9): 2839-3012.
[20] Chua L. O., Karacs K., Sbitnev V. I., et al., A nonlinear dynamics perspective of Wolfram's new kind of science. Part VIII: More isles of Eden [J]. International journal of bifurcation and chaos, 2007b, 17(11): 3741-3894.
[21] Chua L. O., Pazienza G. E., Orzo L., et al., A nonlinear dynamics perspective of Wolfram’s new kind of science. Part IX: Quasi-Ergodicity [J]. International journal of bifurcation and chaos,2008, 18(9): 2487-2642.
[22] Chua L. O., Pazienza G. E., Orzo L. and J. Shin., A nonlinear dynamics perspective of Wolram’s new kind of science. Part X: Period-1 rules [J]. International journal of bifurcation and chaos, 2009, 19(5): 1425-1654.
[23] Chua L. O., Pazienza G. E., Orzo L. and J. Shin., A nonlinear dynamics perspective of Wolfram’s new kind of science. Part XI: Period-2 rules [J]. International journal of bifurcation and chaos, 2009, 19(6): 1751-1930.
[24] Cattaneo G., Finellt M., Margara L., Investigating topological chaos by elementary cellular automata dynamics [J]. Theor. Comput. Sci., 2000, 244: 219-241.
[25] Akin H., The topological entropy of n-th iteration of an additive cellular automata [J]. Applied mathematics and computation, 2006, 174: 1427-1437.
[26] Ohi F., Chaotic properties of the elementary cellular automata rule 40 in Wolfram's class I [J]. Complex systems, 2007, 17: 295-308.
[27] Guan J. B., Shen S. W., Tang C. B., et al., Extending Chua's global equivalence theorem on Wolfram's new kind of science [J]. International journal of bifurcation and chaos, 2007, 17(12):4245-4259.
[28] Ohi F., Chaotic properties of the elementary cellular automata rule 168 in Wolfram's class I [C]. AUTOMATA-2008: Theory and applications of cellular automata, 2008: 196-207.
[29] Chen F. Y., Jin W. F., Chen G. R., Chen F. F., Chen L., Chaos of elementary cellular automata rule 42 of Wolfram’s class II [J]. Chaos, 19(1):013140, 2009.
[30] Chen F. F., Chen F. Y., Jin W. F., Chen L., Topological entropy and complexity of one class of cellular automata rules [C]. IWCFTA 2008, 2008, 2863-2867.
[31] Chen L., Chen F. Y., Chen F. F., Jin W. F., Complex symbolic dynamics of Bernoulli-shift cellular atuomata rule [C]. IWCFTA 2008, 2008, 2868-2873.
[32] Jin W. F., Chen F. Y., Chen G. R., Chen L., Chen F. F., Extending the symbolic dynamoics of Chua’s Bernoulli-shift rule 56 [J]. Journal of cellular automata, 2009.
[33] Chen F. Y., Jin W. F., Chen G. R., Chen L., Chen F. F., Complex symbolic dynamoics of Chua’s period-2 rule 37 [J]. Journal of cellular automata, 2009.
[34] Gardner M., MATHEMATICAL GAMES, The fantastic combinations of John Conway's new solitaire game 'life' [J]. Scientific American, 1970, 223: 120-123.
[35] Bays C., Candidates for the game of life in three dimensions [J]. Complex systems, 1987, 1:373-400.
[36] Heudin C. J., A New Candidate Rule for the Game of Two-dimensional Life [J]. Complex systems, 1996, 10: 367-381.
[37] Wuensche A., Classifying cellular automata automatically: finding gliders, giltering, and relating space-time patterns, attractor basins, and the Z parameter [J]. Complexity, 1999,4(3):47-66.
[38] Sapin E., Bailleux O., Chabrier J. J., Research of Complex Forms in Cellular Automata by Evolutionary Algorithms [J]. EA, 2004, 2936: 357-367.
[39] Kutrib M., Cellular Automata - A computational Point of View [J]. SCI, 2008, 113: 183-227.
[40] Martinez G. J., Adamatzky A., H. V. McIntosh., On the Representation of Gliders in Rule 54 by De Bruijn and Cycle Diagrams [J]. ACRI, 2008, 5191: 83-91.
[41] Culik K., Hurd L. P., Yu S., Computation theoretic aspects of cellular automata [J]. Physica D,1990, 45: 357-378.
[42] Sapin E., Baileux O., Chabrier J. J., Research of a Cellular Automaton Simulating Logic Gages by Evolutionary Algorithms [J]. EuorGP03. Lecture notes in computer science, 2003, 2730:414-423.
[43] Sapin E., Bailleux O., Chabrier J. J., Collet P., A new universel automata discovered by evolutionary algorithms [J]. Gecco2004. Lecture notes in computer science, 2004, 3102:175-187.
[44] G. J. Mratinez, H. V. McIntosh, Mora J. C. S. T., Gliders in rule 110 [J]. International journal of unconventional computing, 2005, 2: 1-49.
[45] Martinez G. J., Adamatzky A., H. V. McIntosh., Phenomenology of glider collisions in cellular automaton rule 54 and associated logical gates [J]. Chaos solitons and fractals, 2006, 28:100-111.
[46] G. J. Martinez, H. V. McIntosh, J. C. S. T. Mora, Vergara S. V. C., Rule 110 objects and other collision-based constructions [J], Journal of cellular automata, 2007, 2: 219-242.
[47] Adamatzky A., Martinez G. J., Zhang L., Wuensche A., Operating binary strings using gliders and eaters in reaction-diffusion cellular automata [J]. Math. and computer modelling, 2010,52(1): 177-190.
[48] Martinez G. J., McIntosh H. V., Mora J. C. S. T., Production of Gliders by Collisions in Rule110 [J]. ECAL, 2003, 2801: 175-182.
[49] Adamatzky A., Universal Dynamical Computation in Multidimensional Excitable Lattices [J]. International journal of theoretical physics, 1998, 37(12): 3069-3108.
[50] Shi L., Chen F. Y., Jin W. F., Gliders, Collisions and Chaos of Cellular Automata Rule 62 [C]. IWCFTA’09, 2009, 221-225.
[51] Jing Chen, Fangyue Chen, Yunfeng Bian, Wei Chen., Dynamics of Wolfram's Class III Cellular Automata Rule 73 [C]. International Conference on Scientific Computing, 2011, 220-225.
[52]王毅,若干细胞自动机的符号动力学研究[D].杭州：杭州电子科技大学.
[53]陈惠开,应用图论图和电网络[M].北京:人民邮电出版社, 1990. 31.
[54]郑咸义,计算方法[M].广州:华南理工大学出版社, 2002. 44.
[55]徐俊明,图论及其应用[M].合肥:中国科技大学出版社, 2000. 46-49.
[56] Kitchens B., Symbolic dynamics: One-sided, two-sided and countable state Markov shifts [M]. Berlin: springer-verlag, 1998.
[57] Wiggins S., Introduction to Applied Nolinear Dynamical Systems and Chaos [M]. Berlin: springer-verlag, 1990.
[58] Xiong, J. C, Yang, Z. G., Chaos Caused by a Topologically Mixing Map [J]. In dynamical systems and related topics, world scientific, singapore, 1992, 500-572.
[59] Blanchard, F., Glasner, E., Kolyada, S., Maass, A., On Li-Yorke pairs [J] J. Reine angew. math.,2002, 547: 51-68.
[60]叶向东,拓扑动力系统概论[M].北京：科学出版社, 2008.
[61] Fagnani, F., Margara, L., Expansivity, permutivity, and chaos for cellular automata [J] Theory of Computing Systems, 1998, 31(1): 663-677.
[62] Moothathu, T. K. S., Homogeneity of surjective cellular automata [J] Dynamical Systems,2005, 13(1):195-202.
[63] Culik II K, Yu S., Undecidability of CA classification schemes [J]. Complex systems.1988,2:177-190.
[64] Cattano G, Dennunzio A, Margara L. Chaotic subshifts and related languages applications to one-dimensional cellular automata [J]. Fundamenta Informaticae. 2002, 52:39-80.
[65] Bays C., Classification of semitotalistic cellular automata in three dimensions [J].Complex Systems.1988, 2:235-254.
[66] Paola Favati, Grazia Lotti, Luciano Margara., Additive one-dimensional cellular automata are chaotic according to Devaney's definition of chaos [J]. Theoretical Computer Science.174(1997):157-170.
[2] Neumann J. V., Theory of self-reproducing automata [M]. Edited and completed by Burks A. W. Burks, University of Illinois press, Champaign, 1966.
[3] Berlekamp E. R., Conway J. H., Guy H. K. Winnning Ways for Your Mathematical Plays [M]. New York: Acadamic Press, 1982.
[4] Wolfram S., Statistical mechanics of cellular automata [J]. Review modern physics, 1983, 55(3):601-644.
[5] Wolfram S., Universality and complexity in cellular automata [J]. Physica D, 1984, 10(1): 1-35.
[6] Wolfram S., Computation theory of cellular automata [J]. Comm. Math. Phys., 1984, 96:15-57.
[7] Wolfram S., Theory and Application of Cellular Automata [M]. Singapore: word scientific,1986.
[8]周作领.符号动力系统[M].上海:上海科技教育出版社, 1997.
[9] Wolfram S., A new kind of science [M]. Wolfram media, inc., Champaign, illinois, 2002.
[10] Langton C. G., Studying artificial life with cellular automata [J]. Physica D, 1986, 22:120-149.
[11] Langton C. G., Computation at the edge of chaos: phase transitions and emergent computation[J]. Physica D, 1990, 42: 12-37.
[12] Cook M., Universality in elementary cellular automata [J]. Complex system, 2004, 15: 1-40.
[13] Chua L. O., Yoon S., Dogaru R., A nonlinear dynamics perspective of Wolfram's new kind of science. Part I: Threshold of complexity [J]. International journal of bifurcation and chaos,2002, 12(12): 2655-2766.
[14] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part II: Universal neuron [J]. International journal of bifurcation and chaos, 2003,13(9): 2377-2491.
[15] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part III: Predicting the unpredictable [J]. International journal of bifurcation and chaos,2004, 14(11): 3689-3820.
[16] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part IV: From Bernoulli shift to 1/f spectrum [J]. International journal of bifurcation and chaos, 2005, 15(4): 1045-1183.
[17] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part V: Fractals everywhere [J]. International journal of bifurcation and chaos, 2005,15(12): 3701-3849.
[18] Chua L. O., Sbitnev V. I., Yoon S., A nonlinear dynamics perspective of Wolfram's new kind of science. Part VI: From time-reversible attractors to the arrows of time [J]. International journal of bifurcation and chaos, 2006, 16(5): 1097-1373.
[19] Chua L. O., Guan J. B., Valery I. S., et al., A nonlinear dynamics perspective of Wolfram's new kind of science. Part VII: Isle of Eden [J]. International journal of bifurcation and chaos, 2007a,17(9): 2839-3012.
[20] Chua L. O., Karacs K., Sbitnev V. I., et al., A nonlinear dynamics perspective of Wolfram's new kind of science. Part VIII: More isles of Eden [J]. International journal of bifurcation and chaos, 2007b, 17(11): 3741-3894.
[21] Chua L. O., Pazienza G. E., Orzo L., et al., A nonlinear dynamics perspective of Wolfram’s new kind of science. Part IX: Quasi-Ergodicity [J]. International journal of bifurcation and chaos,2008, 18(9): 2487-2642.
[22] Chua L. O., Pazienza G. E., Orzo L. and J. Shin., A nonlinear dynamics perspective of Wolram’s new kind of science. Part X: Period-1 rules [J]. International journal of bifurcation and chaos, 2009, 19(5): 1425-1654.
[23] Chua L. O., Pazienza G. E., Orzo L. and J. Shin., A nonlinear dynamics perspective of Wolfram’s new kind of science. Part XI: Period-2 rules [J]. International journal of bifurcation and chaos, 2009, 19(6): 1751-1930.
[24] Cattaneo G., Finellt M., Margara L., Investigating topological chaos by elementary cellular automata dynamics [J]. Theor. Comput. Sci., 2000, 244: 219-241.
[25] Akin H., The topological entropy of n-th iteration of an additive cellular automata [J]. Applied mathematics and computation, 2006, 174: 1427-1437.
[26] Ohi F., Chaotic properties of the elementary cellular automata rule 40 in Wolfram's class I [J]. Complex systems, 2007, 17: 295-308.
[27] Guan J. B., Shen S. W., Tang C. B., et al., Extending Chua's global equivalence theorem on Wolfram's new kind of science [J]. International journal of bifurcation and chaos, 2007, 17(12):4245-4259.
[28] Ohi F., Chaotic properties of the elementary cellular automata rule 168 in Wolfram's class I [C]. AUTOMATA-2008: Theory and applications of cellular automata, 2008: 196-207.
[29] Chen F. Y., Jin W. F., Chen G. R., Chen F. F., Chen L., Chaos of elementary cellular automata rule 42 of Wolfram’s class II [J]. Chaos, 19(1):013140, 2009.
[30] Chen F. F., Chen F. Y., Jin W. F., Chen L., Topological entropy and complexity of one class of cellular automata rules [C]. IWCFTA 2008, 2008, 2863-2867.
[31] Chen L., Chen F. Y., Chen F. F., Jin W. F., Complex symbolic dynamics of Bernoulli-shift cellular atuomata rule [C]. IWCFTA 2008, 2008, 2868-2873.
[32] Jin W. F., Chen F. Y., Chen G. R., Chen L., Chen F. F., Extending the symbolic dynamoics of Chua’s Bernoulli-shift rule 56 [J]. Journal of cellular automata, 2009.
[33] Chen F. Y., Jin W. F., Chen G. R., Chen L., Chen F. F., Complex symbolic dynamoics of Chua’s period-2 rule 37 [J]. Journal of cellular automata, 2009.
[34] Gardner M., MATHEMATICAL GAMES, The fantastic combinations of John Conway's new solitaire game 'life' [J]. Scientific American, 1970, 223: 120-123.
[35] Bays C., Candidates for the game of life in three dimensions [J]. Complex systems, 1987, 1:373-400.
[36] Heudin C. J., A New Candidate Rule for the Game of Two-dimensional Life [J]. Complex systems, 1996, 10: 367-381.
[37] Wuensche A., Classifying cellular automata automatically: finding gliders, giltering, and relating space-time patterns, attractor basins, and the Z parameter [J]. Complexity, 1999,4(3):47-66.
[38] Sapin E., Bailleux O., Chabrier J. J., Research of Complex Forms in Cellular Automata by Evolutionary Algorithms [J]. EA, 2004, 2936: 357-367.
[39] Kutrib M., Cellular Automata - A computational Point of View [J]. SCI, 2008, 113: 183-227.
[40] Martinez G. J., Adamatzky A., H. V. McIntosh., On the Representation of Gliders in Rule 54 by De Bruijn and Cycle Diagrams [J]. ACRI, 2008, 5191: 83-91.
[41] Culik K., Hurd L. P., Yu S., Computation theoretic aspects of cellular automata [J]. Physica D,1990, 45: 357-378.
[42] Sapin E., Baileux O., Chabrier J. J., Research of a Cellular Automaton Simulating Logic Gages by Evolutionary Algorithms [J]. EuorGP03. Lecture notes in computer science, 2003, 2730:414-423.
[43] Sapin E., Bailleux O., Chabrier J. J., Collet P., A new universel automata discovered by evolutionary algorithms [J]. Gecco2004. Lecture notes in computer science, 2004, 3102:175-187.
[44] G. J. Mratinez, H. V. McIntosh, Mora J. C. S. T., Gliders in rule 110 [J]. International journal of unconventional computing, 2005, 2: 1-49.
[45] Martinez G. J., Adamatzky A., H. V. McIntosh., Phenomenology of glider collisions in cellular automaton rule 54 and associated logical gates [J]. Chaos solitons and fractals, 2006, 28:100-111.
[46] G. J. Martinez, H. V. McIntosh, J. C. S. T. Mora, Vergara S. V. C., Rule 110 objects and other collision-based constructions [J], Journal of cellular automata, 2007, 2: 219-242.
[47] Adamatzky A., Martinez G. J., Zhang L., Wuensche A., Operating binary strings using gliders and eaters in reaction-diffusion cellular automata [J]. Math. and computer modelling, 2010,52(1): 177-190.
[48] Martinez G. J., McIntosh H. V., Mora J. C. S. T., Production of Gliders by Collisions in Rule110 [J]. ECAL, 2003, 2801: 175-182.
[49] Adamatzky A., Universal Dynamical Computation in Multidimensional Excitable Lattices [J]. International journal of theoretical physics, 1998, 37(12): 3069-3108.
[50] Shi L., Chen F. Y., Jin W. F., Gliders, Collisions and Chaos of Cellular Automata Rule 62 [C]. IWCFTA’09, 2009, 221-225.
[51] Jing Chen, Fangyue Chen, Yunfeng Bian, Wei Chen., Dynamics of Wolfram's Class III Cellular Automata Rule 73 [C]. International Conference on Scientific Computing, 2011, 220-225.
[52]王毅,若干细胞自动机的符号动力学研究[D].杭州：杭州电子科技大学.
[53]陈惠开,应用图论图和电网络[M].北京:人民邮电出版社, 1990. 31.
[54]郑咸义,计算方法[M].广州:华南理工大学出版社, 2002. 44.
[55]徐俊明,图论及其应用[M].合肥:中国科技大学出版社, 2000. 46-49.
[56] Kitchens B., Symbolic dynamics: One-sided, two-sided and countable state Markov shifts [M]. Berlin: springer-verlag, 1998.
[57] Wiggins S., Introduction to Applied Nolinear Dynamical Systems and Chaos [M]. Berlin: springer-verlag, 1990.
[58] Xiong, J. C, Yang, Z. G., Chaos Caused by a Topologically Mixing Map [J]. In dynamical systems and related topics, world scientific, singapore, 1992, 500-572.
[59] Blanchard, F., Glasner, E., Kolyada, S., Maass, A., On Li-Yorke pairs [J] J. Reine angew. math.,2002, 547: 51-68.
[60]叶向东,拓扑动力系统概论[M].北京：科学出版社, 2008.
[61] Fagnani, F., Margara, L., Expansivity, permutivity, and chaos for cellular automata [J] Theory of Computing Systems, 1998, 31(1): 663-677.
[62] Moothathu, T. K. S., Homogeneity of surjective cellular automata [J] Dynamical Systems,2005, 13(1):195-202.
[63] Culik II K, Yu S., Undecidability of CA classification schemes [J]. Complex systems.1988,2:177-190.
[64] Cattano G, Dennunzio A, Margara L. Chaotic subshifts and related languages applications to one-dimensional cellular automata [J]. Fundamenta Informaticae. 2002, 52:39-80.
[65] Bays C., Classification of semitotalistic cellular automata in three dimensions [J].Complex Systems.1988, 2:235-254.
[66] Paola Favati, Grazia Lotti, Luciano Margara., Additive one-dimensional cellular automata are chaotic according to Devaney's definition of chaos [J]. Theoretical Computer Science.174(1997):157-170.