Rule 30's crystal front
Grown from one black cell, Rule 30's left side is a crystal of repeating diagonals and its right side looks random. A New Kind of Science records where the crystal's period doubles, ending with “64 at 2,107,985,255 or more,” and how fast the boundary moves, about 0.252 cells per step. At some depths the crystal cannot fix its next diagonal by itself, as Rowland showed in 2006: one bit has to come from the chaotic layer beside it. We find that this layer is the same for every seed we tried. One such bit, at depth 1,420,878,969, decides whether period 64 starts at exactly 2,107,985,255 or later. We simulated that layer out to step 1.88 billion: the bit is 1, so the NKS figure is exact. The 0.252 belongs to the period-16 era. From step 117,324 on, the boundary moves at the difference-pattern speed of about 0.243.
Rule 30, single black cell
What the boundary is
Every diagonal parallel to the left edge eventually repeats. The periods are powers of two and only ever double. The NKS notes to chapter 2 (page 871) list where each period first appears: 2 at depth 3, 4 at 8, 8 at 29, 16 at 400, 32 at 87,867, and 64 at 2,107,985,255 or more. Depth counts cells in from the left edge, and OEIS A364239 lists the same depths plus one. Our simulation reproduces every one through period 32.
Now continue each diagonal's repeating pattern past the boundary, all the way to the right edge. You get a second, virtual Rule 30 history: a crystal filling the whole cone. The real pattern agrees with it on the left and differs from it on the right. So the boundary is exactly the left edge of a difference pattern between the real evolution and this virtual crystal. Switch the picture above to Difference from crystal to see it: the chaotic region is the orange damage.
That pins down how the boundary moves. Rule 30 is f(l, c, r) = l XOR (c OR r). A difference sitting at the right input r gets through only when c = 0. So disorder can leak one cell into the crystal exactly when the crystal cell beside the boundary is 0. These are one-step Boolean sensitivities, the same edges Steph's CA Trace Explorer draws. In the 10-million-step run the boundary moved one cell left on 58.9% of steps, held still on 14.7%, and moved right by one or more cells on the rest, when cells just past it happened to fall into step with the crystal.
The crystal takes bits from the chaos
Each crystal diagonal is driven by the two diagonals nearer the edge. When the inner one contains a 1, its resets fix the next diagonal completely. When the inner one is all white (which happens exactly when the two diagonals before it came out identical), the next diagonal only accumulates the one before it, and that pins it down up to complementing every cell. An odd sum doubles the period, which is the NKS criterion; an even sum keeps it. Either way, which of the two complements appears is a single bit that the crystal cannot supply. It comes from the chaotic layer beside the boundary, at the moment the boundary reaches that diagonal. At a doubling the two complements differ only by a time shift, so it is the even cases that change the future.
Rowland spotted these choices in 2006. He found the first even case at depth 53,208, and further ones at 58,287 and 72,576 on its two branches (columns 53,209, 58,288 and 72,577 in his numbering). Up to depth 2.1 billion, Rule 30 meets nine all-white driver transitions: the doublings at depths 3, 8, 29, 400, 87,867 and 2,107,985,255 (each one cell deeper than its all-white driver at d - 1), and even cases at 53,208, 58,287 and 1,420,878,969. The even bits decide a lot. Flip the one at 58,287 and the period-32 doubling moves from depth 87,867 to 229,338. Flip the one at 53,208 and another choice comes up at 72,576; one way it goes, the doubling lands at 291,257. Trying every combination from depth 400 on gives exactly 16 possible histories, with the period-32 doubling anywhere from depth 87,867 to 894,235. Rule 30 took the earliest.
Yet every seed we tried gives the same crystal. We ran 30 random seeds, 10 each 16, 1,000 and 100,000 cells wide. Each gave the same doublings and the same boundary trajectory, cell for cell, shifted in time by between −52 and +132 steps. That can only happen if the chaotic layer next to the boundary is also seed-independent, and it is: comparing two seeds over 600,000 steps, the patterns agreed for between about 300 and 1,800 cells past the boundary. The layer is slaved to the crystal's own history, so the crystal's free bits come out the same wherever you start. Rowland was tempted to conjecture just this, that there is “really only one ‘left side’ of rule 30,” but judged it likely false. Out to step 150,000, which covers his first branch points, our seeds agree with the conjecture. Pick random 24 cells above to see the same crystal appear.
The bit behind “or more”
Following the period-32 crystal on its own takes us much deeper than any full simulation. The recurrence reproduces all 7.5 million simulated diagonals with no mismatches, then reaches the next all-white driver at depth 1,420,878,969, with an even sum. If the bit there is 1, the crystal runs on with no further choice and period 64 first appears at depth 2,107,985,255, exactly the NKS figure. If the bit is 0, nothing doubles before depth 3,340,408,060, where another free bit appears; taking 0 there too leads to a third at 4,989,445,008 and no doubling before depth 7.5 billion. So 2,107,985,255 is the earliest the doubling can come, which is what “or more” says.
Which way Rule 30 actually goes is decided by the chaotic layer when the boundary arrives. We simulated a 600,000-cell band around the boundary from step 2,000,000 to step 1,877,449,410, twice, with different cells invented at the band's far end. The two runs agree at every checkpoint, and both read the bit at step 1,877,349,410: it is 1. Period 64 first appears at depth 2,107,985,255, exactly as NKS says, and the next term of OEIS A364239 is 2,107,985,256.
How far away is period 128?
An era ends at an all-white diagonal, which needs the two diagonals before it to match in all P cells: a 1-in-2^P coincidence if they look random. There is a counting reason to expect exactly that. The recurrence also runs backwards, because each diagonal can be recovered from the two after it. So within an era the crystal follows a path through the 4^P possible pairs of diagonals that never repeats. The 2^P − 1 possible starting points share those pairs between their paths, so the average path is about 2^P diagonals long, and exactly 2^(P−1) of the possible endings have an odd sum. Enumerating every start up to P = 16 confirms it: the average is within 0.4% of 2^P, and the lengths spread out like waiting times. Samples of starts for periods 18 to 32 agree within their noise, and Rule 30's own waits fall at ordinary places in these distributions. An era should therefore last about 2^(P+1) diagonals: 4, 8, 32, 512, 131,072 and 8.6 billion, against Rule 30's 3, 5, 21, 371, 87,467 and 2.1 billion.
For period 64 that is 2^65 ≈ 3.7 × 10^19, so the next depth is probably a 19- or 20-digit number, most likely a few times 10^19. The path from depth 2,107,985,255 to the next all-white diagonal is already fixed, with no coin flip on the way. But as far as anyone knows it has to be followed one diagonal at a time, for roughly 10^19 steps. The no-repeat argument also proves the era must end. A path that cannot repeat runs out of pairs within 4^64 = 2^128 steps, whatever the chaos chooses at the even cases, so period 128 is certain before depth about 3.4 × 10^38. Nersissian (2026) proves that the periods are unbounded.
The speed changes when the crystal's period doubles
We ran the pattern for 10,000,000 steps with an exact bit-parallel simulation. The boundary reaches the first period-32 diagonal at step 117,324. Before that it moved left at 0.2511 cells per step. That window contains Wolfram's own 2019 measurement of about 0.252, taken “over the first 100,000 or so steps.” Afterwards it moves at 0.24315 ± 0.00003, measured over 1.87 billion steps in the band simulations; the 10-million-step run alone gives 0.2433 ± 0.0004. Cut into windows of 117,324 steps, the first window (period 16) is faster than every one of the 84 that follow.
Shorter stretches wander, as a diffusing boundary should, by about ±0.0011 per million steps. An independent replication by Claude Fable measured 0.2413 ± 0.0010 over steps 117,324 to 1,317,324, and our run gives the same over that stretch (0.2416). Over the full 10 million steps the average is 0.2433.
So the period-16 era ran about 3% faster than what follows. After the doubling, the boundary is within 0.2% of the difference-pattern speed: 0.2437 ± 0.0002 in our runs and 0.2428 in NKS. A small gap of 0.0005 ± 0.0002 between the period-32 boundary and our damage measurement remains, and we can't yet say whether it is real.
Boundary speed in consecutive 117,324-step windows
The crystal's period sets the speed
Rule 30's own history happens only once, so we built more crystals. We forced the two outermost diagonals to random repeating words of period P, let the crystal grow from them into random cells, and measured the front, 80 runs per period over 100,000 steps each. For periods of 24 and up the front moves at 0.2433 ± 0.0003, close to the 0.2437 ± 0.0002 at which damage spreads through random Rule 30. Period 16 is measurably faster, at 0.2469 ± 0.0005.
The cleanest test runs inside single systems. In 61 runs a period-16 crystal doubled to period 32 partway through. In the same run, the boundary slowed by 0.0046 ± 0.0007 cells per step after the doubling. A separate Python implementation that shares no code with the C one gives the same split: 0.2476 ± 0.0005 for period 16 and 0.2435 ± 0.0004 for period 32. Claude Fable's independent replication found 0.2463 ± 0.0008 and 0.2428 ± 0.0008.
Front speed against crystal period (synthetic crystals, mean ± 2 s.e.)
Table
| Period | Runs | Speed (cells/step) | Std. error |
|---|
Audit of the S = E classification
Astra's report left one check open: an independent look at the 246 computational exclusions. We rewrote the experiment from the definitions alone. Our code reproduces every number in the report, including the witness triangles, all four depth totals and the depth-4 controls. Exactly the ten listed rules satisfy S = E, and all 246 others fail at depth 2. We also classified three related properties for the explorer. All four classifications are now proved for every depth: each rule that passes has an all-horizon proof, and each rule that fails has an explicit small counterexample.
| Property (all configurations, all horizons) | Rules passing through depth 8 | First failure of the rest | Status |
|---|---|---|---|
| S = E: a sensitive path exists exactly when the flip changes the target | 10 | all at depth 2 | all 10 proved, by hand and by a window invariant; exclusions independently reproduced |
| P = E: path count mod 2 equals the effect | 18 | all at depth 2 | the 16 affine rules plus 4 and 223, all proved, by hand and by a window invariant |
| E ⇒ S: no path means no effect | 32 | depth 2, except 35, 49, 59, 115 at depth 3 | all 32 proved: an exact classification |
| S ⇒ E: a path means a real effect | 76 | all at depth 2 | all 76 proved: an exact classification |
How the all-depth proofs work. Run the baseline, the flipped run, the sensitive-path set and its parity side by side as one cellular automaton, and each property becomes a cell-by-cell invariant. A sound invariant search over windows of k cells (every window of every reachable state lies in a closed set of windows that never violates the property) proves S = E and P = E for all their rules at k = 3, and E ⇒ S for rules 36 and 219 at k = 5. The 16 centre-permutive rules, where flipping the middle input always flips the output, need a non-local argument: their sensitive-path set only grows and is always an interval around the source, and a change one cell outside it has a single changed parent, which must be sensitive. A local lemma covers the rest. If every multi-input change at an image neighbourhood that alters the output also contains a single sensitive input, then following sensitive edges back through changed cells reaches the flip. For S ⇒ E, 64 of the 76 rules are monotone in each input, with the left and right inputs pointing the same way. Then all the changes at a given step push outputs in one direction, nothing can cancel, and a sensitive path always carries the change through. The window search covers the other 12.
Known, new, and not yet settled
Already known
- The left diagonals' doubling depths (3, 8, 29, 400, 87,867, and 64 at 2,107,985,255 or more), the white-stripe and odd-parity doubling criterion, and the boundary speed of about 0.252: NKS notes to chapter 2, page 871 (2002).
- The two-way choices at even all-white diagonals (first at depth 53,208, then 58,287 and 72,576 on its branches) and the question whether different initial conditions give different left sides: Rowland 2006, section 5.
- A proof of the doubling criterion: Rowland 2006; see also Brunnbauer 2019, OEIS A364239, and unbounded periods in Nersissian 2026.
- The difference-pattern speed of 0.2428 and the “similar but not identical” remark: NKS notes to section 6.3. The 0.252 measured over the first 100,000 or so steps: Wolfram 2019.
- Sensitivity paths versus actual damage in cellular automata: Bagnoli, Rechtman and Ruffo 1992.
New here, as far as a targeted search found
- The boundary is the left edge of a difference pattern against the continued crystal, and its moves follow one-step sensitivity.
- The boundary speed depends on the crystal's period. The quoted 0.252 is the period-16 value; from step 117,324 the speed is 0.24315, within 0.2% of the difference-pattern speed. Synthetic crystals and a paired doubling test show the period is the cause.
- The bits Rowland identified come from the chaotic layer beside the boundary, and that layer is the same for every seed we tried, so those seeds share one left side (tested to step 150,000).
- NKS's “64 at 2,107,985,255 or more” is exact: the free bit at depth 1,420,878,969 is 1, read from a simulation of the boundary layer to step 1.88 billion.
Not settled
- All of this is measurement, not proof. Rule 30's own period-16 window is a single 117,324-step realisation; its gap from the later speed is about 2.7 standard deviations, and the controlled experiments carry most of the weight.
- Seed independence is tested to 150,000 steps. In the period-32 era the seed-dependent region seems to creep back toward the boundary, by about 1.2 cells per 10,000 steps in our band simulations, so over billions of steps different seeds might eventually read different bits.
- Period 128. The next all-white diagonal is already fixed by the numbers above, but it is expected around 10^19 diagonals away, and whether it doubles the period is close to a coin flip.
- Why period 16 is faster is open. The front advances just as often in both eras; after a period-16 advance, fewer cells beyond it happen to fall into step.
- Nothing here proves anything about the Rule 30 prize problems. It does bear on a worry raised next to them, that the ordered left side might one day fluctuate across the centre column. The boundary does change speed when the crystal doubles, but for periods of 24 and up the speed settles at the damage speed, about 0.243 cells per step away from the centre.
How it was computed
- Edge frame: measure depth from the moving left edge. Then at+1(d) = at(d−2) XOR (at(d−1) OR at(d)), so depth d never depends on deeper cells. Truncating at any depth is exact below it.
- Boundary at step t: the first depth not yet on its periodic tail, read as the first difference between the rows at t + 64 and t. Once a prefix matches with a fixed lag it matches forever, so the test is exact.
- C, 64 cells per machine word, 10,000,000 steps; a Python implementation agrees step for step to 1,000,000. The crystal recurrence, followed from depth 0 with the seven observed bits, reproduces every simulated diagonal to depth 7,500,000.
- Beyond 10 million steps we simulate only a band of 600,000 cells around the boundary. Since depth never depends on deeper cells, the band stays exact until cells invented at its far end could reach the boundary; two runs with different invented cells must agree, and both reproduce the full simulation's boundary exactly from step 2,000,000 to 9,750,000.
- An independent review by Claude Fable replicated the main numbers with its own code and found the page-871 list and the even-sum bits at 53,208 and 58,287, which an earlier version of this note missed. Both were already in print, in NKS and in Rowland 2006.
- Possible histories and era lengths:
chains.cfollows the recurrence on cyclic P-cell words. It enumerates every era start for P ≤ 16, samples period-32 starts, and follows every combination of free bits from Rule 30's own state at depth 400. Its fast solver reproduces all nine of Rule 30's all-white diagonals to depth 2,107,985,255. - The write-up for a general audience is The bit behind Wolfram's “or more”.