The Study Of CA Symbolic Dynamics Theory And Its Applications

Cellular automata (CA for short), formally introduced by John von Neumann in1951, are discrete (both in time, space and state) dynamical systems which serve asgood simulation tools for modeling many complex systems. In recent decades, moreand more researchers focus their attention on studying the theoretical and applied as-pects of CA. While in the field of theoretical research, the classification of CA is alwaysa hot topic, and heretofore many classification schemes have been presented from dif-ferent points of view. However, among them, the majority suffers the loss of generalitydue to many restricted conditions given under assumption. In this thesis, from the pointof view of symbolic dynamics, we investigate the extended CA which are composedof infinite number of cells without the restriction of boundary conditions, and the corework is to discuss the global equivalence classification. Moreover, other works includethe Cellular Neural Networks (CNN for short) realizations of Elementary Cellular Au-tomata (ECA for short) and global evolutionary properties of some additive ECA rules.More specifically, the main contents of this thesis are as follows:1. We find, in this thesis, two CNN genes (corresponding input-output Booleanfunctions are linearly separable) composed of five variables with two kinds ofneighborhoods to successfully extract the endings and bifurcation points in theprintfeature image. Noteworthy, the input-output Boolean function correspond-ing the CNN gene in practice should be linearly separable. In terms of ECAcomposed of both linear separable and linear non-separable rules, we thereforeoperate by two steps. First step, we directly implement linear separable ECArules via CNN genes, and second step, we optimally decompose the linear non-separable ECA rules into the logic operation combinations of linear separableECA rules, then utilize the CNN genes obtained in the first step to implementthem. In this sense we implement all ECA rules, which to some extent re?ectsthe ECA application in CNN.2. We present a topological conjugacy classification of ECA composed of bi-infinitenumber of cells from the point of view of symbolic dynamics, and the classifica-tion result coincides with that of ECA composed of finite number of cells withperiodic boundary conditions. Furthermore, we find that the two homeomor-phisms which are utilized to classify ECA in the extended case can also be usedto group one-dimensional CA with radius 2. The classification of additive rules validates the result. On the foundation of one-dimensional cases, we also pro-vide theoretically the homeomorphisms that classify high-dimensional CA in anextended case. Particularly, we find the dual rule of the famous game of life rulebasing on this platform.3. In light of many results obtained by Wolfram through large amount of computersimulations and empirical observations in A New Kind of Science published in2002, we firstly recap the main results in paper series conducted by Chua et alfrom 2002 to 2007, then we investigate some properties of Isle of Eden possessedby some ECA rules. We also give a simple proof of some global evolutionaryproperties of two representative additive ECA rules.