An example of a block cellular automaton. … Like many block cellular automata, the system shown is reversible, since in the rule each pair has a unique predecessor. … Block cellular automata with two possible colors and blocks of size two that conserve the total number of black cells (the last example has this property only on alternate steps).

Note (d) for Emulating Cellular Automata with Other Systems…Symbolic systems [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 (with {0, 0, 0}  0 ), the following will construct a symbolic system which emulates it: Flatten[{Array[(p[x_][#1][#2][#3]  p[x[{##} /. rules]][#2][#3]) &, {2, 2, 2}, 0] /. {0  p, 1  q}, {r[x_]  p[r[p][p]][x], p[x_][p][p][r]  x[p][p][r]}}] The initial condition for the symbolic system is given by Fold[#1[#2] &, r[p][p], init /. {0  p, 1  q}][p][p][r] Step t in the cellular automaton corresponds to step t (t + Length[init] + 3) in the symbolic system. … It is also possible to construct symbolic systems with the so-called confluence property, in which results from any fixed number of steps of cellular automaton evolution can be found by applying rules in any possible order (see page 1036 ).

The first set of pictures below show an example, based on the rule 184 cellular automaton. … As an example, the second picture below shows the rule 110 cellular automaton evolving from random initial conditions.

It turns out that as illustrated in the picture below rule 30 has a property somewhat like the additive cellular automaton discussed two pages ago : in addition to allowing one row to be deduced from the row above, it allows columns to be deduced from columns to their right. But unlike for the additive cellular automaton, it takes not just one column but instead two adjacent columns to make this possible.

Indeed, my expectation is that asking about possible outcomes of t steps of evolution will already be NP-complete even for the rule 30 cellular automaton, as illustrated below. … But it seems likely that as one increases t , no ordinary Turing machine or cellular automaton will ever be able to guarantee to solve the problem in a number of steps that grows only like some power of t .

Densities in other [cellular automaton] rules The pictures below show how the densities on successive steps depend on the initial density. … Page 339 shows a cellular automaton with very different behavior.

Discrete Voronoi diagrams The k = 3 , r = 1 cellular automaton {{0 | 1, n : (0 | 1), 0 | 1}  n, {_, 0, _}  2, {_, n_, _}  n - 1} is an example of a system that generates discrete 1D Voronoi diagrams by having regions that grow from every initial black cell, but stop whenever they meet, as shown below. Analogous behavior can also be obtained in 2D, as shown for a 2D cellular automaton in the pictures below.

Continuous Cellular Automata…In fact, it turns out that in continuous cellular automata it takes only extremely simple rules to generate behavior of considerable complexity. … And in fact, as the picture in the middle of page 160 shows, it is even possible to find cases that exhibit localized structures very much like those occasionally seen in ordinary cellular automata. A continuous cellular automaton whose rule adds the constant 1/4 to the average gray level for a cell and its immediate neighbors, and takes the fractional part of the result.

Note that to generate the pictures that follow requires applying the underlying cellular automaton rule for individual cells a total of about 12 million times.

Note that to generate the pictures that follow requires applying the underlying cellular automaton rule for individual cells a total of about 12 million times.