Studies In Dynamics Of Some Complex Bernoulli Shift Cellular Automata

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.