Rule 30: different starting rows, the same left-hand evolution

I compare two starting rows: one occupied only at position 0, and one occupied at 0, 2, 4, 6, … . Every other cell is 0.

The rows differ at infinitely many positions. Their center values still agree at every time. The same holds at every position to the left of the center.

                  center
single seed:  …000 | 1 | 000000…
right tail:   …000 | 1 | 010101…

Rule 30 uses the update next = left XOR (center OR right). I write F^t(u)(n) for the value at position n after t updates from row u. Rows extend over all integer positions, increasing to the right.

For the two rows above, the equality is:

F^t(single seed)(n) = F^t(right tail)(n)
for every t ≥ 0 and every n ≤ 0.

The general statement

Let u be any binary row with a rightmost occupied cell at R ≥ 1: u(R)=1 and u(n)=0 for all n>R. There is no restriction on the row to the left.

Then there is a row v whose right tail alternates 1, 0, 1, 0, … from some positive position onward, with

F^t(v)(n) = F^t(u)(n)
for every t ≥ 0 and every n ≤ 0.

Here “alternating tail” describes the initial row in space. It does not say that a fixed cell alternates over time.

The single-seed example has R=0, so it is not a direct instance of the general statement. It follows from the first construction below: the cell at R−1=-1 is 0, and this construction preserves the full evolution at every n≤R.

How to construct the row

There are two cases.

The cell at R−1 is 0. Keep the row through position R and add occupied cells at R+2, R+4, R+6, …. This preserves the evolution at every position n≤R.

The cell at R−1 is 1. Move the rightmost occupied cell from R to R+1, leaving everything else unchanged. The values at every position n≤R−1 agree for all t≥0. At the new right edge, the cells at R and R+1 are 01, so apply the first construction at R+1.

Since R≥1, both cases preserve the evolution at every n≤0.

Why the changes stay on the right

The proof uses two local identities. Put E=R+t, the moving right edge of the original row.

When u(R−1)=0, adding just one cell at R+2 gives these exact disagreement sets:

t even: {E+2}
t odd:  {E, E+1, E+2}

Every listed position is greater than R: the odd case first occurs at t=1. The identity follows by induction, checking the update near the moving edge. At the decisive step, the center input of the local three-cell neighborhood is 1 in both evolutions. The term center OR right therefore does not depend on the right input there.

The new rightmost cell again has a 0 immediately to its left. We can therefore add another cell two places farther right and repeat. Each finite stage preserves the same left region.

The infinite tail follows from finite dependence. For any fixed time t and position n, the output only uses the initial cells in [n−t,n+t]. A sufficiently long finite completion agrees with the infinite one throughout that interval. This proves equality at that point, for arbitrary t and n≤R.

For the second case, moving the rightmost occupied cell one position right gives:

t even: {E, E+1}
t odd:  {E+1}

The same local induction keeps these disagreements strictly to the right of R−1. Combining this edge move with the completion proves the general statement.

What this leaves open

The completed starting row has infinitely many occupied cells on the right. The construction therefore gives neither a finite starting row for an arbitrary prescribed center sequence nor a result about eventual periodicity of the single-seed center column.

There is related work on directional reconstruction, diagonal structure and trace restrictions, including Wolfram's reconstruction note, Rowland's local-structure paper and Kopra's trace results. I have not established whether this exact construction has appeared before.

Source and checks

This note uses source commit 85d7d83c06f692f3fa7d19af42b6c988e0f58ca0. The general R≥1 statement is Rule30.full_checkerboard_completion_exists in Phase20ExplicitCompletion.lean. The R=0 single-seed example has a separate formal proof in Phase17InfiniteFiber.lean: Rule30.infiniteEvenRow_same_left_trace and Rule30.infiniteEvenRow_same_center.

For this note, all ten Lean modules in the checked dependency set were rebuilt in a fresh directory with Lean 4.34.0. The build passed. One AI reviewer also reconstructed the edge argument and ran a separate bounded simulation. The simulation checks finite cases; the all-time statement relies on the proof and its Lean verification.