Font Size: a A A

A Symbolic Dynamics Perspective To Cellular Automata

Posted on:2017-12-30Degree:MasterType:Thesis
Country:ChinaCandidate:B ChenFull Text:PDF
GTID:2348330482976783Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Cellular automata(CA),initiated by John von Neumann,are a class of spatially and temporally discrete dynamical systems characterized by local interactions.Ever since its inception,more and more researchers focus their attention on studying the theoretical and applied aspects of CA.While in the field of theoretical research,Conway devised the game of life,Stephen Wolfram conceive elementary cellular automata(ECA)and provided a series of researches and applications,L.O.Chua et al provided a nonlinear dynamics perspective to Wolfram's empirical observations,and Alonso-Sanz originally proposed ECA with memory.In this thesis,from the point of view of symbolic dynamics,we present an accurate characterization of complex symbolic dynamics of gliders in Ddimensional CA.Meanwhile,we discuss the dynamical behaviours of hybrid cellular automata(HCA)and discover that the HCA(9,74)and HCA(168,133)can generate a host of gliders and complicated glider collisions.More specifically,the main contents of this thesis are as follows:1.By introducing the D-dimensional symbolic space,some fundamental dynamical properties of D-dimensional shift map are explored in a subtle way.The purpose is to present an accurate characterization of complex symbolic dynamics of gliders in the Conway's game of life rule.A series of dynamical properties of gliders on their subsystems are investigated by the directed graph representation and transition matrix.More specifically,the gliders here are topologically mixing and possess the positive topological entropy on their subsystems.It is worth mentioning that the method presented in this paper is also applicable to other gliders in different D dimensions.2.By introducing the symbol vector space and exploiting the mathematical definition of ECAM,we present an analytical characterization of complex asymptotic dynamics of ECAM rule 12.Elementary cellular automaton rule 12,a member of Wolfram's class II which was said to be simple as fixed points before,actually exists a chaotic subsystem in the historic model.It is worth mentioning that the method presented in this paper is also applicable to other ECAM.3.Based on the evolutionary game theory,we introduce the payoff matrix and design a simple RPS game rule into an one-dimensional orthogonal grids.We regard RPS games as a special extended class of cellular automata(CA),where each cell has three possible states.It is of interest to find that the RPS game rule actually defines two chaotic subsystems.More importantly though,the RPS game rule is topologically mixing on the chaotic subsystems,indicating that it is chaotic in the sense of both Li-Yorke and Devaney.It is worth mentioning that the method presented in this paper is also applicable to other RPS game rules.4.Elementary cellular automata(ECA)rule 9 and rule 74,members of Chua's Bernoulli shift rules and Wolfram's class II,can generate a host of gliders and complicated glider collisions by introducing the hybrid mechanism,which are more plentiful than those generated by ECA rule 110.Many gliders also emerge from ECA rule168 and rule 133,which are members of Chua's period rules.For HCA(9,74)and HCA(168,133),after classifying and coding the newfound gliders,we expand a qualitative discussion of glider collisions.Through exploiting the mathematical definition of hybrid cellular automata(HCA),we also present an analytical characterization of symbolic dynamics of some gliders.
Keywords/Search Tags:Symbolic dynamics, D-shift map, topologically mixing, topological entropy, chaos, glider, Conway's game of life, elementary cellular automata with memory, RPS game, hybrid cellular automata
PDF Full Text Request
Related items