Eight rules and a triangle

Every system in this field so far has iterated a number. This one iterates a row.

Take a line of cells, each on or off. To get the next row, look at each cell together with its two neighbours — three cells, so eight possible patterns — and consult a table saying what each pattern produces. Apply the table everywhere at once, and repeat.

A rule is eight bits. Read as a binary numeral they give a number between 0 and 255, which is the rule’s name. That is all the notation there is, and Wolfram’s numbering — introduced in 1983 — has stuck because nothing simpler was available.

What one byte does #

Start from a single live cell in an otherwise empty row and run rule 90 downward.

That is the Sierpiński triangle, and it arrived from a rule that mentions no triangles, no scaling and no geometry. The rule is local — every cell sees three cells — and the pattern is global, and nothing in the eight cases hints at the shape.

It is also, exactly, Pascal’s triangle modulo two. Cell $k$ of row $n$ is on precisely when $\binom{n}{k}$ is odd, which this collection has already drawn from binomial coefficients in a completely different field with completely different code.

Two routes to one picture #

The agreement is the strongest check available on either of them, and it is worth seeing why it holds rather than just noting it.

Rule 90 says a cell is the exclusive-or of its two diagonal parents. Pascal’s rule says an entry is the sum of its two parents. Modulo two, sum and exclusive-or are the same operation — adding one to one gives zero under both. The two constructions have identical recurrences and identical starting rows, so they produce identical grids, and nothing further is needed.

The generator does not take that argument on trust. It computes the parity of $\binom{n}{k}$ independently, via Lucas’ theorem — the entry is odd exactly when $k$’s binary digits are a subset of $n$’s, which is the single expression (k & ~r) === 0 — and asserts the automaton’s cell equals it, for every cell of the first forty rows. Two unrelated computations agreeing at eight hundred places is worth more than either one looking right.

That is this site’s standing habit stated as a test: a figure should be checkable against something that is not itself.

It is worth noticing what the agreement rules out and what it does not. It rules out an error in either implementation, since a single wrong cell in either would break the comparison at that cell. It does not rule out the possibility that both are computing the wrong thing — if the neighbourhood convention were mirrored in both, the check would still pass. That is why the other assertion matters: the rule table is rebuilt from the drawn squares and compared to the number 90, which pins the convention to something a reader can count off the first figure.

Two checks of different kinds, neither sufficient alone, is the usual shape of a verified figure here.

Why 256 and not more #

The count is worth deriving once, because it explains what “elementary” is excluding and how fast the alternatives grow.

A neighbourhood is three cells, each on or off, so there are $2^3 = 8$ of them. A rule assigns one bit to each, so there are $2^8 = 256$ rules. That is the whole arithmetic, and it is the reason this family can be studied exhaustively: 256 is small enough to run every member and look at all of them, which has been done.

Widen the neighbourhood to five cells and there are $2^{32}$ rules — four billion, already past exhaustive study. Allow three states instead of two, with three-cell neighbourhoods, and there are $3^{27}$, about seven and a half trillion. The elementary family is the largest one that fits in a single afternoon’s computation, and it is the only cellular-automaton family whose members have all been looked at.

Of the 256, many are duplicates. Reflecting left-right and swapping on for off both give rules that behave identically up to a relabelling, so the 256 collapse to 88 genuinely distinct behaviours. Rule 90’s mirror is itself; rule 30’s is rule 86, which draws the same picture backwards.

The other 255 #

Rule 90 is not typical. Running all 256 rules and looking at what they do gives four rough classes, which is the crude taxonomy Wolfram proposed and which has survived as a description if not as a theory.

Dies out. The row goes uniformly blank or uniformly full within a few steps. Rule 0 does it immediately; rule 255 fills everything. Whatever the starting row was, it is gone within a handful of steps and unrecoverable — the map has collapsed the whole state space onto one point.

Settles into stripes. A periodic pattern in space, repeating in time. Rule 4 leaves isolated cells alone; rule 250 makes a plain triangle of alternating cells. The distinguishing feature is that a change made anywhere stays where it was made: perturb one cell and the damage stays local instead of spreading, which is the cellular version of a perturbation dying out.

Never settles, and looks random. Rule 30 is the standard case.

Structured, but not periodic. Localised patterns that move, persist and interact.

Rule 110 is the case, and it turns out to be able to compute anything.

The classification is informal — the boundaries between the classes are not defined and some rules do not fit — but the fact that a system this simple exhibits all four is the reason the family is studied at all.

Starting from noise instead #

Every figure so far starts from one live cell, which is the cleanest experiment and not the typical one. Starting from a random row asks a different question: not what the rule builds but what it does to an arbitrary state.

The classes above are properly statements about random starts. A rule that dies out does so from almost any row; a rule that makes stripes finds them from almost any row; rule 30’s noise is a property of the rule, not of the single-cell start that happens to display it neatly.

The single-cell picture is still the more informative one for a different reason. It shows the rule’s light cone — how fast influence spreads. Each step a cell can only affect its immediate neighbours, so after $n$ steps nothing outside a distance $n$ has changed, and the triangular outline of every single-cell figure on this page is that speed limit drawn. Locality is the one structural constraint in the whole family, and it is visible in every picture.

The row must repeat #

The strips above are drawn on a finite ring of cells, which forces a conclusion before any rule is chosen.

A ring of $n$ cells has exactly $2^n$ possible rows. The rule is deterministic, so the next row is a function of the current one, and a sequence of rows drawn from a finite set must eventually revisit one. Once it does, everything after repeats exactly — the run is periodic from that point, forever.

That is the pigeonhole principle applied to a state space, and it is one of the few things provable about every rule at once. No elementary cellular automaton on a finite ring is genuinely aperiodic. Rule 30’s open problem is about the infinite line, where the argument does not apply.

The bound it gives is useless in practice, which is the interesting part. On a ring of 100 cells the period could be anything up to $2^{100}$, a number larger than the count of atoms in a great many things. So “eventually periodic” is a theorem with no observational content: a run that will repeat after $10^{30}$ steps is indistinguishable from one that never does, and the guarantee says nothing that can check. It is the same shape as a walk that returns with probability one and takes an infinite expected time to do it.

The rule 30 column #

Rule 30’s centre column deserves its own paragraph because of what was done with it.

The middle column of that figure is a bit sequence. It has no detected period, passes the standard randomness batteries, and was used as the random number generator in Mathematica for years. Its state is a row of cells; its rule is eight bits; its output is indistinguishable from noise by any test tried.

Whether it is actually aperiodic is unknown. Wolfram offered a prize for a proof either way in 2019 and it stands unclaimed. So a rule with eight bits in it has an open problem attached, and the open problem is the simplest question that can be asked about the output.

The rules that add #

There is a subfamily where everything is computable in closed form, and its boundary explains a lot about which rules have shortcuts.

A rule is additive when its output is the exclusive-or of some fixed subset of its three inputs. Rule 90 is left xor right; rule 60 is left xor centre; rule 150 is all three. There are eight such rules, and they are the ones with a formula.

Additivity buys a superposition principle: run the rule from two separate live cells and the result is the exclusive-or of the two single-cell runs. So the behaviour from any starting row is the combination of the behaviours from each of its live cells taken alone, which reduces a run from an arbitrary row to a sum of copies of one triangle. That is the shortcut, and it is why these rules produce exactly self-similar pictures.

Every other rule lacks it. Rule 30 from two live cells is not the combination of two rule-30 triangles, because the interaction where they meet is not a sum, and that failure of superposition is the whole difference. Linearity is the property that makes a system solvable, and it is as decisive here as it is for a differential equation — eight rules out of 256 have it and those eight are the ones with answers.

What cannot be run backwards #

Ask the reverse question — given a row, what was the row above it? — and most rules have no answer.

Rule 90 maps many rows to the same successor. A row of all zeros comes from all zeros, and also from the alternating row on a ring of even length; two different pasts, one present. So the rule is not invertible, information is destroyed at every step, and the past cannot be reconstructed from the present.

Six of the 256 rules are invertible, and they are the trivial ones — shifts and complements, which do nothing but move or flip. Everything with interesting behaviour destroys information.

That is worth setting beside the moves that cannot be undone: irreversibility here is not a limitation of the analysis but a counting fact about the map, and it is exactly why the state eventually cycles rather than wandering forever. A reversible rule on a finite ring visits a cycle from step one; an irreversible one first funnels down a transient into whichever cycle it lands in, and the transient is where all the pictures on this page live.

What makes this different from the last field #

Two structural differences are worth naming, because they change what the questions are.

The state is not a number. An interval map has a state in $[0,1]$ and a picture with an axis. Here the state is a row of $n$ cells, so the state space has $2^n$ points and no useful ordering. Cobwebs, derivatives and Lyapunov exponents all need a notion of “nearby” that a bit-string does not obviously have.

Everything is finite and exact. No rounding, no floating point, no shadowing lemma. A computed run of an automaton is the run — the only errors possible are programming errors. That is a real advantage: every figure in this essay is exactly what the rule does, which is a claim no chaotic orbit drawn on this site can make.

The cost is that the tools of the last field do not transfer. What replaces them is a question about computation rather than about geometry, and that is where the next rung goes.

Where the complication comes from #

It is worth being precise about what is surprising here, because “simple rules give complex behaviour” is easy to say and easy to say vacuously.

The rule is eight bits. The initial condition is one cell. Everything the picture shows is therefore produced by nine bits of input plus the number of rows, and it is not compressible below that — no description of row 500 of rule 30 is shorter than running the rule 500 times.

That last clause is the substantive claim, and it has a name: computational irreducibility. For some rules there is a shortcut — rule 90’s row $n$ is given by a binomial coefficient, so row 500 can be written down without computing rows 1 to 499 — and for others there appears to be none. The difference between rule 90 and rule 30 is not that one is more complicated to state; it is that one has a closed form and the other does not.

The distinction is not aesthetic. It says that for some systems the fastest way to know the future is to let it happen — that simulation is not an approximation to understanding but the only route to the answer. If that is true of a rule with eight bits, an appeal to complexity is not available as an explanation for why some real system resists prediction: sensitivity made the answer unknowable from imprecise data, and irreducibility makes it unreachable even from exact data by any route shorter than running it.

Nobody has proved that rule 30 has no shortcut. What is known is that no one has found one, and that the same question for rule 110 has an answer that makes a shortcut impossible for a reason worth an essay of its own.