Endimensionale Cellular Automata

Hele ideen bag cellular automata er ganske simpel:

Man har en linje, der består af en række ens firkantede celler som kan antage en række talværdier; og man har algoritme til at udvikle denne linje efter. Det er alt! Men alligevel fører den rette algoritme til meget komplekse strukturer, til tider mos-lignende, til tider stablede trekanter, til tider helt ubeskrivelige.

I den enkleste slags linjer kan cellerne kun antage værdierne 0 og 1 - vi vil (kun) se på disse. Denne type betegnes kort med k = 2, hvor k er antallet af tilstande for en enkelte celle. Ofte omtales celler med værdien 0 som døde og celler med værdien 1 som levende.

Her er 2 generationer af en 11-cellers linje:

Her og i det følgende er generation n+1 afbildet under generation n.

Linjen er udviklet efter algoritmen : Hvis summen af cellen og dens to naboer er 1 eller 2 skal den nye celle har værdien 1 ellers 0. Koden for denne algoritme er :

Man taler ofte om koden som den binære fremstilling og om reglen som det tilsvarende titalssystems-tal. (Dette gælder naturligvis kun for k = 2. For k = n bruger man n-talsystemet til oversættelsen.) Koder baseret på summation af celleværdier kaldes totalistiske koder.

Men hvad gør man når man kommer til kanten? Der er to slags "kanter": Ved den ene type kant lader man som om celle-linjen fortsætter til begge sider og altid er fyldt med lutter nuller. Den anden slags kant betragter celle-linjen som en cirkel. Fx er værdien af celle nr.1 til tiden t+1 bestemt af celle nr. n, 1, 2 til tid t. Den sidste type kant er den mest anvendte.

Jeg må med det samme gøre opmærksom på, at alle illustrationer her er udsnit af større billeder - derfor er enhver sammenhæng mellem kanterne tilfældig.

I stedet for kun at udregne summen af cellen og to naboer kunne man også medtage naboernes naboer. Nu bliver summen en værdi imellem 0 og 5, og koden bliver således et 6 cifret tal. Kort specificerer man kodens "radius" med r.

Eksempel: Her er r = 2. Her og i alle følgende illustrationer er celler med værdien 1 vist sorte.

kode 010100 (dvs regel 20)

Generelle koder (I dette afsnit er r = 1).

I stedet for at summerer celleværdierne i et nabo-område, kan man behandle alle de mulige kombinationer at 0 og 1 hver for sig, således at værdien af 100 og 001 ikke nødvendigvis er den samme. Denne slags koder kaldes ofte generelle koder, og de indeholder de totalistiske koder som et særtilfælde. Algoritmen omskrives til kodeform, ved at man tillægger alle de mulige kombinationers binærværdi den nye celleværdi. Hvis jeg fx ønsker, at 110 giver 1 tillægger jeg binærværdien af 110 (dvs. 6) celleværdien 1. Når ydereligere 010 og 000 giver 0 bliver min kode:

Den største ulempe ved generelle koder er ofte, at koden er temmelig lang at opskrive.

Arbejder man fx med r = 3 bliver ens kode et 32-cifret tal.

Vi vil kun kikke lidt på fire koder, der adskiller sig væsentligt fra totalistiske koder: Koden 11001100 bevirker at hver generation bliver en nøjagtig kopi af startlinjen. På samme måde gør 00110011, at alle generationer med lige nummer netop er en kopi af startlinjen. Analogt bevirker koderne 11110000 og 10101010 at generation n+1 er en nøjagtig kopi af generation n flyttet henholdsvis en celle mod højre og en celle mod venstre. (En lille opgave til læseren : Hvorfor fungerer de fire koder på denne måde?)

kode 11110000

Klassedeling af de totalistiske koder

Stephen Wolfram, som formentlig er den, der ved mest om endimensionale cellular automata, har inddelt totalistiske atomataer i fire klasser.

Klasse 1: Ligegyldigt hvilken startlinje går mønstret efter få generationer over i et stadie, hvor alle celle indeholder samme værdi.

Eksempel: r = 2 kode: 110000

Klasse 2: Efter få generationer bliver mønsteret opdelt i "strimler" hvor cellerne har samme værdi. En ændring i en enkelt celleværdi i startlinjen har kun en lille indflydelses-radius i det endelige mønster, oftest af størrelsesorden r. I eksemplet er r = 2 og kode er: 101000

Klasse 3: Mønsteret udvikler aldrig nogen grænser, men bliver ved med at udfylde

den plads det har tilrådighed. Ved tilfældige startlinjer er sandsynligheden efter et stykke tid mht. den enkelte celles værdi stort set som i startlinjen.

En ændring af en enkelt celles startværdi har tit indflydelse på 2rt+1 celler (hvor t er generationens nummer. Det er umuligt for nogen celle af have indflydelse på mere end 2rt+1 celler - ligegyldigt hvilken klasse koden tilhører.)

De tre eksempler har koderne henholdsvis: 011100, 110010, 101010 og alle med r = 2.

Klasse 4: Linjen udvikler efter nogen tid komplekse små-mønstre. Nogle lever i mange generationer, andre er periodiske. En ændring i startlinjen har typisk uforudsigelige følger.

Et eksempel på en kode fra klasse 4 er 010100, som er vist på side 2.

Desuden er kode 110100 r = 2 (som er nært beslægtet med 010100) også klasse 4.

I klasse 3 og 4 findes linjer som kun kan optræde som startlinjer. Disse linjer kaldes tit "Garden of Eden".

Illegale koder

Illegale koder er alle koder med ulige regelnummer. Formentlig tilhører alle illegale koder klasse 3. Grunden til navnet ligger i, at det er "snyd" at en række døde celler giver anledning til levende celler. Med det skal selvfølgelig ikke forhindre os i at tage et hurtigt kik på en interessant illegal kode.

Imidlertid har kode 000101 (r=2) nogle karaktertræk som en klasse 4 kode. De to næste billeder ( se næste side) er begge af denne kode og med tilfældig startlinje. På det første billede er alle levende celler markeret med sort, på det andet er kun de levende celler der fremkom ved sum 2 markeret. Bemærk forøvrigt strukturen, der bevæger sig mod højre i midten af det andet billede.

Glidere:

Strukturer, der gentager sig selv, men flyttet en (eller flere) celler til en side kaldes glidere. Det er en særlig fin egenskab ved en kode hvis den giver mulighed for gliders.

Kode 010100 (se illustrationen på side 2) indeholder i hvertfald to glidere: Gliderne har begyndelses-linjerne 1101000011 og 1001111011.

Nu kan man spørger sig selv: Glidere kan opstå spontant ud fra udviklingen af en tilfældig startlinje, mon der findes en stabil struktur som glideren kan opstå fra? Et andet interessant spørgsmål er, om der i nogen klasse 4 kode findes strukturer, som beviselig bliver ved med at vokse? I 1985 gav James K. Parker fra Princeton University et samlet bekræftende svar på de to spørgsmål.

Glider gun

Han udgav en rapport om en helt ekstraordinær struktur han havde opdaget: En glider gun. Denne struktur spyttede en glider ud til den ene side efter 119 generationer og endnu en glider til den anden side 119 generationer senere. Alt i alt en periode på 238.

Glidergunen findes ved k = 2, r = 3, kode 01011000 (regel 88). Begyndelseslinje : 1111111111011.

Såvidt jeg ved, er denne glider gun den eneste endimensionale (med k = 2) der er kendt i dag, men Stephen Wolfram mener, at det er sandsynligt, at der også eksisterer en eller måske flere gliderguns i regel 20 (k = 2, r = 2).

Billedet viser regel 88 med en tilfældig startlinje. Bemærk der anden type glider i midten af billedet.

Game of Life

Der findes (ikke overraskende) også ikke-endimensionale cellular automataer. Faktisk blev cellular automata oprindeligt opfundet i 1963 som todimensionale biologiske modeller. En af de berømteste todimensionale er Game of Life. Netop denne kode er blevet genstand for megen opmærksomhed siden begyndelsen af 1970'erne, hvor det vidste sig, at det er muligt at lave AND, OR og NOT-gates i Game of Life.

Til dem, der har fået lyst til at gå på jagt i automata-junglen, er her et par koder til at begynde med.

Hvis du finder en spændende kode eller noget andet interessant, så send en notits til Famøs.

Totalistiske koder:

Litteratur:

Dewdney : Scientific American, 252 (Maj 1985), s. 18-30.

Duff, Michael J.B. : Modern Cellular Automata, Theory and Applications, Plenum Press, 1984

Physica D, (Nonlinear Phenomena) vol. 10D, 1984, s. 1-248, North-Holland Physics Publishing

Wolfram, Stephen : Cellular automata as models of complexi ty, Nature vol. 311 (1984), s. 419-424.

Wolfram, Stephen : Theory and Applications of Cellular

Automata, World Scientific Publishing, 1986.