Research On The Classification Of Elementary Cellular Automata Of Alpha Asynchronism And Asynchronous Communication Based On Evolution Features

Cellular Automata(CA)is a mathematical object that occupies a special position in the study of complex systems.They are composed of simple automata rules that can accommodate a limited number of states to form extraordinary global characteristics.The global transitions of cellular automata are divided into two types: synchronous and asynchronous.Synchronous transitions are simple and convenient to realize local rules,while asynchronous transitions are complicated and difficult but more in line with distributed systems and natural organisms.Starting from the simplest one-dimensional cellular automata with only two states,the elementary cellular automata(ECA),this thesis discusses the classification of 256 elementary cellular automata under asynchronism.The 256 elementary cellular automata under synchronism have been analyzed and classified in different ways by various scholars as early as the 1980 s and 1990 s,while the elementary cellular automata under asynchronism have not been discussed due to many asynchronous modes and inconsistent reasons.There are better classification methods.In this thesis,based on the alpha asynchronous scheme,the elementary cellular automata under alpha asynchronous scheme are classified according to the robustness of the measure entropy as follows:(1)High entropy and high robustness,(2)Low entropy and high robustness,(3)Large entropy span,low robustness and(4)Low robustness and phase transitions.This classification method is consistent with the early research conclusions using density as a parameter,which indirectly proves the correctness of the classification method.In addition to the measure entropy,the uncertainty of the asynchronous complex system has also received some attention.This thesis try to use Kolmogorov-Sinai(KS)entropy to explore the uncertainty of the elementary cellular automata,and gives a preliminary protocol that can analyze the uncertainty of more than 80% of the rules.Based on this,we have reached a preliminary conclusion: the lower the uncertainty is,the faster the convergence speed is,and the convergence speed slows down as the uncertainty increases until it converges.The asynchronous scheme of cellular automata are mainly divided into two categories: complete asynchronous scheme and alpha asynchronous scheme.The asynchronism commonly used in the framework of distributed systems is called asynchronous communication.This thesis attempts to formalize a new type of cellular automation under the framework of asynchronous communication.This model is called Asynchronous Communication Cellular Automata(ACCA),which allows each cell to exchange states independently of its neighboring cells at a random time through a specific asynchronous communication protocol,which can separate the communication between cells from the exchanging state.Based on ECA,we discuss the influence of asynchronous communication on its dynamic behavior and analyze the corresponding robustness.Asynchronous communication will inevitably lead to a delay in information exchange.Based on this,we have analyzed the principle of delay on the asynchronous ECA phase transition phenomenon.Although both communication and state exchanging have unpredictable randomness,an effective method of converting each synchronous CA into an equivalent ACCA can still achieve computational equivalence between ACCA and conventional CA.