Symbolic Dynamics of Cellular Automata
摘要
The study of the dynamical behavior characterization is a major concern in cellular automata discipline, and it is also a basic research content to explore new methods and concepts for the analysis of their evolutionary dynamics. We introduce symbolic dynamics, one of the main methods for investigating discrete dynamical systems, into the study of quantitative dynamic behavior analysis of cellular automata, and establish a variety of homeomorphic mappings to construct topological conjugate equivalence classes of cellular automata. For a large number of cellular automata with nonlinear or non-surjective features, we quantitatively characterize their rich and complex evolutionary dynamic properties, such as topological mixing, topological entropy, chaos in various senses, etc. Further, we propose the mathematical definition of the evolutionary glider and glider gun, characterizing their chaotic dynamic properties, and providing theoretical support for the numerical simulation conclusions and methods. It should be said that our research results provide an innovative scientific research method for establishing a complete theoretical system for the evolutionary dynamics analysis of cellular automata.