Regel 30: Eén zwarte cel

De groene kolom in het midden is het onderwerp van de prijzen van Stephen Wolfram. Terwijl elke rij verschijnt, wordt de middelste cel uitgelezen in de strook aan de rechterkant; tot nu toe ziet dit er precies uit als de worpen van een eerlijke munt.

1. De regel

Een regel die je met een potlood kunt uitvoeren

Stel je een rij vierkantjes voor, elk zwart of wit. Om de volgende rij te maken, kijkt elk vierkantje naar drie vierkantjes erboven: het vierkantje direct erboven, en de linker- en rechterburen daarvan. Deze drie kleuren kunnen in acht combinaties voorkomen, en de regel bepaalt simpelweg voor elke combinatie welke kleur het nieuwe vierkantje krijgt.

Schrijft men de acht antwoorden als een binair getal, dan krijgt men 00011110, wat 30 is. Dat is alles wat Regel 30 inhoudt.

In woorden: het nieuwe vierkantje is zwart wanneer het vierkantje linksboven verschilt van "het vierkantje erboven óf het vierkantje rechtsboven is zwart". Eén logische regel, overal hetzelfde, voor altijd toegepast.

2. Waarom het belangrijk is

Willekeur uit het niets

In het begin van de jaren 80 begon Stephen Wolfram systematisch te kijken naar de simpelste mogelijke programma's van dit type. Er zijn er slechts 256. De meeste doen iets saais: ze sterven uit, herhalen zich of vormen nette, geneste patronen.

Regel 30 doet dat niet. De linkerkant stabiliseert in regelmatige strepen, maar de rechterkant stabiliseert nooit, en de middelste kolom doorstaat de standaardtests voor willekeur.

Deze observatie — dat een zeer eenvoudige regel gedrag kan produceren dat willekeurig lijkt — werd een hoeksteen van Wolfram's A New Kind of Science (2002). Jarenlang genereerde Regel 30 de willekeurige gehele getallen van Mathematica. Het patroon siert de muren van het treinstation Cambridge North. En het was het onderwerp van een uitdaging.

"Het is bijna 40 jaar geleden dat ik Regel 30 voor het eerst zag — maar het verbazingwekkend me nog steeds."

— Stephen Wolfram, bij de aankondiging van de Rule 30 Prizes, 1 oktober 2019.

Op die dag stelde Wolfram prijzen ter waarde van $30.000 beschikbaar: $10.000 voor elk van de drie vragen over de middelste kolom. Zeven jaar later zijn alle drie de vragen nog steeds open. Lees de kolom als een munt, waarbij zwart staat voor 'kop' en wit voor 'munt':

• Probleem 1: Blijft de middelste kolom altijd niet-periodiek?

Valt de munt ooit in een patroon dat zich eeuwig herhaalt? (Open)

• Probleem 2: Komt elke kleur gemiddeld even vaak voor?

Is de munt op de lange termijn eerlijk? (Open)

• Probleem 3: Kost het berekenen van de n-de cel minstens n stappen inspanning?

Is er een kortere weg naar de n-de worp? (Open)

De munt is niet willekeurig: elke worp wordt bepaald door de regel. Daarom is elk antwoord simpelweg 'ja' of 'nee', en alleen een bewijs kan dit beslechten. Het team van Wolfram heeft een miljard cellen van de kolom berekend. Ze zien er perfect willekeurig uit, maar dat bewijst niets.

3. Orde aan de randen

Waar de orde is, en waar deze eindigt

Kijk opnieuw naar de piramide. De linkerkant is gestreept en de rechterkant is wild, maar geen van beide is precies wat het lijkt. Beide randen bevatten orde met een exacte vorm; beide vormen werden op 9 oktober 2026 ontdekt door nauwkeurig naar de afbeelding te kijken.

De strepen aan de linkerkant eindigen langs een grillige lijn Lees de piramide in lijnen parallel aan de linkerrand, de diagonalen. De eerste paar diagonalen stabiliseren in korte herhalende patronen, en zodra een reeks ervan zich herhaalt, doet deze dat voor altijd, omdat die diagonalen alleen van elkaar afhankelijk zijn. Dus bij elke rij is er een exact aantal diagonalen dat hun eeuwige strepen heeft bereikt.

Deze lijn loopt niet langs de zijkant van de piramide. Hij begint bovenaan bij het centrum en buigt naar buiten met ongeveer een kwart van de snelheid van de rand van de piramide zelf: gemiddeld 0,244 vierkantjes per rij. Dat ligt dicht bij de snelheid (ongeveer 0,246) waarmee een wijziging aan de rechterkant zich naar links verspreidt door een willekeurige rij; of deze twee exact gelijk zijn, is onbekend.

Zelfs de wilde kant heeft een liniaal aan de rand Langs de wilde rechterrand komen de witte driehoeken die de rand raken voor op perfect gelijke afstand; alleen hun grootte verschilt. Dit is exact waar. Bij elke tweede rij begint een witte driehoek één vierkantje binnen de rand, en de breedte hangt alleen af van hoe vaak 2 de rijnummertelling kan delen, net als de markeringen op een liniaal.

Rijen 2, 6, 10, 14 enzovoort (twee keer een oneven getal) krijgen de kleinste driehoek; rijen 4, 12, 20 de volgende maat; rijen 8, 24, 40 de daaropvolgende, enzovoort. De reden is dat elke diagonaal parallel aan de rechterrand zich herhaalt met een periode die een macht van 2 is. Dit is voor alle tijd bewezen.

Geen van beide vormen van orde bereikt de prijzenkolom. Bij rij t bevindt de middelste kolom zich op de t-de diagonaal vanaf beide randen, steeds dieper, waar de perioden te lang zijn geworden om te zien: de 54ste diagonaal vanaf de rechterrand herhaalt zich pas na 4.194.304 rijen. Orde aan de randen zegt dus nog niets over het midden, en dat is waarom de problemen zo moeilijk zijn.

4. Het complete plaatje

Een driehoek, een vierkant en een cirkel

Nu naar de prijzenkolom zelf. Probleem 1 vraagt of deze zich ooit kan herhalen. Stel dat dit gebeurt in de simpelste vorm: wit, zwart, wit, zwart, voor altijd. Houd het centrum vast aan dat ritme, als een muur, en voer Regel 30 uit op de vierkantjes rechts daarvan vanaf een willekeurig begin. De kolom direct naast de muur doet iets opmerkelijks: deze valt in een vaste lus van 56 stappen, een wiel, en blijft daarop staan tot iets van verder rechts hem eraf stoot, waarna hij zich weer vestigt op een nieuwe positie op het wiel.

5. Neem het tegenovergestelde aan

Wat een herhalend centrum zou vereisen

Regel 30 heeft een nuttige eigenschap: als je de middelste kolom en de kolom ernaast kent, is elk vierkantje aan de linkerkant gedwongen, één na de ander. Een herhalend centrum dwingt dus de hele linkerkant af.

Voor elke eindige start (een patroon met slechts een eindig aantal zwarte vierkantjes) zou de gedwongen linkerkant na een bepaalde diepte definitief wit moeten worden. Een tegenvoorbeeld voor Probleem 1 is precies dat: een witte rand die nooit wordt doorbroken.

Maak het centrum alles zeggen, en zie een eindige start opraken Dezelfde eigenschap werkt ook de andere kant op. Kies willekeurig wat het centrum moet zeggen — de priemgetallen, de Fibonacci-getallen, de cijfers van $\pi$ in binair, je eigen naam — en bouw de start één vierkantje per keer naar links op. Elk sequentie kan zo gemaakt worden. De crux is dat de start nooit eindigt; elke stap vereist een extra vierkantje. Als je het inkort tot een eindige start, breekt de sequentie zodra het eerste ontbrekende vierkantje het centrum bereikt. Een eindige start levert ongeveer één stap per vierkantje op, ongeacht wat er gevraagd wordt, tenzij de sequentie een is die Regel 30 zelf maakt. Probleem 1 vraagt of enig herhalend patroon een van die sequenties is.

Eén bit omklappen en de verandering verspreiden Een startwoord kan ook geanimeerd worden. Klap één van de bits om, en de verandering verspreidt zich alleen binnen een kegel die opent vanaf het omgeklapte vierkantje. De rechterrand is een rechte lijn (exact één vierkantje per stap). De linkerrand beweegt alleen wanneer de kleuren het toelaten: ongeveer een kwart vierkantje per stap door het willekeurig ogende binnenste, en een volledig vierkantje zodra het de witte buitenkant bereikt.

Als de kolom naast het centrum ook herhaalt, kristalliseert de linkerkant Wanneer het centrum een vast ritme aanhoudt en de kolom ernaast een herhalend patroon krijgt, bevriest de linkerkant na een korte afstand in een kristal: een muur gebouwd uit één steen, die zich zowel horizontaal als verticaal herhaalt. De steen is nooit leeg, dus de linkerkant kan nooit volledig wit worden. Dit is de stelling van Jen uit 1990.

Wanneer het nooit herhaalt

Een tegenvoorbeeld's tweede kolom kan dus nooit herhalen, en de linkerkant heeft geen kristal om in te stabiliseren. De linkerkant blijkt een stapel Sierpinski-driehoeken te zijn. Begin met één zwart vierkantje en vul elke rij eronder met een simpelere regel: een vierkantje is zwart wanneer exact één van de twee vierkantjes erboven (recht omhoog en rechtsboven) zwart is. Dit is de Gray-code.

Deze eigenschap is niet uniek voor de linkerkant. Regel 30 is in essentie een regel die Sierpinski-driehoeken groeit, waarbij elke "kick" (een specifieke kleurcombinatie) een nieuwe driehoek start. Elke cel in de hele piramide, zowel de gestreepte als de wilde kant, is een oneven overlap van Sierpinski-driehoeken.

Wat een witte rand zou kosten

Een witte rand zou een verstoring met zich meebrengen die een specifiek ritme heeft: oneven, oneven, even, oneven, oneven, even — het patroon van de Fibonacci-getallen (1, 1, 2, 3, 5, 8, 13). Iets in het systeem moet dat ritme voor altijd beantwoorden. De analyses tonen aan dat Regel 30 dit verbiedt, omdat de betaling hiervan altijd oudere en oudere gebeurtenissen vereist.

6. Wat we hebben gevonden

De status van Probleem 1

De drie problemen zijn nog niet opgelost, maar het volgende is vastgesteld (gecontroleerd door een tweede lezer binnen het project):

De geanalyseerde casus Een centrum dat uiteindelijk voor altijd één kleur behoudt, is onmogelijk voor elke eindige start met een zwart vierkantje (bewezen door Condrey in september 2026). Het geval "wit, zwart, wit, zwart" is de volgende onopgeloste casus.

Er bestaat geen tegenvoorbeeld vlakbij het centrum; een witte rand zou meer dan 248 vierkantjes naar links moeten beginnen. Voor een nauwe verwant van Regel 30, Regel 210, is inmiddels vastgesteld dat geen enkele eindige start het centrum laat tikken in wit, zwart, wit, zwart.

Kenmerken van een eventueel tegenvoorbeeld Mocht er een tegenvoorbeeld bestaan, dan moet het aan deze voorwaarden voldoen:

• De kolom naast het centrum herhaalt zich nooit, waardoor het "wiel" voor altijd slipt.
• De slips kunnen niet sneller zeldzamer worden dan een vaste ratio.
• De kolom draagt minder dan een achtste van een bit per lezing, ongeacht wat er rechts staat.
• Het kan niet het beroemde Fibonacci-woord zijn, noch de Thue-Morse sequentie (ten minste voor linker randen tot 15.868 vierkantjes).

De middelste kolom zelf

• De kolom is onvoorspelbaar als een munt voor elke lineaire test: over de eerste 4.194.304 cellen genereert geen enkele lineaire recurrentie korter dan de helft van die lengte de kolom.
• De kleuren blijven in balans, zoals bij een eerlijke munt.
• Infinitievemente veel andere eindige starts produceren exact dezelfde middelste kolom.

Een ring die de klok voor altijd draaiende houdt Een constructie van 84 vierkantjes, herhaald van uiteinde tot uiteinde, komt elke zes stappen bij zichzelf terug. Het centrum tikt voor altijd wit, zwart, wit, zwart. Dit is geen tegenvoorbeeld omdat het oneindig veel zwarte vierkantjes heeft, maar het laat zien dat Regel 30 precies kan doen wat een tegenvoorbeeld zou moeten doen.

7. Een tweeling in de rekenkunde: Collatz

Dezelfde vraag wordt gesteld over getallen in het Collatz-probleem: neem een geheel getal; is het even, deel het door twee; is het oneven, vermenigvuldig met drie, tel er één bij op en deel door twee. Herhaal dit. Lothar Collatz vroeg in 1937 of elk startgetal uiteindelijk bij 1 uitkomt.

In binair is dit dezelfde machine als Regel 30. Vermenigvuldigen met 3/2 (de kern van de oneven stap van Collatz) werkt op een binaire rij bijna hetzelfde als Regel 30. Beide vertrekken vanuit de Gray-code en voegen daar een correctie aan toe.

De overeenkomst reikt tot aan de randen. In beide gevallen is de vraag of een eindige start (een getal met eindig veel cijfers of een rij met eindig veel zwarte vierkantjes) leidt tot een output die zich gedraagt als muntworpen. De methode die de eenvoudige gevallen oplost, stopt bij beide op hetzelfde punt, evenals in het Mahler-probleem van 3/2 uit 1968.

Collatz heeft de rekenkunde (modulaire resten, logaritmen), terwijl Regel 30 lokaliteit heeft (correcties zijn enkelvoudige vierkantjes). Een bewijs aan één kant zou aantonen wat een bewijs aan de andere kant moet vervangen.

8. Hoe dit is gedaan

Dit werk is uitgevoerd tussen 4 en 9 oktober 2026 door Gareth, in samenwerking met AI-collega's: Claude (Anthropic) en GPT (OpenAI). Elk bewijs werd voorgesteld door één partij en gecontroleerd door een andere voordat het als bewezen werd geregistreerd. Voorspellingen werden genoteerd vóór de experimenten.

Bronnen:

• Stephen Wolfram, "Announcing the Rule 30 Prizes" (2019) en "Oh My Gosh, It's Covered in Rule 30s!" (2017).
• A New Kind of Science (2002).
• Condrey, "Finite Configurations Cannot Generate a Constant Trace in Rule 30" (2026).
• Jen, over de periodiciteit van aangrenzende kolommen (1990).
• Meier en Staffelbach, over het herstellen van de linkerkant van Regel 30 vanuit het centrum (1991).