Rule 30: andere Startzeilen, dieselbe Entwicklung auf der linken Seite

Ich vergleiche zwei Startzeilen: eine mit einer einzigen Eins bei 0 und eine mit Einsen bei 0, 2, 4, 6, … . Alle anderen Zellen sind 0.

Die Zeilen unterscheiden sich an unendlich vielen Stellen. Trotzdem stimmen ihre Werte in der Mitte zu jeder Zeit überein. Dasselbe gilt an jeder Position links von der Mitte.

                    Mitte
Einzelzelle:    …000 | 1 | 000000…
Rechter Strahl: …000 | 1 | 010101…

Die Regel lautet neu = links XOR (mitte OR rechts). Mit F^t(u)(n) bezeichne ich den Wert an Position n nach t Schritten aus der Startzeile u. Die Zeilen sind über alle ganzzahligen Positionen definiert; die Positionen steigen nach rechts an.

Für die beiden Zeilen gilt:

F^t(Einzelzelle)(n) = F^t(rechter Strahl)(n)
für alle t ≥ 0 und alle n ≤ 0.

Die allgemeine Aussage

Sei u eine beliebige binäre Zeile. Ihre rechteste belegte Zelle liegt bei R≥1: u(R)=1, und für alle n>R gilt u(n)=0. Links davon ist die Zeile beliebig.

Dann gibt es eine Zeile v, die ab einer positiven Position nach rechts räumlich abwechselnd 1, 0, 1, 0, … enthält und für die gilt:

F^t(v)(n) = F^t(u)(n)
für alle t ≥ 0 und alle n ≤ 0.

Das abwechselnde Muster betrifft die Startzeile im Raum. Es sagt nicht, dass eine feste Zelle zeitlich abwechselnd 0 und 1 annimmt.

Das Einzelzellbeispiel hat R=0 und fällt deshalb nicht direkt unter die allgemeine Aussage. Es folgt aus der ersten Konstruktion unten: Bei R−1=-1 steht eine 0, und diese Konstruktion lässt die gesamte Entwicklung an allen Positionen n≤R unverändert.

So entsteht die neue Zeile

Es gibt zwei Fälle.

Die Zelle bei R−1 ist 0. Die Zeile bleibt bis Position R unverändert. Rechts ergänzen wir belegte Zellen bei R+2, R+4, R+6, …. Die Entwicklung an jeder Position n≤R bleibt gleich.

Die Zelle bei R−1 ist 1. Wir verschieben die rechteste belegte Zelle von R nach R+1 und lassen den Rest unverändert. An jeder Position n≤R−1 stimmen die Werte für alle t≥0 überein. Am neuen rechten Rand stehen bei R und R+1 die Werte 01. Dort können wir die erste Konstruktion anwenden.

Wegen R≥1 bleibt in beiden Fällen die Entwicklung an allen Positionen n≤0 gleich.

Warum die Änderungen rechts bleiben

Der Beweis nutzt zwei lokale Identitäten. Wir setzen E=R+t; das ist der nach rechts wandernde Rand der ursprünglichen Zeile.

Wenn u(R−1)=0 gilt, ergänzen wir zunächst nur eine Zelle bei R+2. Die beiden Entwicklungen unterscheiden sich dann genau an diesen Stellen:

t gerade:   {E+2}
t ungerade: {E, E+1, E+2}

Alle angegebenen Positionen liegen rechts von R, denn der ungerade Fall tritt erstmals bei t=1 auf. Die Identität folgt durch Induktion mit einer Prüfung der lokalen Regel am wandernden Rand. An der entscheidenden Stelle ist der mittlere Eingang der lokalen Dreiernachbarschaft in beiden Entwicklungen 1. Deshalb hängt mitte OR rechts dort nicht vom rechten Eingang ab.

Die neue äußerste Zelle hat wieder eine 0 direkt links neben sich. Wir können also zwei Positionen weiter rechts die nächste Zelle ergänzen und fortfahren. Jede endliche Ergänzung erhält denselben linken Bereich.

Der Übergang zum unendlichen Strahl nutzt die endliche Abhängigkeit der Regel. Für ein festes t und eine feste Position n wird der Wert nur von den Anfangszellen in [n−t,n+t] bestimmt. Eine hinreichend lange endliche Ergänzung stimmt dort mit der unendlichen überein. Damit gilt die Gleichheit an diesem Punkt für beliebige t und n≤R.

Beim Verschieben der äußersten Zelle im zweiten Fall lauten die Unterschiede:

t gerade:   {E, E+1}
t ungerade: {E+1}

Auch das folgt durch lokale Induktion. Die Unterschiede bleiben strikt rechts von R−1. Zusammen mit der anschließenden Ergänzung ergibt sich die allgemeine Aussage.

Was offen bleibt

Die ergänzte Startzeile enthält rechts unendlich viele Einsen. Die Konstruktion liefert daher weder eine endliche Startzeile für eine beliebig vorgegebene Mittelfolge noch eine Aussage über die spätere Periodizität der Mittelspalte beim Einzelzellstart.

Verwandte Arbeiten behandeln die Rekonstruktion in seitlicher Richtung, Diagonalstrukturen und Einschränkungen von Zeitspuren, darunter Wolframs Rekonstruktionsnotiz, Rowlands Arbeit über lokale Strukturen und Kopras Ergebnisse zu Zeitspuren. Ob diese genaue Konstruktion schon früher beschrieben wurde, habe ich nicht geklärt.

Quellen und Prüfungen

Diese Notiz verwendet den Quellenstand 85d7d83c06f692f3fa7d19af42b6c988e0f58ca0. Die allgemeine Aussage für R≥1 heißt Rule30.full_checkerboard_completion_exists in Phase20ExplicitCompletion.lean. Für das Einzelzellbeispiel mit R=0 gibt es eigene formale Beweise in Phase17InfiniteFiber.lean: Rule30.infiniteEvenRow_same_left_trace und Rule30.infiniteEvenRow_same_center.

Für diese Notiz wurden alle zehn dafür geprüften Lean-Module mit Lean 4.34.0 in einem frischen Verzeichnis neu gebaut. Der Lauf war erfolgreich. Ein KI-Agent hat außerdem das Randargument rekonstruiert und eine separate, zeitlich begrenzte Simulation ausgeführt. Die Simulation prüft endliche Fälle; die Aussage für alle Zeiten beruht auf dem Beweis und seiner Lean-Verifikation.