Symbolic Dynamics Of Some Cellular Automata With Memory

Cellular Automatas(CA),formally introduced by John von Neumann in 1950 s,are a class of spatially and temporally discrete dynamical systems.In the 1980 s,Wolfram raisde Elementary Cellular Automatas(ECA)about binary 1-dimensional CA with radius1,a total of 256 ECA.The new evolution rules formed by adding memory function in ECA evolution,and these rules are determined by the original ECA rules and the memory functions,therefore,Cellular Automata with Memory(CAM)have more complex dynamic properties than ECA.Wolfram subdivided 256 ECA onto uniform,periodic,chaotic and complex according to the evolution of the ECA model.Mart??nez divided ECA into three categories: weak,moderate and strong qualitatively,according to the ECA rules added the memory fuction are in the same class or change to another category of wolfram's four categorys.This dissertation will describe and analyze the dynamics of CAM from the perspective of symbolic dynamic system.The main contents of this dissertation are as follows: The first chapter introduces the research background and status quo of CA and CAM.The second chapter briefly lists relevant theorems,concepts,etc.Third chapter divides ECA into three categories: weak,moderate and strong qualitatively,according to the case of ECA rules adds the memory fuction in Wolfram four categories,qualitatively.Chapter fourth transits ECA100 from homomorphism to periodicity by adding function,and the dynamical properties of CAM100 are discussed from the perspective of dynamical systems on symbolic vector spaces,and it has a rich and complex subsystem of Bernoulli-measure on the bi-infinite vector space symbolic dynamical system.In other words,it is topologically mixed and has positive topological entropy on its subsystems.Therefore,it is chaotic in the sense of Li-Yorke and Devaney.The fifth chapter will realize the ECA from cycle to cycle,under the same conditions with ECA100,by adding memory function to ECA10.And this chapter calculate specifically the topological entropy of ECA10 and CAM10,the topological entropy of CAM10 is smaller,namely,it is can be realize to reduce the complexity of Cellular Automata by adding memory function.The last chapter is a summary of the full text and prospects for future research.