Game of Life
Game of life är en cellulär automat som konstruerades av matematikern John Conway, 1970.
Det är ett spel för 0 spelare som spelas på ett oändligt rutat papper. Varje ruta (cell) kan vara död (vit) eller levande (svart). Varje gång klockan tickar föds eller dör några celler, enligt särskilda regler.
Cellulära automater är diskreta matematiska modeller som till exempel kan användas för att studera fenomen i kaotiska system, eller bara för att de är roliga att titta på.
Regler
- En levande cell med 0-1 levande grannar dör av ensamhet.
- En levande cell med 4-8 levande grannar dör av trängsel.
- En död cell med 3 levande grannar återföds.
- Alla övriga celler är oförändrade.
Mönster
Genom att studera Game of Life har man upptäckt återkommande mönster i alla storlekar. De större är flera tusen celler breda och höga.
Stabila
Följande är ett "block". Varje död/vit cell har högst 2 levande/svarta grannar, så de förblir döda. Varje levande cell har 3 levande grannar, så de förblir levande. Inget förändras.
Följande är en "bikupa". Som ovan finns det ingen levande cell med 0-1 levande grannar (ingen dör), och ingen död cell med 3 levande grannar (ingen återföds). Inget förändras.
Oscillerande
Här appliceras exakt samma regler som ovan, men på annorlunda indata. För dessa indata får vi ett repeterande mönster i 2 (blinker) respektive 3 (pulsar) steg.
Rymdskepp
Här har vi en seglare och ett lätt rymdskepp. Dessa mönster repeterar sig själva på ett sätt som gör att de ständigt flyttar sig, snett respektive rakt.
Fördjupning (frivillig)
Game of Life är en två-dimensionell cellulär automat. Det finns även automater med andra antal dimensioner.
En-dimensionell cellulär automat
Principen är att vi har en rad med celler, till skillnad från det tvådimensionella "spelbrädet" vi hade i Game of Life.
För varje "tick" uppdateras varje cell beroende på det gamla tillståndet för cellen själv och dess två grannar. Det finns 8 sådana tillstånd:
- levande, LEVANDE, levande (till vänster, "jag själv", till höger)
- levande, LEVANDE, död
- ...
- död, DÖD, död
Detta är alltså de indata som ska avgöra om en viss cell fortsätter leva, dör, fortsätter vara död, eller återföds. Men vilken regel ska vi applicera? I Game of Life var ju regeln "om jag har 0-1 eller 4-8 levande grannar dör jag, om jag har 3 levande grannar återföds jag, annars ändras inget". Vilken regel gäller för de 1-dimensionella automaterna?
Det har vi faktiskt inte bestämt. Game of Life är namnet på en av väldigt många tänkbara tvådimensionella automater. Här har vi också många tänkbara endimensionella automater, beroende på exakt hur vi väljer att konstruera vår uppdateringsregler.
Så hur många tänkbara uppdateringsregler finns det? Ja, om vi håller oss till att en cell bara påverkas av de omedelbara grannarna, finns det alltså 8 olika input till regeln. För vart och ett av dessa inputs kan regeln välja att cellen i nästa steg ska vara död eller levande. Det finns alltså 8 oberoende val att göra, och varje val har 2 alternativ. Det blir 2^8 = 256 tänkbara regler som man kan välja att använda. Här är det viktigt att inse att man i varje automat bara väljer en av dessa 256, och sedan applicerar den konsistent steg för steg.
Reglerna är har en standardiserad numrering. Regel 1 säger till exempel att alla mönster leder till att cellen dör. Nedan ser vi exempel på flera intressanta regler.
Övre raden i varje regel visar de 8 olika inputs man kan ha, från levande-levande-levande till död-död-död. Undre raden visar vad regeln bestämmer att mittencellen ska bli efter att regeln har applicerats. Regel 30 säger t.ex. att levande-levande-levande leder till att mittencellen dör, medan levande-död-död leder till att mittencellen återföds.
Vi kan också visa vad olika regler ger upphov till, steg för steg, om man applicerar dem i ett starttillstånd med en enda levande cell. Istället för att animera detta, som vi gjorde ovan, visar vi nu 20 steg ("generationer") där varje steg är en separat rad. Det blir alltså en tvådimensionell bild där y-dimensionen egentligen motsvarar tid. Själva automaten är fortfarande 1-dimensionell.
Vissa regler skapar fraktaler (till exempel Sierpinski-trianglar) och vissa mönster som skapas har hittats i naturen, bland annat på snäckskal.
Videor
Bildkällor
http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
Sidansvarig: Peter Dalenius
Senast uppdaterad: 2021-12-03