The Growth of Crystals At a microscopic level crystals consist of regular arrays of atoms laid out much like the cells in a cellular automaton. … As an idealization of this process, one can consider a cellular automaton in which black cells represent regions of solid and white cells represent regions of liquid or gas. … Cellular automata with rules that specify that a cell should become black if any of its neighbors are already black.

Intrinsic synchronization in cellular automata Taking the rules for an ordinary cellular automaton and applying them sequentially will normally yield very different results. But it turns out that there are variants on cellular automata in which the rules can be applied in any order and the overall behavior obtained—or at least the causal network—is always the same. The picture below shows how this works for a simple block cellular automaton.

It was in a certain sense lucky that one-dimensional cellular automata were the first examples of simple programs that I investigated. … And since several of the 256 elementary cellular automaton rules already generate great complexity, just studying a couple of pages of pictures like the ones at the beginning of this chapter should in principle have allowed one to discover the basic phenomenon of complexity in cellular automata. … I had the idea of looking at pictures of cellular automaton evolution at the very beginning.

The strategy for demonstrating universality in a two-dimensional cellular automaton is in general very much the same as in one dimension. … And as it turns out there was already an outline of a proof given even in the 1970s that the Game of Life two-dimensional cellular automaton is universal. Returning to one dimension, one can ask whether among the 256 elementary cellular automata there are any apart from rule 110 that show even signs of class 4 behavior.

In case (d), almost all cells are active, and the system operates essentially like a cellular automaton.

[Construction of] universal objects A more direct way to create a universal object is to set up, say, a 4D array in which two of the dimensions range respectively over possible 1D cellular automaton rules and over possible initial conditions, while the other two dimensions correspond to space and time in the evolution of each cellular automaton from each initial condition.

Lyapunov exponents If one thinks of cells to the right of a point in a 1D cellular automaton as being like digits in a real number, then linear growth in the region of differences associated with a change further to the right is analogous to the exponentially sensitive dependence on initial conditions shown on page 155 . The speed at which the region of differences expands in the cellular automaton can thus be thought of as giving a Lyapunov exponent (see page 921 ) that characterizes instability in the system.

Computational fluid dynamics From its inception in the mid-1940s until the invention of cellular automaton fluids in the 1980s, essentially all computational fluid dynamics involved taking the continuum Navier–Stokes equations and then approximating these equations using some form of discrete mesh in space and time, and arguing that when the mesh becomes small enough, correct results would be obtained. Cellular automaton fluids start from a fundamentally discrete system which can be simulated precisely, and thus avoid the need for any such arguments. One issue however is that in the simplest cellular automaton fluids molecules are in effect counted in unary: each molecule is traced separately, rather than just being included as part of a total number that can be manipulated using standard arithmetic operations.

Note (a) for Cellular Automata…Networks [as basis for cellular automata] Cellular automata can be set up so that each cell corresponds to a node in a network. … If the connections at each node are not labelled, then only totalistic cellular automaton rules can be implemented. Many topological and geometrical properties of the underlying network can affect the overall behavior of a cellular automaton on it.

Note (b) for Emulating Cellular Automata with Other Systems…Sequential substitution systems [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 , the following will construct a sequential substitution system which emulates it: CAToSSS[rules_] := Join[rules /. ({a_, b_, c_}  d_)  ({1, 2a, 2b, 2c}  {2d, 1, 2b, 2c}), {{1, 0, 0}  {0, 0}, {0}  {1, 0, 0, 0}}] The initial condition {0, 0, 2, 0, 0} for the sequential substitution system corresponds to a single black cell surrounded by white cells in the cellular automaton.