Evolution Complexity Of Several Elementary Cellular Automata

Cellular automata, as ideal mathematical models, can be regarded as a kind of infinite dimensional systems characterized by discreteness in space, time and state. Therefore, they can be easily used to simulate many phenomena happening in physics, biology, chemistry and other fields.In this paper, we will discuss the 2-evolution languages of 51 elementary cellular automata by using the tools of formal language, symbolic dynamical theory, distinct excluded block and finite automaton. These 51 elementary cellular automata will be divided into three categories after analyzing distinct excluded block set of each elementary cellular automaton: evolution languages that have no distinct excluded blocks, evolution languages that are finite complement regular languages and evolution languages that are infinite complement regular languages.Evolution languages of elementary cellular automata in the first category have no distinct excluded block, so they are regular.Evolution languages of elementary cellular automata in the second category have finite distinct excluded blocks, and their 2-evolution languages are also regular.Evolution languages of elementary cellular automata in the last category have infinite distinct excluded blocks, but those distinct excluded blocks do have regular patterns. After theoretical analysis, we will know their 2-evolution languages are regular, too.In the last section, the results of evolution languages of all 88 elementary cellular automata will be summarized combined with the outcomes already known.