Complex Dynamics Of Some Period Cellular Automata Rules

Cellular automata (CA), conceived by John von Neumann in the 1950s, are dy-namic systems in which space and time are discrete. The CA algorithm is a parallel process operating on the array of cells. The simultaneous change of state of each cell is specified by a local transition rule. Through different local rules designed, CA can exhibit all kinds of varieties and complexities, and produce complicated phenomena of dynamic interaction and self-duplicating. Even elementary cellular automata with very simple local rules have rich dynamical behaviors. Since CA came into being, they have been widely applied in the research of sociology, economics, strategics, science, etc.In this thesis, symbolic dynamics of robust periodic elementary cellular automata rules 62 and 96 is investigated in the bi-infinite symbolic sequence space. One main contentions is that these robust period rules, which were said to be simply as periodic before, actually display rich and complex nonlinear dynamics in the infinite case.In Chapter 1, we review briefly the notations and concepts of one-dimensional CAs and symbolic dynamics, as well as the research progress of CAs. In Chapter 2, we exploit the concepts of CA basin tree diagram and forward time-Ï„maps to uncover the qualitative properties of rule 96, which reveal its non-robust Bernoulli-shift character- istics. Based on concepts from subshift of finite type, this chapter conducts a rigorous analysis of itsr chaotic properties, such as topologically mixing and topological en-tropy. In Chapter 3, we concentrate on time asymptotic dynamics of unique robust period-3 rule 62. This chapter provides a systematic analysis of glider dynamics and interactions in rule 62, including several natural gliders, a catalog of glider collisions and many glider guns. It is important to emphasize that gliders are believed to be the characteristic signatures allowing one to recognize class IV behavior. Certainly, the catalog of its all possible gliders and glider collisions is less plentiful than that of rules 54 and 110. Also, it is proved that the intrinsic temporal complexity of rule 62 is high according to the usual features quantifying the complexity of discrete dynamics, such as topological entropy and topologically mixing. Finally. we make a brief summary on this work, and prospect for further research in Chapter 4.