Cellulaire automaten

De regels van een cellulaire automaat beschrijven hoe je uit de huidige toestand (vorm) de volgende toestand bepaalt. De uitvoering van deze regels resulteert in een proces als opeenvolging van deze toestanden.
Conway’s Game of Life is een voorbeeld van een 2-dimensionale cellulaire automaat. Je hebt dan een vlak met cellen (witte en zwarte hokjes).
Een 1-dimensionale cellulaire automaat bestaat uit een reeks aaneengesloten cellen. Een cel is “levend” (zwart, 1) of “dood” (wit, 0). De toestand van een automaat op een bepaald moment geeft aan welke cellen levend zijn, en welke dood. Dit kun je weergeven als een (horizontale) rij zwart/witte cellen (hokjes).

Gegeven een toestand van een automaat, kun je voor elke cel de volgende toestand bepalen uit de toestand van die cel en die van zijn directe buren. Je kunt de opeenvolging van toestanden weergeven door deze onder elkaar te tekenen, in een plat vlak.

Een voorbeeld van een automaat: (rule 110 = 0110 1110)
 

Regels voor de automaat (rule 110)

Met behulp van deze regels kun je vanuit een begintoestand de volgende toestanden uitrekenen. We tekenen de opeenvolgende toestanden (of generaties) onder elkaar.
In de figuur hieronder is dan gedaan voor een begintoestand met één zwarte cel, met de bovenstaande regels.

1-dimensionale cellualire automaat: de eerste regel is de
begintoestand, de volgende regels zijn de opeenvolgende
toestanden.


In plaats van met de “vormen” zwart en wit kunnen we ook met symbolen werken, bijvoorbeeld 0 en 1. (We kunnen allerlei symbolen gebruiken, als we maar twee waarden kunnen onderscheiden.)

In tabelvorm worden de regels dan:

0 000 0
1 001 1
2 010 1
3 011 1
4 100 0
5 101 1
6 110 1
7 111 0


Dit voorbeeld is uitgewerkt in een spreadsheet. Dit bestand (Cellular Automaton) tref je aan bij Bijlagen.

Weergave van het proces in een spreadsheet
In de spreadsheet staan de opeenvolgende stappen van het proces onder elkaar. Zo kun je de loop van het proces volgen.
Deze aanpak zullen we ook in volgende opdrachten gebruiken. De eerste rij bevat de begintoestand, soms met de invoer.
Elke volgende rij bevat de volgende stap in het algoritme - waarvan het resultaat dan in cellen van de rij zichtbaar wordt.

Voor de spreadsheet met de cellulaire automaat hebben we ook tussenresultaten, namelijk een codering van het patroon van de cel en de buren; voor de overzichtelijkheid hebben we deze in een apart vel (sheet, tab) geplaatst.

Links en verdieping
In het Wikipedia-artikel over Rule 110 vind je een beschrijving van het gedrag van deze cellulaire automaat.
Een bijzondere eigenschap is dat deze automaat Turing-complete is: je kunt daarmee in principe alle mogelijke berekeningen uitvoeren.
Voor zover bekend is dit het eenvoudigste systeem waarmee dit kan.

Meer over cellulaire automaten vind je in het boek van Stephen Wolfram, A New Kind of Science. Dit boek is online beschikbaar. In dit boek vind je veel fraaie figuren die ontstaan uit zulke eenvoudige regels en automaten. Je vindt er ook figuren uit de natuur die soms verrassend sterk lijken op deze figuren, zoals in hoofdstuk 8 (bijv. p. 423, p. 426).

Opdracht voor jezelf:

Formuleer nu zelf een lesdoel voor deze opdracht. Wat heb je door het maken van deze opdracht geleerd?