Another consequence of additivity: the correspondence between colors of cells on rows and columns in the rule 60 cellular automaton. … Multiplying these matrices modulo 2 by vectors corresponding to a row of the cellular automaton gives a column, and vice versa.

But it turns out that there are cellular automata whose behavior is in effect still more complex—and in which even such averages become very difficult to predict. … And as a result it becomes almost impossible to predict—even approximately—what the cellular automaton will do. … The only sure way to answer these questions, it seems, is just to run the cellular automaton for as many steps as are needed, and to

History [of cellular automaton classes] I discovered the classification scheme for cellular automata described here late in 1983, and announced it in January 1984. … The notion that class 4 can be viewed as intermediate between class 2 and class 3 was studied particularly by Christopher Langton , Wentian Li and Norman Packard in 1986 for ordinary cellular automata, by Hyman Hartman in 1985 for probabilistic cellular automata and by Hugues Chaté and Paul Manneville in 1990 for continuous cellular automata.

Directional reversibility [in cellular automata] Even if successive time steps in the evolution of a cellular automaton do not correspond to an injective map, it is still possible to get an injective map by looking at successive lines at some angle in the spacetime evolution of the system.

Computations in Cellular Automata…So what about the cellular automata that we discussed earlier in this book? … At some level, any cellular automaton—or for that matter, any system whatsoever—can be viewed as performing a computation that determines what its future behavior will be. … And this turns out to be possible for some of the cellular automata that I discussed earlier in this book.

Minimal cellular automata for sequences Given any particular sequence of black and white cells one can look for the simplest cellular automaton which generates that sequence as its center column when evolving from a single black cell (compare page 956 ). The pictures below show the lowest-numbered cellular automaton rules that manage to generate repetitive sequences containing black cells with successively greater separations s . … If one looks not just at specific sequences, but instead at all 2 n possible sequences of length n , one can ask how many cellular automaton rules (say with k = 2 , r = 2 ) one has to go through in order to generate every one of these.

In a cellular automaton with n cells, the problem of finding the repetition period is in general PSPACE-complete—as follows from the possibility of universality in the underlying cellular automaton. … With sufficiently simple behavior, a cellular automaton repetition period can readily be determined in some power of Log[n] steps.

P completeness If one allows arbitrary initial conditions in a cellular automaton with nearest-neighbor rules, then to compute the color of a particular cell after t steps in general requires specifying as input the colors of all 2t + 1 initial cells up to distance t away (see page 960 ). … It turns out that finding the outcome of evolution in any standard universal Turing machine or cellular automaton is P-complete in this sense, since the process of emulating any such system by any other one is in NC. … A notable example due to Cristopher Moore from 1996 is the 3D majority cellular automaton with rule UnitStep[a + AxesTotal[a, 3] - 4] (see page 927 ); another example is the Ising model cellular automaton from page 982 .

More Cellular Automata…About 85% of all three-color totalistic cellular automata produce behavior that is ultimately quite regular. … Looking at pictures like these, it is at first difficult to believe that they can be generated just by following very simple underlying cellular automaton rules. … As it turns out, complexity is particularly widespread in cellular automata, and for this reason it is fortunate that cellular automata were the very first systems that I originally decided to study.

For while The behavior of a sequence of cellular automaton programs obtained by successive random mutations. … The cellular automata shown here all have 3 possible colors and nearest-neighbor rules.