Om cellulära automater | Game of Life, Regel 30, Regel 110 och mer

De fyra grunddelarna

Varje cellulär automat är uppbyggd av samma fyra delar. Rutnätet är rummet som cellerna lever i. Det kan vara en endimensionell linje, ett tvådimensionellt plan som ett schackbräde eller till och med ett tredimensionellt rum. Tillstånden är det som en cell kan vara. I det enklaste fallet är en cell binär: svart eller vit, 1 eller 0. Grannskapet är de celler som direkt påverkar en cell. På ett kvadratiskt rutnät är det oftast Moore-grannskapet, alla åtta omgivande celler, eller von Neumann-grannskapet, bara norr, öster, söder och väster. Reglerna är automatens hjärna: logiken som ger varje cell dess nya tillstånd. Till exempel: om jag lever men har färre än två levande grannar dör jag av ensamhet. Varje cell tillämpar samma regler i samma ögonblick.

1. Conways Game of Life

Regler: B3/S23. En levande cell överlever med 2 eller 3 levande grannar. En död cell vaknar till liv med exakt 3. Alla andra celler är döda i nästa generation. John Conway konstruerade det 1970, och Martin Gardners kolumn i Scientific American gjorde det berömt. Det ger glidare, oscillatorer och rymdskepp. Bill Gosper hittade den första glidarkanonen samma år: ett mönster som skjuter ut en ny glidare var 30:e generation, för alltid. Life kan utföra beräkningar, eftersom glidare kan bära signaler och kollidera som logiska grindar. Framför allt visar det komplext beteende som växer fram ur enkla regler.

Gospers glidarkanon i Game of Life som skjuter ut en diagonal ström av glidare — Gospers glidarkanon efter 330 generationer. Renderad i PictorX.

2. Regel 30

Typ: en endimensionell elementär cellulär automat. Varje cells nästa tillstånd beror på cellen själv och dess två grannar, och varje generation ritas som en ny rad under den förra. Stephen Wolfram introducerade Regel 30 år 1983. Börja från en enda svart cell så växer en kaotisk triangel fram. Den ser slumpmässig ut trots sin deterministiska regel, så slumpmässig att dess mittkolumn har använts som pseudoslumptalsgenerator. Samma slags trianglar syns i pigmentet på snäckskalet hos Conus textile.

Triangel från Regel 30 som vuxit från en enda svart cell, kaotisk till höger och randig till vänster — Regel 30 från en svart cell, 224 generationer. Renderad i PictorX.

3. Regel 110

Typ: en endimensionell elementär cellulär automat, precis som Regel 30, men med en annan tabell med åtta svar. Regel 110 är bevisat beräkningsuniversell: Matthew Cook visade att den med en lämplig första rad kan efterlikna vilken beräkning som helst som en allmän dator kan utföra. Den har rörliga strukturer som vandrar över en upprepad bakgrund och växelverkar när de möts. Det är de kollisionerna som beviset använder som logik. Den visar hur mycket enkla regler kan efterlikna godtyckliga beräkningar.

Regel 110 som vuxit från en cell till höger och sprider sig åt vänster i inkapslade trianglar — Regel 110 från en svart cell vid högerkanten. Renderad i PictorX.

4. Brian's Brain

Tillstånd: av, på (fyrande) och refraktär. Regler: en avstängd cell slås på om exakt 2 grannar är på. En påslagen cell blir refraktär. En refraktär cell stängs av. Brian Silverman konstruerade den. Eftersom en cell måste vila en generation efter att den har fyrat, rör sig varje puls hela tiden bort från där den har varit. Resultatet är ett myller av självgående mönster som liknar vågor i exciterbara medier, som nervvävnad eller hjärtmuskel, och som ofta ser levande och organiskt ut.

Brian's Brain som sprider sig från en slumpmässig fläck, fyrande celler i gult och bleknande spår i violett — Brian's Brain 70 generationer efter en slumpmässig fläck, med bleknande spår. Renderad i PictorX.

5. Wireworld

Tillstånd: tom, elektronhuvud, elektronsvans och ledare. Regler: ett huvud blir en svans, en svans blir ledare, och en ledare blir ett huvud när exakt 1 eller 2 av dess grannar är huvuden. Tomma celler förblir tomma. Brian Silverman konstruerade även Wireworld, år 1987. Ledarceller är ledningar, och ett huvud följt av en svans är en elektron som löper längs dem. Den kan simulera elektroniska kretsar: en slinga av ledning med en elektron är en klocka, ett litet hack är en diod och några få celler bildar en logisk grind. Kompletta datorer har byggts i den, till exempel Wireworld-datorn av David Moore och Mark Owen, som räknar ut primtal.

Wireworld-krets med två klockslingor, två dioder och en XOR-grind, elektroner i blått och rött på gul ledning — Två klockor, två dioder och en XOR-grind i Wireworld. Renderad i PictorX.

Wolframs 256 regler och fyra klasser

En endimensionell cell med två grannar ser ett av åtta mönster, från 111 ner till 000. En regel anger det nya tillståndet för vart och ett av dem, så den består av åtta bitar, och det finns 2⁸ = 256 elementära regler. Läs de åtta svaren som ett binärt tal så får du regelns namn: Regel 30 är 00011110 och Regel 110 är 01101110. Stephen Wolfram sorterade reglerna efter vad de gör, från ordning till kaos. 1. Klass 1 hamnar i ett enhetligt tillstånd. 2. Klass 2 hamnar i stabila eller upprepade strukturer. 3. Klass 3 förblir kaotisk och ser slumpmässig ut, som Regel 30. 4. Klass 4 bygger strukturer som rör sig och växelverkar på gränsen mellan ordning och kaos, som Regel 110.

Rangordning efter svårighet

Game of Life ★☆☆☆☆ · Regel 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regel 110 ★★★★★. De två första förklarar sig själva medan du tittar. Regel 110 gömmer sina rörliga strukturer i en upprepad bakgrund.

Vackrast visuellt

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

Viktigast matematiskt

1. Regel 110, för universaliteten · 2. Game of Life, för universalitet och emergens · 3. Regel 30, för kaos och slumpmässighet · 4. Wireworld, för digital logik · 5. Brian's Brain, för exciterbara system.

I naturen, fysiken och kryptografin

Cellulära automater används för att simulera komplexa system i naturen, fysiken och kryptografin. Idén går tillbaka till Stanisław Ulam och John von Neumann på 1940-talet, som använde ett rutnät av celler för att konstruera en maskin som kunde kopiera sig själv. I verkligheten kan man se cellulära automater i pigmentet hos vissa snäckor, till exempel Conus textile, vars trianglar liknar Regel 30, och i fjällen hos pärlödlan, som växlar mellan grönt och svart enligt en regel som ligger nära en cellulär automat. Fysiker använder dem för att modellera gasflöden, sandhögar och skogsbränder. Den skenbara slumpmässigheten i Regel 30 gjorde den till en kandidat för slumptalsgeneratorer och strömchiffer.

Utforska dem i PictorX

Öppna Cellulära automater för att köra alla fem. Titta på glidarkanonen, en flotta rymdskepp eller R-pentominon, som behöver 1 103 generationer för att stabiliseras. Skriv valfri Life-regel som B36/S23, eller valfritt elementärt regelnummer från 0 till 255. Rita och sudda celler, skicka elektroner genom Wireworld-kretsarna, koppla ihop kanterna och byt till färgglatt läge. Spara en PNG eller öppna arbetsytan i PictorX-redigeraren.

Ofta ställda frågor

Vad är en cellulär automat?

Ett rutnät av celler där varje cell har ett tillstånd. Vid varje tick uppdateras alla celler samtidigt enligt en fast regel som bara tittar på en cell och dess grannar. Trots de enkla reglerna kan mönstren bli komplexa och oförutsägbara.

Vem uppfann cellulära automater?

Stanisław Ulam och John von Neumann, på 1940-talet i Los Alamos. John Conways Game of Life (1970) gjorde idén populär, och Stephen Wolfram studerade de 256 elementära reglerna på 1980-talet.

Vilka cellulära automater är Turingkompletta?

Bland de fem här är Regel 110 och Game of Life bevisat universella, och Wireworld kan rymma en komplett dator. Universell betyder att de, med rätt startmönster, kan utföra vilken beräkning som helst som en allmän dator kan.

Vilka är Wolframs fyra klasser?

Klass 1 dör ut till ett enhetligt tillstånd, klass 2 hamnar i stabila eller upprepade strukturer, klass 3 förblir kaotisk som Regel 30, och klass 4 bygger rörliga strukturer som växelverkar, som Regel 110.

Varför ser Regel 30 slumpmässig ut?

Varje steg är bestämt, men varje cell blandar sin vänstra granne med de två andra på ett sätt som snabbt sprider små skillnader. Inget enkelt mönster har hittats i mittkolumnen, och därför har den använts för att skapa slumptal.