Elementary cellular automata
A row of cells. Each looks at itself and its two neighbors, then applies a rule to decide the next generation. There are exactly 256 such rules. Some produce nothing. Some produce chaos. One is Turing complete. Time flows downward.
cell(t+1) = rule[ left(t), center(t), right(t) ]
What are elementary cellular automata?
An elementary cellular automaton is the simplest possible one-dimensional cellular automaton. You have a row of cells, each either on or off. At each time step, every cell looks at itself and its two immediate neighbors — three binary values, eight possible combinations. A rule is a lookup table that maps each of these eight neighborhoods to an output: on or off. Since each of the eight outputs can be 0 or 1, there are exactly 28 = 256 possible rules. Stephen Wolfram systematically studied all of them, numbering each rule by interpreting its eight output bits as a binary number.
Wolfram's four classes
Wolfram classified the behavior of these 256 rules into four classes. Class I rules produce uniform final states — everything dies or everything fills in. Class II rules settle into periodic, repeating structures. Class III rules produce chaotic, apparently random patterns with no obvious structure. Class IV rules produce complex, localized structures that interact in intricate ways — the boundary between order and chaos, where computation lives.
Rule 30 — chaos from nothing
Rule 30 is the most famous Class III rule. Starting from a single cell, it generates a pattern that appears completely random on the left side while maintaining some structure on the right. Wolfram was so taken by this rule that he used the center column as a random number generator in Mathematica for years. The pattern produced by Rule 30 appears in nature: the pigmentation on the shell of the textile cone snail (Conus textile) follows essentially the same rule, each row of pigment cells responding to the state of the row laid down before it.
Rule 110 — Turing completeness
Rule 110 is a Class IV rule, and in 2004, Matthew Cook proved that it is Turing complete — meaning that with the right initial conditions, Rule 110 can simulate any computation that any computer can perform. This is a staggering result. A one-dimensional rule with two states and a three-cell neighborhood, fully specified by eight bits, is as powerful as any computer ever built or that could ever be built. The proof works by showing that Rule 110 can simulate cyclic tag systems, which are known to be universal.
Rule 90 — the Sierpinski triangle
Rule 90 is an additive rule — the output is simply the XOR of the left and right neighbors. Starting from a single cell, it produces an exact Sierpinski triangle, the famous fractal. This is also equivalent to computing Pascal's triangle modulo 2. It is one of the most beautiful demonstrations of how fractal geometry can emerge from the simplest discrete dynamics.
Simple rules, complex behavior
The philosophical depth of elementary cellular automata is difficult to overstate. Here is a system with the simplest possible ingredients — binary cells, nearest-neighbor interaction, synchronous updates — and yet it produces the full spectrum of dynamical behavior: from death to periodicity to chaos to universal computation. This challenges the widespread intuition that complex behavior requires complex rules. It does not. Complexity is not something you put in; it is something that emerges.
Stephen Wolfram argued in A New Kind of Science (2002) that this observation has profound consequences for how we should understand the natural world — that simple programs, not equations, are the right framework for modeling natural processes. The book was controversial, praised for its ambition and criticized for its claims of novelty, but the core observation stands: the computational universe is rich beyond anything we would have predicted, and most of that richness is already present in the simplest systems we can write down.