Symbolic Dynamics Of Cellular Automata With Memory And Torsional Smale Horseshoe

In the the 1950 s,John von Neumann put forward a mathematical model called cellular automaton when studying robotic self-replication.A special kind of cellular automata is the elementary cellular automata,which was proposed by Stephen Wolfram.In this model,there are 256 ECA rules,each cell has two states and updates its state in discrete time depending on its own state and states of its two closest left and right neighbors.Besides that,Ramon Alonso-Sanz originally proposed ECAs with memory in 2003.The standard ECAs are ahistoric;that is,the new state of a cell depends on the neighborhood configuration of only the preceding time step.While in ECAs with memory,which is an extension to the conventional framework of ECAs,every output cell is allowed to remember its states during a certain fixed period of its evolution.In addition,for different memory functions,the dynamics of their behaviors are often different.This thesis mainly studies the topological conjugacy classification of two kinds of elementary cellular automata with memory and the relationship between them,as well as the dynamic properties of F16 from the perspective of symbolic dynamics.Finally,an application of symbolic dynamical system of Smale horseshoe is given.More specifically,Chapter 1 briefly introduces the research achievements of two types of cellular automata,and the relationship among symbolic dynamics,cellular automaton and Smale horseshoe.Chapter 2 presents several basic concepts of symbolic dynamical systems used in this paper.Chapter 3 displays the topological conjugacy classification of two kinds of elementary cellular automata with memory by exploiting two fundamental homeomorphisms in symbolic vector space and also discusses the topological conjuacy relationship between them.Chapter 4 is firstly to get the subsystem with Bernoulli right shift for ECA16 by using finite sub-shifts.Then the symbolic dynamical properties such as topological mixture and topological entropy of ECA 16 on subsystems are analyzed by the transfer matrix.Next the dynamics properties of F₁₆ and F₁₆² on the invariant subsystem are in depth studied.We conclude that F₁₆ is chaotic in the sense of Li-Yorke.Furthermore,it is topologically mixing on this invariant subsystem,so F₁₆ is also chaotic in the sense of Devaney.Chapter 5 describes an application of symbolic dynamical system of Smale horseshoe by means of the shift mapping of symbol sequence space.Finally,chapter 6 summarizes the full text and puts forward further research prospects.