Cellulaire automaten

Het spel Game of Life is een voorbeeld van een tweedimensionale cellulaire automaat:
het spel speelt zich af in het platte vlak.
In dit gedeelte gaan we verder in op eendimensionale cellulaire automaten: een toestand bestaat uit een reeks cellen op één lijn.
Je kunt de opeenvolgende toestanden dan onder elkaar plaatsen: in het platte vlak zie je dan in één oogopslag het proces: de ontwikkeling van het algoritme in de tijd.

In een eendimensionale cellulaire automaat heeft een cel 2 buren: links en rechts.
De volgende toestand van een cel hangt af van de huidige toestand van de cel en zijn twee buren.
Voor 3 cellen heb je 8 mogelijke configuraties. De regels van de automaat beschrijven voor elke configuratie welke kleur cel deze oplevert.

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).