Cellular Automata And Symbolic Dynamical Systems

Cellular Automata(CA ), formally introduced by John von Neumann in 1951, are mathematical models in which time and space are discrete. Through different local rules designed, Cellular Automata exhibit all kinds of varieties and complexities. Even Elementary Cellular Automata(ECA )with very simple local rules, which have rich dynamical behaviors and have parallel information process structure that are suitable to being realized in VLSI, have extensive applications in many scientific domains.Symbolic dynamics is an important tool for mathematical analysis. For different symbolic sequence mappings under the same symbolic space, if we can find the homoe-morphism that establish the relation of topological conjugacy of these mappings, then we can classify these mappings. Different mappings belonging to the same class exhibit the same dynamical behaviors.In this paper, the relation between the Elementary Cellular Automata and bi-infinite symbolic sequence is established. The 256 kinds of local rules of Cellular Automata are corresponding to the 256 kinds of local rule mappings in symbolic space. From the point of topological conjugacy of symbolic dynamics, we prove rigorously that among the 88 global equivalence classes , into which Wolfram classified 256 local rules via large amount of simulation observations, those different mappings belonging to the same global equivalence class are mutually topologically conjugate. Furthermore, we investigate the periodic points and their properties of several Additive Cellular Automata local rule mappings.The paper is organized as follows. Chapter 1 introduces the research and the development of Cellular Automata and some basic concepts of Elementary Cellular Automata. Chapter 2 lists all 256 kinds of local rule mappings constructed . Through two homoemorphisms we've found, all 256 local rule mappings are classified. Chapter 3 characterizes the discussion of periodic point of several Additive Cellular Automata local rule mappings. Some concluding remarks and further study along the same line are given in Chapter 4.