Symbolic Dynamics Of Some Cellular Automata Rules And Pseudo-Random Number Generator

From the days of Von Neumann who first proposed the concept of cellular automata (CA), tothe recent book of Wolfram‘A New Kind of Science’, the simple structure of CA has attractedresearchers from various disciplines. It has been subjected to rigorous mathematical and physicalanalysis and its application has been proposed in different branches of science. The reason behindthe popularity of cellular automata can be traced to their simplicity, and to the enormous potentialthey hold in modeling complex systems. CA can be viewed as spatially and temporally discretedynamic systems, made up of a number of individual cells. Each individual cell is in a specific statewhich changes over time depending on the states of its local neighbors through the designed localrule. The overall structure can be viewed as a parallel processing device. However, this simplestructure produces complex patterns displaying the potential to simulate different sophisticatednatural phenomena.Symbolic dynamics is an important tool to study the dynamic behavior of dynamical systems.The state of the systems can be expressed as an infinite sequence of finite number of symbol, themovement track of the state by an infinite sequence can be determined by simple rules such as theshift. Many complex dynamic systems can be equivalent to shift systems through a topologicalconjugate transformation, which can be possible through simple symbolic system analysis to studythe behavior of general dynamical systems. This method plays an important role particularly in theresearch of complex dynamical behaviors in the chaos.Based on the theory of computation, none nontrivial proposition about CA is decidable. Henceif one focuses on a specific CA, then the dynamical behaviors of CA become tractable. The objectof this work is to study in depth the dynamics of the elementary cellular automata rule 41 and rule90. Firstly, three invariant Bernoulli-shift subsystem of rule 41 are proposed. Further more, thedynamic behavior of the subsystems is analyzed, such as topological transitivity, positivetopological entropy.Secondly, according to the property of coupled-expanding map, the conclusion rule 90topologically conjugate with the shift map of one-sided symbol space is proved and the dynamics ofrule 90 has a clear result. Thirdly, based on the relationship between cellular automata and theplanar mapping, the computer simulation model is established. An analysis of the complex of someelementary cellular is got on the basis of the simulation results. Then some elementary cellularautomata are used for designing a pseudo-random number generator and the pseudo-randomsequence pass through the statistical test suite for random and pseudorandom number generators forcryptographic applications, which is the publication NIST.