The column rule 30 will not explain

Eight rules and a triangle introduced rule 30 as the standard case of a simple rule producing complicated behaviour, and gave its centre column a paragraph: the column was used as a random number generator for years, passes the standard batteries of statistical tests, and nobody can prove anything about it. A rule that remembers one row back made rule 30 reversible by a trick and ended by stating the three questions Stephen Wolfram posed publicly in 2019 about the original, forgetful rule. This essay measures the column and its surroundings, to see what the questions look like from the data and what the data cannot say.

The rule is the whole of it. A row of cells, each 0 or 1. At each step every cell is replaced by the cell to its left, combined by exclusive-or with the result of “itself or the cell to its right”. Start from a single 1 in a row of 0s, and the 1s spread out one cell per step in each direction, filling a triangle with a pattern that is regular on one side and irregular on the other.

Three questions about one column #

Read down the centre of the triangle, one cell per row, and the result is a sequence of 0s and 1s beginning 1101110011000101100100111. Wolfram’s three questions about it are, in plain words: Does the sequence ever become periodic? Does it contain 0s and 1s equally often in the long run? And can its $n$-th cell be computed with substantially less work than running the rule for $n$ steps? Each comes with a prize for a proof either way, and all three are unclaimed.

The three are not independent. A column that became periodic would have long-run frequencies that are simple fractions, which could still be a half but would make the third question easy, since a periodic sequence can be read off from its period. A column with a shortcut — a way to compute the $n$-th cell from a description of $n$ in a few operations — might or might not be periodic, but would be very far from the random-looking object the tests see. All three ask, in different ways, whether the column has a structure that a short description could capture.

The computations below run the rule for two hundred thousand steps. Rows are stored thirty-two cells to a computer word, and the whole run takes a second or two; the first two hundred rows are checked against the rule applied cell by cell. Two hundred thousand cells of the column are a tiny sample of an infinite sequence, and nothing measured on them can answer any of the three questions. What they can do is show what the questions are about.

The share of 1s #

The running share of 1s wanders around one half and settles towards it, ending at 0.50036 after two hundred thousand cells. Its wanderings stay inside the band a fair coin’s running share keeps to two-thirds of the time, a half plus or minus one over twice the square root of the number of cells. That is what a random sequence would do, and it is also what a great many non-random sequences would do: the digits of a rational number with an odd denominator and a long period, for instance, can look exactly like this for as long as one cares to look before the period ends.

A share that tends to a half is a weak property, but even it is not known. Nothing about the rule obviously balances 0s and 1s in the centre. The rule is not symmetric — swapping 0 and 1, or left and right, turns rule 30 into a different rule — and the column could in principle have a long-run share slightly different from a half, or no long-run share at all, its running average swinging between two values on longer and longer scales. The data are consistent with a half and say nothing about the limit.

Every block appears #

A stronger test looks at blocks: cut the column into overlapping pieces of $k$ cells, count how often each of the $2^k$ possible pieces occurs, and compare the counts with what a coin would give.

Every block of up to fourteen cells appears — all 16,384 of length fourteen — and at no length are the counts more uneven than a coin’s would be by more than about two standard deviations. At lengths four to six they are slightly more even than chance would usually make them, a mild oddity of the kind any finite sample shows somewhere. A sequence in which every block of every length eventually occurs with exactly its fair frequency is called normal, and the rule 30 column passes every check of normality that two hundred thousand cells can support.

Normality, like the share of 1s, is a property no finite computation can confirm, and it is the same situation that fractions repeat and roots look random described for the digits of square roots and of $1/\pi$: the numbers pass every statistical test, almost every number is normal by a theorem of Émile Borel, and for no particular natural number has normality been proved. The rule 30 column joins that list, and it adds a twist. The digits of $\sqrt 2$ are defined by arithmetic, and a proof about them might come from arithmetic; the column is defined by an eight-entry table, and there is no obvious theory from which a proof could come at all.

The diagonals are periodic #

The triangle has more structure than the column suggests, and it is visible by reading along diagonals instead of down columns. Take the cells exactly $d$ cells in from one edge of the triangle, one from each row, and ask whether that sequence repeats.

Every diagonal tested repeats. Along the left edge the cycles have length 1, 2 or 4, which is the regular striping visible on that side of the triangle. Along the right edge the cycle lengths are powers of two, and they grow going inwards — 1, 2, 2, 4, 8, 8, 16, 32, 32, 64, … up to 512 at 24 cells in. Each diagonal is periodic; the periods double every few cells; and the centre column, which is the diagonal infinitely far from either edge, sits at the end of a sequence of periods that grows without bound.

That is suggestive, and it is all that it is. It makes a periodic centre column look unlikely, because the periods near the column are already larger than any modest number, and they keep growing. It does not prove anything, because the centre column is not one of the diagonals, and a sequence of periodic sequences with growing periods can converge to almost anything. The structure explains why the triangle looks the way it does — regular stripes on the left, and on the right a texture of triangles of every size whose arrangement repeats only on scales that grow with the distance in — and it shows exactly why the column is hard: it lives where every finite description of the pattern has run out.

A change that always travels right #

One property of the rule explains why the two sides of the triangle look so different, and it can be read straight off the formula. The new value of a cell is its left neighbour combined by exclusive-or with something that depends only on the cell and its right neighbour. So if the left neighbour is flipped and nothing else, the new value flips too, whatever the other two cells hold. A single changed cell therefore always changes the cell to its right at the next step, which changes the cell to its right at the step after, and so on: a disturbance travels rightwards at one cell per step without ever dying out. Rules with this property are called left-permutive, and rule 30 is one.

Leftwards there is no such guarantee. A change in the right neighbour affects the new cell only through the OR, and an OR with a 1 already present hides the change. So disturbances spread left more slowly and irregularly, and the left side of the triangle, sheltered from the full force of what happens elsewhere, settles into the stripes the diagonals measured. The right side receives every disturbance at full speed and never settles.

That is the cellular-automaton form of the divergence of nearby orbits that marks chaotic systems: two rows that differ in one cell differ in a growing stretch afterwards. Measured as a rate, rule 30 spreads information at one cell per step to the right, which gives its rows a positive entropy, in the sense that an orbit written as a word attaches to a dynamical system: the number of distinguishable patterns of length $n$ grows exponentially with $n$. A rule with positive entropy is a rule whose future is not compressible below a fixed rate, and the centre column inherits that from the right side.

None of this bears directly on the three questions, which are about one particular sequence rather than about rows in general. Rows started from random configurations are where entropy and spreading speed are theorems; the single-cell column is a single orbit, and a system with positive entropy can perfectly well have particular orbits that are periodic. The left-permutive property shows why randomness is the natural expectation, and leaves the expectation unproved.

On a ring, the column must repeat #

The first question has an easy answer on a finite tape, and the contrast is instructive. Put the cells on a ring of $w$ cells, so the left neighbour of the first is the last. There are only $2^w$ possible rows, so the run must eventually revisit a row, and from then on it repeats: on a ring, the centre column is always eventually periodic.

The cycle lengths are erratic: 40 steps on a ring of eight cells, 72 on nine, 15 on ten, then 1,428 on fourteen, 247 on nineteen, 185,040 on twenty-four and 833,808 on twenty-nine. They tend to grow with the width while staying far below the number of possible rows — at width 29 the cycle visits fewer than one row in six hundred — and nothing simple predicts which widths give long cycles. The periods were found by Brent’s method — running a fast copy of the rule twice as far as a slow one and waiting for them to agree — and each was confirmed by running exactly one period from the repeated row and arriving back at it.

On the infinite tape the argument for periodicity disappears, because the triangle keeps widening and the number of possible rows is never finite. What the ring shows is that periodicity in rule 30 is a property of the tape rather than of the rule: confine it, and it repeats on a timescale that grows enormously with the room it has; release it, and the first question becomes open.

What a shortcut would need #

The third question asks for a shortcut: a way to compute the $n$-th cell of the column without running all $n$ steps. Running the rule to step $n$ costs about $n^2$ cell updates — the triangle has that many cells — so a shortcut would be anything substantially cheaper, for instance a computation polynomial in the number of digits of $n$.

Some rules have such shortcuts, and they are worth seeing because they show what a positive answer would look like. Rule 90, in which each cell becomes the exclusive-or of its two neighbours, grows Pascal’s triangle reduced modulo two from a single cell, and its $n$-th row is given by the binary digits of $n$: cell $k$ is 1 exactly when $\binom{n}{k}$ is odd, which can be read off in a few operations by Lucas’s theorem. The triangle of eight rules drew it. Rule 30 differs from rule 90 by a single OR, and that OR destroys the additive structure that made the shortcut possible: rule 90’s rows add, so the row from a sum of starting patterns is the sum of their rows, and rule 30’s do not.

Wolfram’s name for the expected answer is computational irreducibility: the belief that for rule 30 no shortcut exists, and the fastest way to find the $n$-th cell is to run the rule. Proving it would mean proving a lower bound on the cost of a specific computation, which is the kind of statement that complexity theory has almost never managed for natural problems; the formula that cannot share showed how far such bounds reach even for the simplest functions. A proof that rule 30’s column needs $n^2$ work, or even $n^{1.01}$, would be far beyond anything known.

Why a simple rule was used as a source of randomness #

The column’s practical history makes the questions sharper. For many years it served as the random number generator inside Mathematica, a large mathematical software system, because it was fast, passed the standard tests and came from a rule simple enough to reason about. The essays on randomness that has to be earned drew the line between generators that pass statistical tests and generators whose outputs are provably unpredictable from a hardness assumption; rule 30 sits on the first side of that line. It has never been broken, in the sense that nobody has found a way to predict its column from earlier cells better than chance, but nothing guarantees that nobody will.

In fact, used a different way, rule 30 has been broken. When a whole row of a rule 30 run is the secret key and the centre column is the output, the key can be recovered from enough output by working backwards through the triangle, and Willi Meier and Othmar Staffelbach found such attacks in 1991. The column from a single cell is not attacked this way, because there is no secret at all — it is completely determined — and the questions about it are purely about structure. That is why they are clean, and also why they are hard: there is nothing to exploit except the rule, and the rule is eight bits.

What the measurements cannot show #

Every figure here shows a finite stretch of an infinite object, and the three questions are about the infinite object. The share of 1s, the block counts and the absence of a period in the first two hundred thousand cells are all compatible with a column that becomes periodic at step $10^{100}$, or whose share of 1s drifts to 0.51 over scales far longer than any run.

The diagonal periods are measured up to row eight thousand and up to 24 cells in from each edge. That every diagonal is eventually periodic, and that the right-hand periods double, is what the measurements show within that range; that the pattern continues is not established here, and the doubling is irregular — sometimes after one step inwards, sometimes after eight — in a way the data do not explain.

Still open: one column, three questions #

Whether rule 30’s centre column is eventually periodic, whether its 1s have long-run frequency one half, and whether its $n$-th cell can be computed in fewer than about $n$ steps are all open. Partial results are known about the triangle’s edges and about rows started from random configurations, where rule 30’s behaviour can be analysed statistically, but the single-cell column has resisted every approach.

Two broader questions sit behind the three. Is there any elementary cellular automaton for which a statement of this kind — aperiodicity, a frequency, a lower bound on computation — has been proved for the single-cell column while the column looks random? And is there a natural class of simple rules for which the absence of a shortcut can be proved, in the way that the halting problem shows that some questions about simple machines have no algorithmic answer? A positive answer to the second would turn computational irreducibility from a belief into a theorem, and nothing yet points to how.