Categorie archief: Compuermodellen

Cellulaire automaten en badkamertegels.

In de vorige blog beschreef ik de game of life als voorbeeld van een cellulaire automaat.

Life is twee-dimensionaal, de cellen leven in een vierkant of rechthoek. Iedere cel heeft acht buren.  Een simpeler versie van een cellulaire automaat is de één-dimensionale. Hier heeft iedere cel maar twee buren. Dat geeft natuurlijk minder mogelijkheden. Het voordeel is dan weer wel dat je alle tijdstappen onder elkaar kunt tekenen. In één oogopslag zie hoe de automaat zich in de tijd ontwikkeld. En op die manier ontstaan vaak mooie patronen.

Bij één-dimensionale automaten wordt de regel waarmee de cellen veranderen vaak als een getal weergegeven. De nieuwe waarde van een cel hangt af van de waarde van de cel zelf en zijn twee buren. Dat geeft 8 verschillende combinaties: 111, 110, 101, 100, 011, 010, 001 en 000. De drie cijfers zijn de waarde van de cellen van links naar rechts. Voor iedere combinatie bepaalt de regel of de volgende waarde van de cel een 0 of 1 moet worden. Bijvoorbeeld:

111 110 101 100 011 010 001 000
1 0 0 1 1 0 0 1

Deze regel kun je dus schrijven als 10011001 in binaire notatie. In ons decimale stelsel is dat 153. Er zijn op deze manier 256 verschillende regels.

Hieronder kun je al deze regels uitproberen: vul een getal in tussen 0 en 255 en druk op “Start”. Wil je een andere proberen: maak schoon en start opnieuw.  Ik heb in de bovenste regel 1 vakje zwart gemaakt. Door te klikken kun je er meer zwart maken.

Probeer een aantal getallen uit. In veel gevallen zie je een regelmatig patroon van driehoeken ontstaan, maar soms ook patronen die tegelijkertijd regelmatig lijken maar zichzelf toch niet herhalen. Eén van die patronen vond ik zo mooi dat ik het gebruikt heb toen mijn nieuwe badkamer betegeld moest worden:

Aan de lezer is het om te ontdekken welk getal bij deze regel hoort. De tegelzetter vond het overigens wel interessant maar begreep het niet helemaal. De afdruk die ik hem gegeven had met het patroon was iets te klein. Hij heeft toen een willekeurige kleur gepakt. De foute. Kun je de fout vinden op de foto?

 

Cellulaire automaten – leven in de computer

Een van de leukste dingen die de combinatie van wiskunde en computers heeft opgeleverd zijn cellulaire automaten. Het principe ervan is simpel: je hebt een verzameling hokjes, die elk een cijfer bevatten. Vaak kan dat alleen een 1 of een 0 zijn. Daarnaast heb je regels die bepalen wat er met de vakjes gebeurt. Bijvoorbeeld: “Als ik een 0 ben en drie van mijn acht buren zijn een 1, dan word ik ook een 1. Een bekend voorbeeld is de Game of Life, bedacht door James Conway. Bij deze automaat (een spel is het niet echt) zijn de vakjes met enen en nullen in een vierkant of rechthoek gerangschikt en gelden de volgende regels:

Bij een 1: Als van je 8 buren er twee of drie een ook een 1 zijn, blijf dan een 1.
Bij een 0: Als je precies drie buren hebt die 1 zijn wordt je een 1.
In alle andere gevallen wordt je een 0.

Als je alle vakjes met een 1 inkleurt krijg je iets dat er als volgt uitziet:

Druk op “Stap” om de regels één keer toe te passen. Je ziet het patroon veranderen. Druk op “Start” om de regels keer op keer toe te passen. Een beetje afhankelijk van het beginpatroon kan een wild, dynamisch patroon ontstaan. Probeer ook het volgende eens uit. Druk op “Stop”, en dan op “Schoon”. Klik dan een paar vakjes aan tot je het volgende patroon ziet:

En druk op start. Je hebt leven gemaakt: dit patroon schuift in vier stappen schuin naar boven. Dit patroon heet – niet verrassend – een glider. Gliders zijn kwetsbaar, bij de kleinste verstoring gaan ze dood. Zet maar eens een zwart vakje op zijn route, of laat er twee botsen.

Life is interessant omdat het mooi laat zien dat je met simpele regels ingewikkeld gedrag kunt krijgen. Als je de wilde patronen zou zien zonder eerst mijn verhaal te lezen zou je waarschijnlijk niet vermoeden dat de onderliggende regels zo simpel zijn. Ondanks die simpele regels blijkt dat de Game of Life veel mogelijkheden biedt. Er zijn patronen die oneindig uitgroeien, gliders, ruimteschepen en zelfs is het mogelijk een programmeerbare computer in life te maken. Voorbeelden kun je vinden op de wikipedia-pagina (en hierboven uitproberen). En op deze site vind je een programma waarmee je allerlei cellulaire automaten kunt proberen, op een groot veld met verschillende regels. En cellulaire automaten zijn een mooie inspiratie als je een badkamer moet betegelen, maar daarover een volgende keer.