Symbolic Dynamics Of Cellular Automata Bernoulli-Shift Rules

Cellular automata(CA),formally introduced by John von Neumann in 1951,are a class of spatially and temporally discrete,mathematical systems characterized by local interactions and an inherently parallel form of evolution.Although they have simple structures,they possess rich dynamical behaviors corresponding to the design of different rules.Therefore they have been widely applied in the research of sociology, economics,strategics,science,etc.In fact,the research on CA,especially Elementary CA with simple local rules,has drawn a great deal of attentions from various scientific communities.Symbolic dynamics is an effective and important tool for CA study.Although the dynamical behaviors of CA can be analyzed under different frameworks,the exact determination of their temporal evolutions is in general very hard,if not impossible. In particular,many topological properties such as topological entropy,sensitivity and topologically mixing of CA are undecidable.However,many topological properties of particular subclasses of CA become tractable,such as,additive CA,equi-continuous CA,surjective CA,and permutive CA.In addition,there are many distinct CA whose dynamical behaviors are much less understood,especially those capable of universal computation.The objective of this paper is to characterize the dynamical behaviors of 112 Bernoulli-shift rules in the bi-infinite symbolic sequence space from the viewpoint of symbolic dynamics.Firstly,this paper discusses the dynamical behaviors of rule 119.In Chapter 2,it demonstrates the global attractor of f₁₁₉ and the basic laws governing the Bernoullimeasure global attractor are obtained.By establishing a topologically conjugate relationship with a subshift of finite type,it is rigorously proved that f₁₁₉ is topologically mixing on the global attractor.Meanwhile,the positive topological entropy of f₁₁₉ is calculated.Therefore,f₁₁₉ is chaotic in the sense of both Li-Yorke and Devaney on the global attractor,and in the sense of Li-Yorke in the bi-infinite symbolic sequence space.Different from rule 119,there exist three different Bernoulli-measure subsystems of rule 88 and rule 25 in the space of bi-infinite symbolic sequences.Meanwhile, the relationships of subsystems and the existence of fixed points are rigorously investigated, revealing that the union of them three different Bernoulli-measure subsystems is not the global attractor.Furthermore,the dynamical properties of topologically mixing and topological entropy of f₈₈ and f₂₅ are exploited on its subsystems in Chapter 3 and 4.It is concluded that f₈₈ and f₂₅ are chaotic in the sense of Li-Yorke.Finally,Chapter 5 gives some concluding on this thesis,and future study.