Om cellulære automater | Game of Life, Regel 30, Regel 110 og mere

De fire grundlæggende dele

Hver cellulær automat er bygget af de samme fire dele. Gitteret er det rum, cellerne lever i. Det kan være en endimensional linje, en todimensional flade som et skakbræt eller endda et tredimensionalt rum. Tilstandene er det, en celle kan være. I det simpleste tilfælde er en celle binær: sort eller hvid, 1 eller 0. Naboskabet er de celler, der direkte påvirker en celle. På et kvadratisk gitter er det som regel Moore-naboskabet, alle otte omkringliggende celler, eller von Neumann-naboskabet, kun nord, øst, syd og vest. Reglerne er automatens hjerne: den logik, der giver hver celle dens nye tilstand. For eksempel: Hvis jeg lever, men har færre end to levende naboer, dør jeg af ensomhed. Alle celler anvender de samme regler på samme tidspunkt.

1. Conways Game of Life

Regler: B3/S23. En levende celle overlever med 2 eller 3 levende naboer. En død celle bliver levende med præcis 3. Alle andre celler er døde i næste generation. John Conway udtænkte det i 1970, og Martin Gardners klumme i Scientific American gjorde det berømt. Det giver glidere, oscillatorer og rumskibe. Bill Gosper fandt den første gliderkanon samme år: et mønster, der affyrer en ny glider hver 30. generation, for altid. Life kan udføre beregninger, fordi glidere kan bære signaler og støde sammen som logiske gates. Frem for alt viser det kompleks adfærd, der vokser ud af simple regler.

Gospers gliderkanon i Game of Life, der affyrer en diagonal strøm af glidere — Gospers gliderkanon efter 330 generationer. Renderet i PictorX.

2. Regel 30

Type: en endimensional elementær cellulær automat. Hver celles næste tilstand afhænger af den selv og dens to naboer, og hver generation tegnes som en ny række under den forrige. Stephen Wolfram introducerede Regel 30 i 1983. Start fra en enkelt sort celle, og der vokser en kaotisk trekant frem. Den virker tilfældig trods sin deterministiske regel, så tilfældig, at dens midterste søjle er blevet brugt som generator af pseudotilfældige tal. Den samme slags trekanter ses i pigmentet på skallen af havsneglen Conus textile.

Trekant fra Regel 30 vokset fra en enkelt sort celle, kaotisk til højre og stribet til venstre — Regel 30 fra én sort celle, 224 generationer. Renderet i PictorX.

3. Regel 110

Type: en endimensional elementær cellulær automat, ligesom Regel 30, men med en anden tabel med otte svar. Det er bevist, at Regel 110 er beregningsmæssigt universel: Matthew Cook viste, at den med en passende første række kan efterligne enhver beregning, som en almindelig computer kan udføre. Den har bevægelige strukturer, der vandrer hen over en gentaget baggrund og påvirker hinanden, når de mødes. Det er de sammenstød, beviset bruger som sin logik. Den viser, hvordan meget simple regler kan efterligne vilkårlige beregninger.

Regel 110 vokset fra én celle til højre, der breder sig mod venstre i indlejrede trekanter — Regel 110 fra én sort celle i højre kant. Renderet i PictorX.

4. Brian's Brain

Tilstande: slukket, tændt (fyrende) og refraktær. Regler: en slukket celle tændes, hvis præcis 2 naboer er tændt. En tændt celle bliver refraktær. En refraktær celle slukkes. Brian Silverman udtænkte den. Fordi en celle skal hvile i en generation, efter at den har fyret, bevæger hver puls sig hele tiden væk fra, hvor den har været. Resultatet er en flok selvbevægende mønstre, der minder om bølger i exciterbare medier som nervevæv eller hjertemuskel og ofte ser levende og organiske ud.

Brian's Brain, der breder sig fra en tilfældig plet, med fyrende celler i gult og falmende spor i violet — Brian's Brain 70 generationer efter en tilfældig plet, med falmende spor. Renderet i PictorX.

5. Wireworld

Tilstande: tom, elektronhoved, elektronhale og leder. Regler: et hoved bliver til en hale, en hale bliver til leder, og en leder bliver til et hoved, når præcis 1 eller 2 af dens naboer er hoveder. Tomme celler forbliver tomme. Brian Silverman udtænkte også Wireworld, i 1987. Ledercellerne er ledninger, og et hoved efterfulgt af en hale er en elektron, der løber langs dem. Den kan simulere elektroniske kredsløb: en ledningsløkke med én elektron er et ur, et lille hak er en diode, og nogle få celler udgør en logisk gate. Der er bygget komplette computere i den, fx Wireworld-computeren af David Moore og Mark Owen, der beregner primtal.

Wireworld-kredsløb med to urløkker, to dioder og en XOR-gate, elektroner i blåt og rødt på gul ledning — To ure, to dioder og en XOR-gate i Wireworld. Renderet i PictorX.

Wolframs 256 regler og fire klasser

En endimensional celle med to naboer ser ét af otte mønstre, fra 111 ned til 000. En regel angiver den nye tilstand for hvert af dem, så den er på otte bit, og der findes 2⁸ = 256 elementære regler. Læs de otte svar som et binært tal, og du får reglens navn: Regel 30 er 00011110, og Regel 110 er 01101110. Stephen Wolfram ordnede reglerne efter, hvad de gør, fra orden til kaos. 1. Klasse 1 falder til ro i en ensartet tilstand. 2. Klasse 2 falder til ro i stabile eller gentagne strukturer. 3. Klasse 3 forbliver kaotisk og ser tilfældig ud, som Regel 30. 4. Klasse 4 bygger strukturer, der bevæger sig og påvirker hinanden på grænsen mellem orden og kaos, som Regel 110.

Rangeret efter sværhedsgrad

Game of Life ★☆☆☆☆ · Regel 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regel 110 ★★★★★. De to første forklarer sig selv, mens du ser på. Regel 110 gemmer sine bevægelige strukturer i en gentaget baggrund.

Smukkest visuelt

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

Vigtigst matematisk

1. Regel 110, for universalitet · 2. Game of Life, for universalitet og emergens · 3. Regel 30, for kaos og tilfældighed · 4. Wireworld, for digital logik · 5. Brian's Brain, for exciterbare systemer.

I naturen, fysikken og kryptografien

Cellulære automater bruges til at simulere komplekse systemer i naturen, fysikken og kryptografien. Idéen går tilbage til Stanisław Ulam og John von Neumann i 1940’erne, der brugte et gitter af celler til at konstruere en maskine, som kunne kopiere sig selv. I den virkelige verden kan man se cellulære automater i pigmentet på visse skaller, som Conus textile, hvis trekanter ligner Regel 30, og i skællene på perleøglen, der skifter mellem grønt og sort efter en regel tæt på en cellulær automat. Fysikere bruger dem til at modellere gasstrømning, sandbunker og skovbrande. Regel 30's tilsyneladende tilfældighed gjorde den til en kandidat til generatorer af tilfældige tal og strømchifre.

Udforsk dem i PictorX

Åbn Cellulære automater for at køre alle fem. Se gliderkanonen, en flåde af rumskibe eller R-pentominoen, der skal bruge 1.103 generationer på at falde til ro. Skriv en hvilken som helst Life-regel som B36/S23 eller et hvilket som helst elementært regelnummer fra 0 til 255. Tegn og visk celler ud, send elektroner gennem Wireworld-kredsløbene, forbind kanterne, og skift til farverig tilstand. Gem en PNG, eller åbn lærredet i PictorX-editoren.

Ofte stillede spørgsmål

Hvad er en cellulær automat?

Et gitter af celler, hvor hver celle har en tilstand. Ved hvert tik opdateres alle celler samtidig efter én fast regel, der kun ser på en celle og dens naboer. Trods de simple regler kan mønstrene være komplekse og uforudsigelige.

Hvem opfandt cellulære automater?

Stanisław Ulam og John von Neumann i 1940’erne i Los Alamos. John Conways Game of Life (1970) gjorde idéen populær, og Stephen Wolfram undersøgte de 256 elementære regler i 1980’erne.

Hvilke cellulære automater er Turing-komplette?

Blandt de fem her er det bevist, at Regel 110 og Game of Life er universelle, og Wireworld kan rumme en komplet computer. Universel betyder, at de med det rette startmønster kan udføre enhver beregning, som en almindelig computer kan.

Hvad er Wolframs fire klasser?

Klasse 1 dør ud til en ensartet tilstand, klasse 2 falder til ro i stabile eller gentagne strukturer, klasse 3 forbliver kaotisk som Regel 30, og klasse 4 bygger bevægelige strukturer, der påvirker hinanden, som Regel 110.

Hvorfor ser Regel 30 tilfældig ud?

Hvert trin er fastlagt, men hver celle blander sin venstre nabo med de to andre på en måde, der hurtigt spreder små forskelle. Der er ikke fundet noget simpelt mønster i dens midterste søjle, og derfor er den blevet brugt til at lave tilfældige tal.