The Symbolic Dynamics Of Some Cellular Automata Rules

Cellular automata (CA) refer to a class of spatially and temporally discrete math-ematical systems which characterized by local interactions and an inherently parallel form of evolution. CA possess simple local rules can exhibit complex dynamical behav-iors. There exist many periodic structure which known as glider in the evolution space of some ECA rules has been investigated. A glider is a compact group of non-quiescent states which have a periodic structure moving in time. From the symbolics dynamics point of view, the glider actually is a periodic subshift which embedded into the bi-infinite sequence. In this paper, the gliders, glider collisions and other phenomenon are found, and the mechanism of the phenomenology are given subshift point of view.Topological dynamics of CA were first analyzed by Hedlund [1969] who viewed the one-dimensional cellular automata (1D CA) within the context of symbolic dynam-ics as endomorphisms of a shift dynamical system.The objective of this paper is to characterized the complex dynamics of Bernoulli-shift rule 14 in the bi-infinite symbolic sequence space from the viewpoint of symbolic dynamics. Moreover it to depict the complicated phenomenon of the gliders and gliders collision in the evolution space of rule 9.Firstly, this paper is devoted to an in-depth study of Chua's Bernoulli-shift rule 14 from the viewpoint of symbolic dynamics. It is shown that rule 14 identifies two chaotic dynamical subsystems and presents very rich and complicated dynamical properties. In particular, it is topologically mixing and possess the positive topological entropies on its two subsystems. Therefore, it is chaotic in the sense of both Li-Yorke and Devaney on the subsystems. Meanwhile, Isle of Eden of rule 14 are ubiquitous presented in its periodic orbits.In chapter 3, it investigate the dynamics of ECA rule 9. As a member of the Chua's Bernoulli shift rules and the Wolfram classâ…¡, Rule 9 is shown to have rich and complex dynamics. This chapter provides a systematic analysis of glider dynamics, interactions and bifurcations in rule 9, including several natural gliders, a catalog of glider collisions, which were found only in Wolfram's complex rules 54 and 110 before. Moreover, we find a new kind of glider phenomenology which we named it as glider bifurcations. moreover, we give the mathematical mechanism of the phenomenology of glider collisions and bifurcations. Meanwhile, it is also proved that rule 9 defines a subsystem with complicated dynamical properties such as topologically mixing and positive topological entropy.In chapter 4, gives some concluding on this thesis and future study.