Two-Dimensional Symbolic Dynamics And Cellular Automata

Cellular automata(CA),introduced by John von Neumann in 1950s,are mathematical models in which time,space and state are discrete.In the representation of patterns,cellular automata are discrete dynamical systems.Trough 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.Symbolic dynamics is an important tool for mathematical analysis.In recent decades,an investigation of the complexity of the models,e.g.,those proposed in the research of biology,chemology,engineering,physics,has always related to the theory and methods of high dimensional symbolic dynamics,particularly two-dimensional. For different continuous maps under the same symbolic space,if the homomorphisms can been found to establish the relationship of topological conjugacy,then these con- tinuous maps can been classified.Different maps belonging to the same equivalence class have qualitatively the same dynamics and can be viewed as one system.Firstly,this paper rigorously proves that 8 shift maps defined on the two-dimensional symbolic space are topologically conjugate.In addition,it is shown that one-dimensional symbolic dynamics and two-dimensional symbolic dynamics are semi-topologically conjugate.Based on this work,Chapter 3 studies the topological conjugacy classification of global maps of two-dimensional binary cellular automata(2D CA) with Neumann neighborhood.In this chapter,2~2~5=4294967296 global maps corresponding to local rules of two-dimensional binary cellular automata are defined in two-dimensional symbolic space.By employing four homeomorphisms,all global maps are classified with the perspective of topological conjugacy.Meanwhile,an algorithm is developed to implement this classification,and it is pointed that the number of equivalence classes obtained in this paper is minimal.Chapter 4 discusses the dynamics of global maps of cellular automata.In this chapter,the complex dynamical behaviors of elementary cellular automata rules 18 and 56 are characterized in the bi-infinite symbolic sequence space.Then,the semi-topological conjugacy between the two-dimensional binary cellular automata and elementary cellular automata is established,and 24 universal twodimensional binary cellular automata local rules are found via this relationship.Furthermore, some numerical simulations of universal local rules are given,which are different from those of the well-known "game of life".Finally,Chapter 5 makes a brief summary on this thesis,and prospects for future studies.