Over cellulaire automaten | Game of Life, Rule 30, Rule 110 & meer

De vier basiselementen

Elke cellulaire automaat is opgebouwd uit dezelfde vier componenten. Het raster is de ruimte waarin de cellen leven. Dit kan een 1D-lijn zijn, een 2D-vlak (zoals een schaakbord), of zelfs een 3D-ruimte. De toestanden zijn wat een cel kan zijn. In het simpelste geval is een cel binair: zwart of wit (1 of 0). De buurt bestaat uit de cellen die direct invloed hebben op een cel. Bij een vierkant raster is dat meestal de Moore-buurt (alle 8 omliggende cellen) of de Von Neumann-buurt (alleen noord, oost, zuid en west). De transitieregels zijn het 'brein' van de automaat: de logica die bepaalt wat de nieuwe toestand van een cel wordt. Bijvoorbeeld: “Als ik zelf leef, maar minder dan 2 levende buren heb, ga ik dood door eenzaamheid.” Elke cel past dezelfde regels op hetzelfde moment toe.

1. Conway's Game of Life

Regels: B3/S23. Een levende cel overleeft met 2 of 3 levende buurcellen. Een dode cel komt tot leven met precies 3. Elke andere cel is dood in de volgende generatie. John Conway ontwierp het in 1970, en de rubriek van Martin Gardner in Scientific American maakte het beroemd. Het levert gliders, oscillatoren en ruimteschepen op. Bill Gosper vond hetzelfde jaar het eerste gliderkanon: een patroon dat elke 30 generaties een nieuwe glider afvuurt, voor altijd. Life kan berekeningen uitvoeren, omdat gliders signalen kunnen dragen en kunnen botsen zoals logische poorten. Bovenal laat het zien hoe complex gedrag uit eenvoudige regels groeit.

Gosper-gliderkanon in de Game of Life dat een diagonale stroom gliders afvuurt — Gosper-gliderkanon na 330 generaties. Gerenderd in PictorX.

2. Rule 30

Type: een eendimensionale elementaire cellulaire automaat. De volgende toestand van elke cel hangt af van de cel zelf en haar twee buurcellen, en elke generatie wordt getekend als een nieuwe rij onder de vorige. Stephen Wolfram introduceerde Rule 30 in 1983. Begin met één zwarte cel en er groeit een chaotische driehoek. Hij lijkt willekeurig ondanks zijn deterministische regel, zo willekeurig dat de middelste kolom is gebruikt als generator van pseudowillekeurige getallen. Hetzelfde soort driehoeken zie je in de pigmentatie van de schelp van de Conus textile.

Driehoek van Rule 30, gegroeid uit één zwarte cel, chaotisch aan de rechterkant en gestreept aan de linkerkant — Rule 30 vanuit één zwarte cel, 224 generaties. Gerenderd in PictorX.

3. Rule 110

Type: een eendimensionale elementaire cellulaire automaat, net als Rule 30, maar met een andere tabel van acht antwoorden. Van Rule 110 is bewezen dat hij Turing-compleet is: Matthew Cook liet zien dat hij met een geschikte eerste rij elke berekening kan nabootsen die een gewone computer kan uitvoeren. Hij heeft bewegende structuren die over een herhalende achtergrond reizen en op elkaar inwerken als ze elkaar tegenkomen. Die botsingen gebruikt het bewijs als logica. Zo laat hij zien hoe heel eenvoudige regels elke denkbare berekening kunnen nabootsen.

Rule 110 gegroeid uit één cel aan de rechterkant, die zich in geneste driehoeken naar links uitbreidt — Rule 110 vanuit één zwarte cel aan de rechterrand. Gerenderd in PictorX.

4. Brian's Brain

Toestanden: uit, aan (vurend) en refractair. Regels: een cel die uit staat gaat aan als precies 2 buurcellen aan staan. Een cel die aan staat wordt refractair. Een refractaire cel gaat uit. Brian Silverman ontwierp het. Omdat een cel na het vuren een generatie moet rusten, beweegt elke puls steeds weg van waar hij al is geweest. Het resultaat is een menigte zichzelf voortbewegende patronen die lijkt op golven in prikkelbare media, zoals zenuwweefsel of hartspier, en er vaak levend en organisch uitziet.

Brian's Brain dat zich uitbreidt vanuit een willekeurige vlek, vurende cellen in geel en vervagende sporen in violet — Brian's Brain 70 generaties na een willekeurige vlek, met vervagende sporen. Gerenderd in PictorX.

5. Wireworld

Toestanden: leeg, elektronkop, elektronstaart en geleider. Regels: een kop wordt een staart, een staart wordt geleider, en een geleider wordt een kop als precies 1 of 2 van zijn buurcellen koppen zijn. Lege cellen blijven leeg. Brian Silverman ontwierp ook Wireworld, in 1987. Geleidercellen zijn draden, en een kop gevolgd door een staart is een elektron dat erlangs loopt. Het kan elektronische schakelingen simuleren: een lus draad met één elektron is een klok, een kleine inkeping is een diode, en een paar cellen vormen een logische poort. Er zijn complete computers in gebouwd, zoals de Wireworld-computer van David Moore en Mark Owen, die priemgetallen berekent.

Wireworld-schakeling met twee kloklussen, twee diodes en een XOR-poort, elektronen in blauw en rood op gele draad — Twee klokken, twee diodes en een XOR-poort in Wireworld. Gerenderd in PictorX.

De 256 regels en vier klassen van Wolfram

Een eendimensionale cel met twee buurcellen ziet een van acht patronen, van 111 tot en met 000. Een regel geeft voor elk daarvan de nieuwe toestand, dus hij bestaat uit acht bits, en er zijn 2⁸ = 256 elementaire regels. Lees de acht antwoorden als een binair getal en je krijgt de naam van de regel: Rule 30 is 00011110, en Rule 110 is 01101110. Stephen Wolfram deelde de regels in naar wat ze doen, van orde tot chaos. 1. Klasse 1 komt tot rust in een uniforme toestand. 2. Klasse 2 komt tot rust in stabiele of herhalende structuren. 3. Klasse 3 blijft chaotisch en ziet er willekeurig uit, zoals Rule 30. 4. Klasse 4 bouwt structuren die bewegen en op elkaar inwerken op de grens tussen orde en chaos, zoals Rule 110.

Rangschikking naar moeilijkheid

Game of Life ★☆☆☆☆ · Rule 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Rule 110 ★★★★★. De eerste twee spreken voor zich terwijl je kijkt. Rule 110 verstopt zijn bewegende structuren in een herhalende achtergrond.

Visueel het mooist

1. Brian's Brain · 2. Conway's Game of Life · 3. Rule 30 · 4. Rule 110 · 5. Wireworld.

Wiskundig het belangrijkst

1. Rule 110, vanwege universaliteit · 2. Game of Life, vanwege universaliteit en emergentie · 3. Rule 30, vanwege chaos en willekeur · 4. Wireworld, vanwege digitale logica · 5. Brian's Brain, vanwege prikkelbare systemen.

In de natuur, natuurkunde en cryptografie

Cellulaire automaten worden gebruikt om complexe systemen in de natuur, natuurkunde en cryptografie te simuleren. Het idee gaat terug op Stanisław Ulam en John von Neumann in de jaren 1940, die een raster van cellen gebruikten om een machine te ontwerpen die zichzelf kon kopiëren. In de echte wereld zie je cellulaire automaten terug in de pigmentatie van bepaalde schelpen, zoals de Conus textile, waarvan de driehoeken op Rule 30 lijken, en in de schubben van de parelhagedis, die volgens een regel die dicht bij een cellulaire automaat ligt tussen groen en zwart wisselen. Natuurkundigen gebruiken ze om gasstromen, zandhopen en bosbranden te modelleren. Door de schijnbare willekeur van Rule 30 werd hij een kandidaat voor generatoren van willekeurige getallen en stroomcijfers.

Ontdek het in PictorX

Open Cellulaire automaten om ze alle vijf te laten lopen. Bekijk het gliderkanon, een vloot ruimteschepen of de R-pentomino, die 1.103 generaties nodig heeft om tot rust te komen. Typ een willekeurige Life-regel zoals B36/S23, of een elementair regelnummer van 0 tot 255. Teken en gum cellen, stuur elektronen door de Wireworld-schakelingen, laat de randen doorlopen en schakel over op de kleurrijke modus. Sla een PNG op of open het canvas in de PictorX-editor.

Veelgestelde vragen

Wat is een cellulaire automaat?

Een raster van cellen waarin elke cel een toestand heeft. Bij elke tik worden alle cellen samen bijgewerkt volgens één vaste regel die alleen naar een cel en haar buurcellen kijkt. Ondanks de eenvoudige regels kunnen de patronen complex en onvoorspelbaar zijn.

Wie heeft cellulaire automaten bedacht?

Stanisław Ulam en John von Neumann, in de jaren 1940 in Los Alamos. De Game of Life van John Conway (1970) maakte het idee populair, en Stephen Wolfram bestudeerde in de jaren 1980 de 256 elementaire regels.

Welke cellulaire automaten zijn Turing-compleet?

Van de vijf hier is van Rule 110 en de Game of Life bewezen dat ze universeel zijn, en in Wireworld past een complete computer. Universeel betekent dat ze met het juiste startpatroon elke berekening kunnen uitvoeren die een gewone computer kan.

Wat zijn de vier klassen van Wolfram?

Klasse 1 sterft uit tot een uniforme toestand, klasse 2 komt tot rust in stabiele of herhalende structuren, klasse 3 blijft chaotisch zoals Rule 30, en klasse 4 bouwt bewegende structuren die op elkaar inwerken, zoals Rule 110.

Waarom ziet Rule 30 er willekeurig uit?

Elke stap ligt vast, maar elke cel mengt haar linkerbuur met de andere twee op een manier die kleine verschillen snel verspreidt. In de middelste kolom is nog geen eenvoudig patroon gevonden, en daarom is die gebruikt om willekeurige getallen te maken.