Cellular Automata

Elementary Cellular Automata

One line of cells, one 8-bit rule, 256 possible universes — and somewhere in them, every kind of complexity there is.

Each horizontal line is one generation; time runs downward. Drag the rule dial through all 256 numbers and watch the character of the pattern flip from dead to striped to fractal to chaotic. Try the famous rules, and switch the initial row between a single live cell and random noise.

What you're seeing

A single row of cells, each on or off, drawn at the top. From it we compute the next row, then the next, stacking each new generation directly below the last — so the picture you see is a space-time diagram: space across, time down. Every row is produced from the one above it by the same minuscule rule, applied to all cells at once. Nothing here is hand-drawn. The triangles, the Sierpiński gasket, the seething chaos — all of it falls out of one number between 0 and 255. Change that number and the entire character of the world changes with it.

The rule

Each cell looks at exactly three things: its left neighbor, itself, and its right neighbor. Three binary inputs means there are only 8 possible neighborhoods (000, 001, 010, … 111). The rule simply assigns a new state — 0 or 1 — to each of those 8 cases. That is 8 bits of information, i.e. a single number from 0 to 255: the rule number (Wolfram's numbering). The output for neighborhood (l, c, r) is bit number l·4 + c·2 + r of the rule. The edges wrap around (a ring), so the line has no boundary. This is the simplest non-trivial computational universe there is — and it is the one-dimensional ancestor of the two-dimensional Game of Life.

Why it matters

In the early 1980s Stephen Wolfram catalogued all 256 of these rules and noticed something that has shaped complexity science ever since: their behavior sorts into four classes.

The punchline is that complexity is not rare and not hard to find. You do not need a genome, a brain, or a differential equation. It is sitting inside a one-line rule on a line of bits. This is the cleanest possible illustration of the edge of chaos: the richest behavior lives right at the border between frozen order (Class I/II) and unstructured noise (Class III).

In the wild

These are abstract models, and it is honest to lead with that. Their value is as an existence proof: simple deterministic rules really do generate every class of behavior, chaos and computation included. A few real-world echoes:

Try this

References

  1. Wolfram, S. (1983). "Statistical mechanics of cellular automata." Reviews of Modern Physics 55(3), 601–644.
  2. Wolfram, S. (1984). "Universality and complexity in cellular automata." Physica D 10(1–2), 1–35. (The four classes.)
  3. Cook, M. (2004). "Universality in Elementary Cellular Automata." Complex Systems 15(1), 1–40. (Rule 110 is Turing-complete.)
  4. Wolfram, S. (2002). A New Kind of Science. Wolfram Media.