Symmetric Nonlinear Cellular Automata as Algebraic References for Rule~30

Dit artikel ontwikkelt een algebraïsch raamwerk rondom de symmetrische niet-lineaire celautomatenregel 22 als referentiepunt om de schijnbare willekeur en asymmetrische aard van regel 30 kwantitatief te analyseren.

De kern

Stel je voor dat je een heel lange rij van lichtknopjes hebt, die allemaal of aan (1) of uit (0) kunnen staan. Dit is een Cellulair Automaat. De regels zijn simpel: elk knopje kijkt naar zichzelf en zijn twee buren (links en rechts) en beslist dan of hij aan of uit gaat in de volgende seconde.

Er zijn 256 mogelijke regels voor hoe deze knopjes zich gedragen. De meeste zijn saai (alles gaat uit, of alles blijft hetzelfde), maar sommige maken prachtige patronen, en weer andere lijken op pure chaos.

Dit artikel gaat over twee specifieke regels: Regel 22 en Regel 30. Regel 30 is beroemd omdat hij zo'n willekeurig ogend patroon maakt dat het zelfs door Wiskundigen wordt gebruikt om willekeurige getallen te genereren. Maar waarom is hij zo willekeurig? En waarom is Regel 22, die er bijna hetzelfde uitziet, zo anders?

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen.

1. De Twee Gebroeders: Symmetrie vs. Chaos

De auteurs van het artikel kijken naar deze twee regels als twee broers die bijna identiek zijn, maar één klein, cruciaal verschil hebben.

• Regel 22 (De Perfecte Spiegel): Deze regel is symmetrisch. Het maakt niet uit of je de buren van links naar rechts of van rechts naar links leest; het resultaat is hetzelfde. Het is als een perfecte spiegel. Als je drie buren hebt die allemaal aan staan, doet de regel iets speciaals: hij "veegt" de chaos weg en maakt het weer netjes.

  • Het resultaat: Een mooi, voorspelbaar patroon dat lijkt op een Sierpiński-driehoek (een fractal), maar dan met wat extra vulling. Omdat het zo symmetrisch is, kunnen wiskundigen precies voorspellen hoeveel lichtjes er op elk moment aan staan. Het is als een machine die je volledig kunt doorrekenen.

• Regel 30 (De Gebroken Spiegel): Deze regel is bijna hetzelfde, maar hij heeft een asymmetrisch stukje in zijn formule. Hij behandelt de linkerbuur anders dan de rechterbuur.

  • Het resultaat: In plaats van een mooi patroon, krijg je een wirwar van lijnen die eruitzien als ruis op een oude TV. Dit is de "chaos" die zo bekend is.

2. De Vergelijking: Een Auto met en zonder Stuur

Om te begrijpen wat er gebeurt, gebruiken de auteurs een auto-analogie.

• Regel 22 is een auto die rechtuit rijdt op een rechte weg. Omdat hij symmetrisch is (links en rechts zijn hetzelfde), blijft hij perfect in het midden. De beweging is soepel en voorspelbaar, alsof je een parabolische bocht volgt. Wiskundig gezien is dit een "parabool" (een rustig, gebogen pad).
• Regel 30 is een auto met een kapotte stuurbekrachtiging die naar links trekt. Omdat de regel asymmetrisch is (hij houdt meer van zijn linkerburen), wordt de auto constant naar links getrokken. Dit zorgt voor een "hyperbolische" beweging: kleine foutjes worden snel groter, en de auto raakt volledig uit de hand. Dit trekt de chaos in gang.

3. Waarom is Regel 30 zo "Willekeurig"?

De grootste vraag over Regel 30 is: Is het echt willekeurig, of is het gewoon heel ingewikkeld?

De auteurs ontdekken het geheim door te kijken naar hoe gevoelig het systeem is voor veranderingen.

• Stel je voor dat je op t tijdstip één knopje aan de linkerkant omklapt. Bij Regel 30 heeft dit een enorme impact op wat er later in het midden gebeurt. Het is alsof je een steen in een stromende rivier gooit; de golf gaat rechtstreeks naar het midden.
• Als je een knopje aan de rechterkant omklapt, heeft dat veel minder invloed. De "stroom" van informatie gaat vooral van links naar rechts.

Dit noemen ze een asymmetrisch gevoeligheidsprofiel.

• De Metafoor: Denk aan een gesprek in een luid café. Bij een symmetrisch systeem (Regel 22) horen links en rechts even goed. Bij Regel 30 is het alsof er een windhoos is die alleen van links naar rechts waait. Alles wat links gebeurt, wordt direct en krachtig doorgegeven naar het midden. Alles wat rechts gebeurt, wordt weggeblazen.

Omdat de linkerkant elke seconde nieuwe, onafhankelijke informatie (een "muntworp") toevoegt aan het midden, wordt het patroon in het midden onmogelijk te voorspellen zonder de hele geschiedenis te kennen. Het voelt als willekeur, maar het is eigenlijk het gevolg van deze eenzijdige stroom van informatie.

4. Wat hebben ze ontdekt?

De auteurs hebben drie grote dingen gedaan:

1. Ze hebben de formule voor Regel 22 opgelost: Ze kunnen precies zeggen hoeveel lichtjes er aan staan op elk moment, zonder te hoeven simuleren. Het is een mooie wiskundige formule.
2. Ze hebben de "breuk" gemeten: Ze hebben gekeken hoeveel Regel 30 afwijkt van de perfecte symmetrie van Regel 22. Die afwijking groeit op een heel specifiek, voorspelbare manier (als een machtswet). Dit laat zien dat de chaos niet zomaar uit het niets komt, maar het gevolg is van dat ene gebroken symmetrie-element.
3. Ze hebben de "motor" van de chaos gevonden: Ze tonen aan dat de schijnbare willekeur van Regel 30 komt door de combinatie van twee dingen:
   • De regel is "links-permutatief" (de linkerbuur bepaalt alles).
   • De asymmetrie zorgt ervoor dat deze linkerburen als onafhankelijke muntworpen werken die de chaos voeden.

Conclusie

Dit artikel zegt eigenlijk: "Chaos is niet altijd mysterieus; soms is het gewoon symmetrie die is gebroken."

Als je een systeem bouwt dat perfect symmetrisch is (zoals Regel 22), krijg je mooie, voorspelbare patronen. Maar zodra je die symmetrie breekt (zoals bij Regel 30), krijg je een systeem dat zich gedraagt als een stromende rivier die alles meesleurt. De "willekeur" van Regel 30 is dus geen magie, maar het logische gevolg van een onbalans in de regels.

Het is een prachtige ontdekking die laat zien dat als je kijkt naar de onderliggende structuur (de symmetrie), je de sleutel kunt vinden tot het begrijpen van zelfs de meest chaotische systemen.

Technische samenvatting

Titel: Symmetrische Niet-lineaire Cellulaire Automaten als Algebraïsche Referenties voor Regel 30

Auteurs: E. Chan-López en A. Martín-Ruiz
Context: Complex Systems (voorgesteld op arXiv:2604.00165v1)

---

1. Het Probleem

Elementaire cellulaire automaten (ECA) zijn eenvoudige discrete dynamische systemen die toch een breed spectrum aan gedrag vertonen, van triviaal tot computationeel onoplosbaar. Regel 30 (een Class 3 automaat) is beroemd om zijn schijnbaar willekeurige output vanuit een eenvoudige deterministische regel.
Drie fundamentele open vragen over Regel 30, geformuleerd door Wolfram, blijven onbeantwoord:

1. Is de centrale kolom echt willekeurig?
2. Is de sequentie uiteindelijk periodiek?
3. Kunnen individuele celwaarden sneller worden berekend dan door expliciete simulatie (computationele irreducibiliteit)?

Bestaande algebraïsche benaderingen (zoals de Algebraïsche Normale Vorm of ANF over $\mathbb{F}_2$) hebben geleid tot complexe recurrenties en een exponentiële groei van de graad van de genererende polynomen, maar een gesloten formule voor het aantal actieve cellen ($|S_m|$) ontbreekt.

2. Methodologie

De auteurs hanteren een symmetrische vergelijkingsbenadering. In plaats van Regel 30 direct te analyseren, gebruiken ze Regel 22 als een symmetrisch referentiepunt.

• Algebraïsche Vergelijking:
  • Regel 30: $g_{30}(a,b,c) = a \oplus b \oplus c \oplus bc$ (Asymmetrisch, bevat het kwadratische term $bc$).
  • Regel 22: $g_{22}(a,b,c) = a \oplus b \oplus c \oplus abc$ (Volledig symmetrisch, bevat de kubische term $abc$).
  • Beide regels delen hetzelfde lineaire deel ($a \oplus b \oplus c$), maar verschillen in hun niet-lineaire correctie.
• Analyse van Regel 22: De auteurs analyseren Regel 22 volledig omdat de volledige $S_3$-symmetrie (invariantie onder permutatie van de drie invoerbits) wiskundige vereenvoudigingen mogelijk maakt die voor Regel 30 niet gelden.
• Overgang naar Continuüm: Door Taylor-ontwikkeling wordt de discrete update-regel gemodelleerd als een partiële differentiaalvergelijking (PDE).
• Sensitiviteitsanalyse: Er wordt gekeken naar de "Boolean sensitivity" (hoe waarschijnlijk het is dat het omdraaien van een invoercel de output verandert) om het mechanisme van willekeur te verklaren.

3. Belangrijkste Bijdragen en Resultaten

A. Gesloten Formules voor Regel 22

Voor de eerste keer worden gesloten vormen afgeleid voor de eigenschappen van Regel 22, die ook voor Regel 30 open vragen zijn:

1. Cardinaliteit van de Support-Set: Een formule voor het aantal actieve cellen $|S_m|$ op tijdstap $m$:
   $$|S_m| = 2^{\text{popcount}(\lfloor m/2 \rfloor)} \cdot 3^{m \pmod 2}$$
   Hierbij is $\text{popcount}(k)$ het aantal enen in de binaire representatie van $k$.
2. Recursieve Constructie: Een tweestaps recursie die de rol van het lineaire en niet-lineaire deel scheidt:
   • Oude stap (dikker maken): Voor oneven $m$ worden actieve cellen "dikker" door buren toe te voegen (effect van $abc$).
   • Even stap (decimatie): Voor even $m$ vindt een zelfgelijke decimatie plaats (analoog aan de Sierpiński-driehoek).
3. Lineaire Groei: De graad van de genererende polynoom $P_m(x)$ groeit lineair ($\deg P_m = m$), in tegenstelling tot de exponentiële groei ($F_{m+1}-1$) van Regel 30.

B. Het Continuüm-Limiet (PDE)

De auteurs tonen aan dat symmetrie de aard van de continue limiet fundamenteel verandert:

• Regel 22 (Symmetrisch): De eerste-orde transportterm ($u_x$) verdwijnt door symmetrie. Het resultaat is een parabolische reactie-diffusievergelijking:
  $$\partial_m u = u_{xx} + 2u + u^3$$
  Dit type vergelijking is bekend uit de wiskundige biologie en niet-lineaire golftheorie.
• Regel 30 (Asymmetrisch): Door het ontbreken van symmetrie blijft een transportterm ($v(u)\partial_x u$) over, wat leidt tot een hyperbolische PDE. Dit verklaart waarom Regel 30 zich anders gedraagt (transport van storingen) dan Regel 22.

C. Symmetriebreking en Afwijking

De auteurs definiëren de afwijking $\epsilon(m) = |S^{(30)}_m| - |S^{(22)}_m|$ als een maat voor het effect van het breken van de symmetrie (vervanging van $abc$ door $bc$).

• Empirisch blijkt deze afwijking te volgen een machtsfunctie: $\epsilon(m) \sim m^b$ met $b \approx 1.11$.
• Dit suggereert een zwak superlineair gedrag, wat de cumulatieve impact van de asymmetrische transportterm kwantificeert.

D. Mechanisme voor Schijnbare Willekeur (Regel 30)

Het artikel identificeert een specifiek mechanisme dat de willekeurigheid van de centrale kolom van Regel 30 verklaart:

1. Links-Permutativiteit: Regel 30 kan worden geschreven als $g(a,b,c) = a \oplus h(b,c)$. Dit betekent dat de linkse buur ($a$) via een XOR-operatie direct de output beïnvloedt, ongeacht de andere invoer.
2. Asymmetrisch Sensitiviteitsprofiel:
   • De sensitiviteit van cellen aan de linkerkant blijft constant hoog ($\approx 0.5$) over de hele tijd.
   • De sensitiviteit aan de rechterkant neemt af.
3. Conclusie: De linkse buur fungeert als een effectief onafhankelijke "coin flip" (muntworp) die elke stap ongeveer één bit aan nieuwe informatie injecteert. Dit, gecombineerd met de XOR-decompositie, resulteert in een maximale conditionele entropie, wat de schijnbare willekeur verklaart.

4. Betekenis en Conclusie

De studie biedt een nieuw perspectief op de complexiteit van cellulaire automaten:

• Symmetrie als Structuurprincipe: Symmetrie (zoals bij Regel 22) leidt tot algebraïsche behandelbaarheid, lineaire groei en parabolische PDE's.
• Symmetriebreking als Bron van Complexiteit: De breuk van deze symmetrie (zoals bij Regel 30) introduceert transporttermen, hyperbolische dynamiek en de mechanismen voor schijnbare willekeur en computationele irreducibiliteit.
• Implicaties: De resultaten suggereren dat de "complexiteit" van Regel 30 niet voortkomt uit het ontbreken van onderliggende regels, maar uit het breken van symmetrieën die anders voor structurele regelmaat zouden zorgen. De linkse permutativiteit is de discrete manifestatie van de transportterm in de PDE die de correlaties vernietigt.

Dit werk legt een brug tussen algebraïsche dynamica, partiële differentiaalvergelijkingen en de theorie van pseudorandom sequenties, en biedt een kwantitatieve basis voor het begrijpen van waarom Regel 30 zo moeilijk te analyseren is.