The Research Of The Complexity Of Dynamical Behaviors Of Some One-dimensional Cellular Automata

Cellular automata (CA), introduced by John von Neumann in 1950's, are mathematical models in which time, space and state are discrete. In the representation of patterns, cellular automata are discrete dynamical systems. Through different local rules designed, cellular automata exhibit all kinds of varieties and complexities, and produce complicated phenomena of dynamic interaction and self-duplicating. Even elementary cellular automata (ECA) with very simple local rules have rich dynamical behaviors and have parallel information process structures that are suitable to being realized in VLSI. Since cellular automata came into being, they have been widely applied in the research of sociology, economics, strategics, science, etc. Especially, cellular automata provide an effective model for studying the global behaviors and complex phenomena in the theory of dynamical system, such as ordering, turbulence, chaos, asymmetry, fractality, etc.Since Stephen Wolfram made a call for the simplification of cellular automata and put forward ECA, many scholars have made a fruitful research and exploration in many fields of one-dimensional cellular automata, such as theory, application, etc, and got a series of important results. Specially, in 2002 based on an extensive computer simulation and empirical observations Wolfram creatively called cellular automata and their research methods A New Kind of Science. Subsequently, Professor L.O. Chua et al. provided a nonlinear dynamics perspective to Wolfram's empirical observations by using some important concepts like basin tree diagram, cellular automata characteristic functions, etc.Based on the theory of computation, it has been proved that the research of CA is difficult because any nontrivial proposition about CA is undecidable. Hence, if one focuses on particular subclasses of CA, then the dynamical behaviors of CA become tractable. This paper studies the dynamical behaviors of some elementary cellular automata under the standpoints of symbolic dynamics. Firstly, Chapter 2 establishes a new quasi-shift map and quasi-subshift in the bi-infinite sequence space, analyzes the dynamics of quasi-shift map, and discusses the relationship between the quasi-subshift and classical subshift. Furthermore, this chapter characterizes the symbolic dynamics of cellular automata rule 11. That is, rule 11 defines two subsystems on which rule 11 is topologically mixing and possesses the positive topological entropy. Therefore, rule 11 is chaotic both in the sense of Li-Yorke and Devaney on its subsystems. By exploiting the concepts of basin tree diagram and cellular automata characteristic functions, Chapter 3 explores the qualitative properties of robust period-1 rules 172,168, 40 and robust period-2 rule 37, which reveal their non-robust Bernoulli-shift characteristics. Based on the theory and methods of symbolic dynamics, this chapter rigorously proves that all these rules possess chaotic subsystems. Finally, Chapter 4 makes a brief summary on this thesis, and prospects for future studies.