Generalized Sub-shifts Of A Cellular Automaton Rule

Cellular Automata (CA), introduced by the founder of the modern computer science John von Neumann in the 1940s-1950s in the research of self-replication of the life system, are a class of spatially, temporally and state discrete mathematical models. With different local rules designed, CA are able to produce the rich behaviors in its time-space evolutions and the phenomena of the complex dynamic interaction and self-replicating. Even the elementary cellular automata (ECA) with much simple local rules also have various dynamical behaviors. Hence, cellular automata provide an efficient model for studying the global behaviors and the complex phenomena in the theory of dynamical system, such as ordering, chaos, asymmetry, fractal, etc. So, cellular automata are widely applied in the parallel computation, economics, the cryptography and the simulation of natural phenomena, etc.The symbolic dynamical system is a significant tool for analysing the dynamical system theory in mathematics. For different maps in the symbolic sequence space, if we can establish the topological conjugacy relation between these maps, then we can classify them. The maps belong to the same class have the same dynamics such as topological entropy topological transitivity, and topological mixing etc.This paper is devoted to an in-depth study of cellular automaton rule 180 under the framework of symbolic dynamical systems. Chapter 1 shows the development of cellular automata and symbolic dynamics, and presents the preliminaries of elementary cellular automata and symbolic dynamical systems. Chapter 2 explores infinite number of180-positively invariant subsets:generalized sub-shifts. First, we define generalized sub-shifts of180 and hyper generalized sub-shifts of180. Second strictly prove that f180 has strange Bernoulli-shifts on the set which is consist of 0-finite configurations. Last, three effective methods of constructing the shift invariant sets of the rule’s global map are proposed. We can get the small sub-system from 0-finite set and then through logical operation:union to reach the sub-system; exploiting the Bernoulli shift properties of f180, according to Boolean function, we can gain the sub-system; we already know that the topological conjugate systems have the same dynamics, so we set up functions, block map and release map which offer an conjugate relationship between f180 and f165. It is noted that these methods are also applicable to studying the dynamics of other rules. Chapter 3 demonstrates some complex dynamics of the rule, such as positive topological entropies, topologically mixing, and chaos in the sense of Li-York and Devaney. We also introduce a more empirical concept "quasi-ergodicity". Rule 180 is quasi-ergodicity because it is left permutive rule. chapter 4 makes a brief summary on this paper and prospects for future studies.