I will try to give only the briefest overview of cellular automata here, as there are already more than enough excellent introductions to the topic on the World Wide Internet.

A brief overview of cellular automata

A cellular automaton is a model of computation wherein a cyclic or unbounded array of individual cells each contain an integral value, often constrained to 0 or 1. Every such model is governed by a specific ruleset and is referred to singularly as a cellular automaton (CA).

CAs are configured to operate in one or more spatial dimensions. While there is no limit on this, the majority of research is limited to 1-D and 2-D models. Some models extend arbitrarily far as needed along each dimension, although for some purposes, finitely long wrap-around spans of cells are used. There is always a timelike progression which drives the computation: the combination of the specific ruleset and the initial cell values at \( t_0 \) completely determine the behavior of the CA as time progresses.

Like anything else, CAs have areas of strength and areas of weakness, relative to other models of computation. One of their great strengths is an innate capacity for massively parallel calculations, which is appealing as we increasingly face hard physical limits on serial computation speeds, and perhaps more to the point, begins to reveal shared properties with the concept of Newtonian spacetime and other facets of the "real world."

But perhaps the greatest strength of CA models is their underlying simplicity. While they can be made arbitrarily complicated, they rarely are, and more importantly, don't need to be. The simplest species of CA are known as Elementary Cellular Automatons (ECAs), shorthand for the 256 simplest rulesets that aren't all trivial.

The elementary cellular automata

Every ECA consists of only one spatial dimension. Each cell takes only two possible values, and bases its behavior solely on its own value and those of its two immediate neighbors. The precise rule for updating that value is what distinguishes the 256 ECAs from one another. Every cell in a standard cellular automaton operates under precisely the same rules as every other cell—it is only the different values of their neighbor cells which allow variation in their behavior.

One of the simplest rules we might have would be to check the value (often called "color") of the cell to your right and then change your own value to match. On the next time step, the cell to your left will do the same thing you just did, and so that value will move a step further; indeed, every starting value will propagate at a constant rate to the left with this rule. When studying ECAs, time is typically depicted as moving down on the y-axis, yielding a 2-D snapshot of what actually takes place over every moment along that one line of cells. The example discussed here would present as a diagonal line crossing space and time in such a plot.

Many rules are along the lines of the straightforward propagation example we just gave, but Rule 170 fits that description most precisely. In this rule diagram, the lower middle cell denotes what the middle cell will become after one time step, based on the values of itself and its neighbors as depicted above it. For these simple CAs, there are only 8 such rules, which together completely define the behavior of the model; this is why there are only \(2 ^ {2 ^ 3} = 256 \) possible rules at this level of simplicity.

What a ruleset actually looks like

To be precise, the top line in each icon shows the given cells \( c_{i-1}, c_{i}, c_{i+1} \) at time \( t_k \), with the cell below showing the resulting value of \( c_i \) at \( t_{k+1} \). As discussed in our example, we see that the new center cell simply copies whatever color was previously on its right side.

The rules for ECA 170.

This is a fairly boring ruleset and results in a fairly boring spacetime plot—scrolling down, you can find Rule 170 near the bottom right, sporting plenty of diagonal lines.

Note that a comparable rule that merely pushes everything to the right instead of the left is essentially the same thing. In fact, each of the 256 ECAs is identical in spirit to 1 or 3 other rulesets due to left-right mirroring and/or complementary value-inversion rules, leaving only 88 truly unique CAs. These are shown below with the identical rule numbers listed (see Wolfram codes) with the top, bolded number featured in the plot. The plots themselves are of a 128-cell wide cyclical configuration captured for 128 time steps.

...and what a ruleset actually looks like:

The 88 elementary cellular automata.
An aside: Conway's Game of Life

Undoubtedly the most famous example of a CA is Mike Conway's Game of Life, a 2-D model. Despite extremely straightforward rules of operation, it yields surprising complexity; it has long since been proved Turing Complete, meaning it is able to carry out any computation that any other TC model can, and is therefore subject to a number of undecidability and incompleteness proofs that have been established by Turing, Godel, Rice, and others over the 20th century.

For example, these results mean that it is impossible, in general, to know if one arbitrary configuration will ever lead to some other specific configuration; in fact, for infinitely many starting configurations, it is impossible to say anything of consequence about their eventual behavior, including whether they will ever stop changing or repeat themselves. But I digress. Excellent overviews of such impossibility proofs and an enormous amount of material are readily available on the Game of Life, so we'll leave that be.

Temporary graphic

(ignore below)

hi-res shots of Rule 54 structure flowing from a single toggled bit