Indeed, not only for cellular automata but also for essentially all of the other kinds of systems that we studied, we found that highly complex behavior could be obtained even with rather simple rules, and that adding further complication to these rules did not in most cases noticeably affect the level of complexity that was produced. … Indeed, it is in fact characteristic of all cellular automata that lie in what I called class 4. … I strongly suspect that it is true in general that any cellular automaton which shows overall class 4 behavior will turn out—like rule 110—to be universal.

Note (b) for Computations in Cellular Automata…Other examples [of cellular automaton computation] Rule 152 and rule 144, which effectively compute Ceiling[n/2] and Ceiling[n/4] , respectively, are shown below with n = 18 initial black cells.

Block occurrences [in rule 30] The pictures below show at which step each successive block of length up to 8 first appears in evolution according to various cellular automaton rules starting from a single black cell.

Note (b) for Cellular Automata…Growth [2D cellular automaton] rules The pictures below show examples of rules in which a cell becomes black if it has exactly the specified numbers of black neighbors (the initial conditions used have the minimal number of black cells for growth).

More general [cellular automaton] rules The programs given so far are for cellular automata with rules of the specific kind described in this chapter. In general, however, a 1D cellular automaton rule can be given as a set of explicit replacements for all possible blocks of cells in each neighborhood (see page 60 ). … I discuss the implementation of totalistic cellular automata on page 886 , and of higher-dimensional cellular automata on page 927 .

The pattern required to satisfy this constraint corresponds to a shifted version of the one generated by the evolution of the rule 30 elementary one-dimensional cellular automaton.

The behavior of an individual domain of black cells in the cellular automaton shown on the next page .

Some of these inputs will be positive if the Patches generated by a variety of one-dimensional cellular automaton rules.

But after searching through perhaps 50,000 rules, one finally comes across a rule of the kind shown below—in which the compressed pattern exhibits very much the same kind of apparent randomness that we saw in cellular automata like rule 30. … A mobile automaton that yields a pattern with seemingly random features.

Special-purpose hardware [for cellular automata] The simple structure of cellular automata makes it natural to think of implementing them with special-purpose hardware. And indeed from the 1950s on, a sequence of special-purpose machines have been built to implement 1D, 2D and sometimes 3D cellular automata. … Both ideas rely on the local nature of cellular automaton rules.