The Study Of The Dynamic Behavior Of Hyper Bernoulli-shift Cellular Automata

Cellular Automata (CA),introduced by John von Nenmann in 1950s, are a class of spatially and temporally discrete, deterministic mathematical systems. Through different local rules designed, CA exhibits a large number of varieties and complexities, and has parallel information processing structures that are suitable to be realized in VLSI. Since its birth, CA are widely applied in multiple fields. In the computer science, CA can be seen as a parallel computer, or are used in the parallel computing research and the computer graphics. Mathematically, CA provides an effective model and tool for the dynamic system with complex phenomena for ordering, disturbance, chaos, fractal and so on. CA has benefited from other related theories, and also has promoted the development of the related ones.Since each CA local rule is defined in a discrete finite set, and a bilateral infinite configuration is composed of finite symbols on the set. Each CA rule thus can induce a topological dynamical system of the configuration space which is composed of all bilateral infinite configurations. It is well known that the symbol dynamical system theory is an important tool for studying CA. For two dynamical systems that are defined on the same symbol space, if there exists a homeomorphism between the two ones to make a topological conjugate relationship, then their dynamical behaviors can be viewed as uniform.Under the background of symbol dynamical system, the object of this work is to study in depth the dynamics of the elementary CA (ECA) rule 26. It is revealed that CA rule 26, which belongs to Wolfram's class IV and Chua's hyper Bernoulli-shift rule class, has very rich and complex dynamical behaviors, and a great many gliders and glider collisions.Chapter 2 shows that there are infinitely many Bernoulli-shift subsystems which are invariant under the global map corresponding to rule 26. In the evolutionary progressing of gliders and composed gliders, as the number of glider factors increasing, the number of evolutionary period is increasing, the phenomenons are found in the computer simulations of the rule. A great many computer simulations and reasoning illustrate this fact. In the part 2 and 3 of this chapter, the dynamical properties on the subsystems of rule 26 are in depth studied, rule 26 is chaotic in the sense of Li-Yorke. Furthermore, there exists another three subsystems on which they are topologically mixing, so rule 26 is also chaotic in the sense of Devaney on these subsystems.In Chapter 3, the glider dynamics of rule 26 are studied. Rule 26 has two background patterns, thus has two background ethers. Under these background patterns, the gliders and glider collisions of the rule are studied in detail, respectively. Under background 2, these glider collisions are very rich, for example, two gliders pass through each other and the original forms have been retained. It is very interesting that this case is rarely observed in other CA rules.In Chapter 4, the concept of the block transformation is introduced, and the topological conjugate relationship between two different local rules is obtained based on the new concept, one can get some other local rule's dynamic properties on the relationship. Undoubtedly, the block transformation is another important tool to study CA, and it is worth further discussion in the future research. In the chapter 5, one makes a brief summary on this thesis, and prospects for future studies.