| Cellular automata, proposed by the founder of the modern computer science John von Neumann in the 1940s ~ 1950s in research of self-replicating phenomenon life system, are a class of mathematical models to research complex systems. Mathematically, cellular automata are spatially and temporally discrete dynamic systems. For different local rules designed, cellular automata visualize rich behaviors in its time-space evolutions. Especially for some simple rules, they have very complex dynamics. The theory of cellular automata has been affected by many scholars of intensive research, including the essence of complexity mechanism inside of cellular automata, the rule classification, and the relations with other disciplines etc. Cellular automata provide a kind of effective model and tool for the study of whole behavior of dynamical system such as chaos and fractal system etc. On the basis of large research achievements of theory, cellular automata have extensive application, including parallel computation, complex industrial system, cryptography, simulation of natural phenomena etc.A glider is a compact group of non-quiescent states which have a periodic structure moving in time in the evolution space of cellular automata. The concept of glider was firstly proposed by Conway in"game of life"in two-dimensional cellular automata. As a circular structure moved with time, the dynamic character of the glider has been widely studied. The study of glider in elementary cellular automata was started by Cook in the research of rule 110. Cook gave the classification of gliders in rule 110. Based on Cook's work, Martinez etc. gave depth and extensive research to the gliders, glider collisions and glider guns which appear in evolution process of the rule 110 and 54. They studied the character of gliders by using the cycle system and de bruijn diagram. Gliders also have extensive application. For example, the computing theory in cellular automata, the relationship between gliders and logical gate in two cellular automata, the Group operation with the ability of parallel computing etc.In this paper, the symbolic dynamics and glider dynamics of two classes of cellular automata are investigated in the framework of symbolic dynamical systems. Firstly, we give the systems which have the Bernoulli shift property of the two classes of elementary cellular automata, respectively. And then, the dynamic behaviors of the local rule on these subsystems are anglicized. We classify the gliders and glider collisions by using the De Bruijn diagram. Finally, the graphs of glider collisions are given and the relationship between glider collision and logical computing is established.The dynamics of elementary cellular automata rule 61 are investigated in the bi-infinite symbolic sequence space by using the symbolic dynamical system in Chapter 2. Then, three subsystems with the Bernoulli shift are given and the relationships between them are analyzed. Finally, the dynamical character such as topological transitive, topological mixing and positive topological entropy are given. In the second part of Chapter 2, the dynamical behaviors of rule 41 are studied. We give a non-wandering set of rule 41 and analyze some dynamical characters of the rule on this non-wandering set. The gliders and glider collisions in rule 61 are studied in Chapter 3. Firstly, we classify the gliders under the ether (111101000) by using the de bruijn diagram, and get the basic gliders and glider factors in each class. Then, we analyze the different glider collisions. The relationship between glider collisions and logical gates is established in Chapter 4. Firstly, the glider collision graphs and corresponding logical true tables are given, and then, the classification of all 2 inputs glider collisions and basic logical units are founded. We also give the classification of 3 inputs glider collisions and parts of logical true table of them. Some examples are presented to verify the method. Finally, a brief summary of this thesis and prospects for future studies are given in last Chapter. |
PDF Full Text Request