Skolekoding.no > p5.js > The Nature of Code > Hva er Cellular Automata
Wolfram Elementarty Cellular Automata
En kort introduksjon fritt oversatt fra The Nature of Code kap 7.1 av Daniel Shiffman. Figurer fra boka.
The Nature of Code
Eksempler fra boka oversatt fra Processing til p5.js
«To play life you must have a fairly large checkerboard and a plentiful supply of flat counters of two colors. It is possible to work with pencil and graph paper but it is much easier, particularly for beginners, to use counters and a board.”
— Martin Gardner, Scientific American (October 1970)
- Vi har et rutenett på papir.
- I hver rute ligger det et kronestykke som enten er «kron » eller «mynt».
- Hvert kronestykke er omgitt av naboer.
- Naboene avgjør om kronstykket skal vendes om eller om det skal ligge som det ligger.
Hva er Cellular Automation?
Cellular automation er et system av «celle»-objekter med følgende karakteristika:
- Hver celle lever i en rute i et rutenett
- Hver celle har en tilstand: 1 eller 0, på eller av, levende eller død (i sin enkleste form)
- Hver celle har et sett naboer som avgjør cellens status
I figur 7.1 har cellen i midten åtte naboer. Fire celler er «på» og fire celler «av». I dette systemet betyr dette at cellen i midten er «av».
Reglene bestemmer vi selv. For eksempel kan vi bestemme at hjørnenaboer vektes lavere enn sidenaboer.
Ulam, Neumann, Wolfram
Stanislaw Ulam og John Neumann, forskere ved Los Alamos Laboratory i New Mexico på 1940-tallet, er de som vanligvis får æren for ideen om cellular automata.
I 2002 kom studien A New Kind of Science av Stephen Wolfram. Dette er muligens er det viktigste bidraget til studiet av celullar automata: . Her viser han på 1280 sider at CA er mer enn en morsomme triks. CA har relevans både til biologi, kjemi, fysikk og annen naturvitenskap.
Elementary Cellular Automata
Hva er den enkleste form for CA? Vi bygger Wolframs elemantary CA fra bunnen av.
Rutenett: Enkleste form for rutenett er en rad med ruter
Tilstand: Enkleste sett av tilstander er to tilstander: 0 eller 1
Naboskap: Enkleste form for naboskap er cellen selv og de to cellene på hver side. Cellene i hver ende har bare én nabo. Ofte sier vi da at den manglende naboen er cellen i motsatt ende av rekka. For rekka nedenfor betyr det at celle nr 1 har celle nr 10 (1) som sin venstre nabo og celle nr 2 (0) som sin høyre nabo. Altså: 1-1-0
Figur 7.4 viser CA generasjon 0. Hva skjer med cellene i neste generasjon. Beholder de sin verdi eller endres verdien?
Hvilken påvirkning har naboene på cellens verdi i neste generasjon?
Hvilke mulige kombinasjoner av 0 og 1 kan de tre cellene i generasjon 0 ha? Det er to muligheter i celle nr 1: 0 og 1. For hver av disse to er det to muligheter i celle nr 2 og deretter to muligheter i celle nr 3. Dette gir totalt åtte muligheter: 2·2·2 = 2³= 8.
Dette er de mulige kombinasjonene av naboskap. Nå er det opp til oss å bestemme hva de ulike naboskapene skal føre til i neste generasjon. For eksempel kan vi bestemme denne regelen:
Som standard starter Wolfram-modellene med med en generasjon 0 der alle cellene har verdi 0, bortsett fra midtcellen som har verdi 1. Lengden av rutenettet har ingen betydning. Her vises et rutenett med ni celler. Vanligvis bruker vi mye lengre rutenett.
La oss se hvordan neste generasjon se ut hvis vi bruker regelsettet fra figur 7.9:
Celle nr 5 endrer verdi fra 1 til 0 fordi begge naboene har verdien 0. Prøv å gjøre det samme med de andre cellene i generasjon 0. Hvordan blir resten av generasjon 1 seende ut? Husk at vi ignorere endecellene. De får alltid verdien 0 = hvit.
Hvis vi fortsetter med dette systemet flere generasjoner framover vil vi få dette bildet.
Dette bildet viser Sierpińskis triangel i lav oppløsning. Waclaw Sierpiński var en polsk matematiker som i 1915 beskrev dette mønsteret. Mønsteret er et fraktalmønster (kap 8) som har vært kjent fra italiensk kunst siden 1300-tallet (britannica.com).
Her er samme mønster med høyere oppløsning:
Dette resultatet var ikke tilfeldig. Regelsettet ble valgt på grunn av mønsteret det genererer. Husk at nabolaget hadde åtte mulige kombinasjoner av 0 og 1. For hver kombinasjon bestemte vi en tilstand for neste generasjon. Dette gir et regelsett på åtte nuller og enere .
Dette er samme regelsettet som tidligere, men vi har snudd det rundt slik at et nabolag av tre enere utgjør den første regelen.
Åtte nuller og enere gir et åttesifret tall i to-tallssystemet. Ett siffer i to-tallsystemet kalles en «bit». Her har vi altså et åtte-bits tall. Hvor mange kombinasjoner av åtte nuller og enere finnes det? 2·2·2·2·2·2·2·2 = 2⁸ = 256. Dette er nettopp slik vi definerer RGB-farger: 256 muligheter for hver av fargene rød, grønn og blå. Åtte bit er det som vanligvis utgjør en byte.
Innenfor Wolfram elementary CA finnes det altså 256 mulige regelsett. Regelen over kalles «Regel 90». Hvis vi omgjør det binære tallet 01011010 til et tall i ti-tallssystemet får vi 90: 0·2⁷ + 1·2⁶ + 0·2⁵ + 1·2⁴ + 1·2³ + 0·2² + 1·2¹ + 0·2⁰ = 90. (Forøvrig kan 90 skrives slik 9·10¹ + 0·10⁰)
La oss forsøke et annet regelsett:
Regel 222 er slik: 1 1 0 1 1 1 1 0. Som vi ser er det ingen garanti for at et regelsett gir et visuelt interessant resultat. Av de 256 mulighetene er det bare noen få som gjør det. Likevel er det ganske utrolig at en en-dimensjonal CA (et rutenett med èn rad) med et regelsett med bare to mulige tilstander (1 og 0) kan produsere mønstre som vi kan observere i naturen hver dag.
Denne teksen er fritt oversatt fra The Nature of Code av Daniel Shiffman, kapittel 7.1. Figurer fra boka: The Nature of Code (natureofcode.com)
Eksempler fra de fleste kapitlene i p5.js
Oversikt over alle 256 Wolfram elemetary cellular automata (writings.stphenwolfram.com)
skolekoding.no
Stein Olav Kivle