Overzicht 2-dimensionale automaten

		Cellular automata in twee dimensies De bekendste 2-dimensionale cellular automaat is die van de wiskundige John Horton Conway en staat bekend onder de titel 'Life' of 'Game of Life'. Het werd populair door de aandacht die Martin Gardner er aan schonk in de Scientific American van oktober 1970. In dit artikel wordt er nog van uitgegaan dat het spel gespeeld wordt op iets als een dambord en niet op een PC, simpelweg omdat die er in 1970 niet waren. De regels van Conway's Life zijn erg simpel. Wat met een brik op een vlak (cel) van het bord gebeurt hangt af van de directe omgeving van de cel (de acht cellen die grenzen aan de cel) en de huidige toestand van de cel. De regels waarmee de volgende situatie (de volgende genratie) wordt berekend zijn: Elke dambrik met twee of drie brikken in zijn omgeving blijft op het bord. Elke brik met vier of meer brikken in zijn omgeving verdwijnt (vanwege "overbevolking"). Elke brik met één brik in zijn omgeving verdwijnt (vanwege "eenzaamheid"). Elke lege cel met precies drie brikken in zijn omgeving krijgt in de volgende generatie een brik ("geboorte"). Uitgaande van deze simpele regels kunnen interessnte startsituaties worden bedacht. Een voorbeeld hiervan is te zien op een wikipedia-pagina over Conway's Life, waar een beginsituatie wordt getoond die als een soort "kanon" steeds opnieuw "kogels" afvuurt. Karakterisering cellular automaten Er zijn erg veel verschillende 2-dimensionale cellular automaten, ook al beperkt men zich in het aantal waarden dat de cel kan aannemen. Vaak beperkt men zich tot een subverzameling van alle mogelijke automaten. De meest bekende beperking is dat alleen "totalistic" rules worden geaccepteerd. Hierbij is alleen het totaal aantal cellen uit de omgeving dat een waarde heeft van belang en niet hoe die waarde verdeeld is over de verschillende cellen. Als er twee cellen in de omgeving zijn die de waarde 1 heeft, dan maakt het niet uit of het twee cellen zijn die naast elkaar liggen of dat ze tegenover elkaar liggen: alleen het feit dat er twee enen zijn is van belang. Conway's Life is een voorbeeld van een totalistic rule. Daarnaast speelt in de karakterisering het aantal kleuren natuurlijk een rol. Hieronder staat een link naar een cellular automaat waarin een computer (met flip-flops, and-poorten, ALU, memory en alles wat voor een computer nodig is) kan worden gemaakt. De omgeving van een cel in die wereld zijn de acht cellen rondom die cel en het aantal kleuren is vier (zwart voor het niets, koper voor het aangeven van electrische leidingen, en de kleuren wit en blauw voor de beweging van 'electronen'). Ook voor deze automaat gaat het om totalistic rules. Soms spelen niet alle acht cellen rondom een cel mee voor de bepaling van de nieuwe waarde. Soms beperkt men zich tot alleen de vier cellen die niet diagonaal ten opzichte van de cel staan. Zo'n omgeving van een cel wordt de 'von neumann'-omgeving genoemd, terwijl de omgeving waarin wel alle acht cellen van belang zijn de 'Moore'-omgeving wordt genoemd. Rules worden vaak onder een code gepresenteerd. Stel dat we ons beperken tot totalistic rules met slechts twee kleuren, uitgaand van een Moore-omgeving. Omdat er van totallistic rules wordt uitgegaan zijn er slechts negen situaties mogelijk (alle acht cellen zijn 0 tot en met alle acht cellen zijn 1). Verder kan de cel waaromheen de omgeving ligt de waarde 0 of 1 hebben. De codering van Conway's Life kan dan de volgende vorm aannemen: [Moore,Doodgaan{1,4,5},Geboorte{3}]. Doodgaan geeft verandering aan als de cel zelf de waarde 1 heeft. Geboorte geeft verandering aan als de cel zelf de waarde 0 heeft. Als er geen verandering optreedt wordt dit niet in de codering opgenomen. Uitgerust met een dergelijke codering is het vervolgens mogelijk programma's te schrijven die niet alleen met de rule van Life kunnen werken, maar waarbij ook andere coderingen kunnen worden opgegeven. Een voorbeeld hiervan is Cellab (zie link hieronder). Op de site van Fourmilab is meer te vinden over het programma Cellab en een aantal rules. Op de site van Quinaplus is meer te vinden over de Wireworld computer in twee dimensies.

Cellular automata in twee dimensies

De bekendste 2-dimensionale cellular automaat is die van de wiskundige John Horton Conway en staat bekend onder de titel 'Life' of 'Game of Life'. Het werd populair door de aandacht die Martin Gardner er aan schonk in de Scientific American van oktober 1970. In dit artikel wordt er nog van uitgegaan dat het spel gespeeld wordt op iets als een dambord en niet op een PC, simpelweg omdat die er in 1970 niet waren.

De regels van Conway's Life zijn erg simpel. Wat met een brik op een vlak (cel) van het bord gebeurt hangt af van de directe omgeving van de cel (de acht cellen die grenzen aan de cel) en de huidige toestand van de cel. De regels waarmee de volgende situatie (de volgende genratie) wordt berekend zijn:

Elke dambrik met twee of drie brikken in zijn omgeving blijft op het bord.
Elke brik met vier of meer brikken in zijn omgeving verdwijnt (vanwege "overbevolking").
Elke brik met één brik in zijn omgeving verdwijnt (vanwege "eenzaamheid").
Elke lege cel met precies drie brikken in zijn omgeving krijgt in de volgende generatie een brik ("geboorte").

Uitgaande van deze simpele regels kunnen interessnte startsituaties worden bedacht. Een voorbeeld hiervan is te zien op een wikipedia-pagina over Conway's Life, waar een beginsituatie wordt getoond die als een soort "kanon" steeds opnieuw "kogels" afvuurt.

Karakterisering cellular automaten

Er zijn erg veel verschillende 2-dimensionale cellular automaten, ook al beperkt men zich in het aantal waarden dat de cel kan aannemen. Vaak beperkt men zich tot een subverzameling van alle mogelijke automaten. De meest bekende beperking is dat alleen "totalistic" rules worden geaccepteerd. Hierbij is alleen het totaal aantal cellen uit de omgeving dat een waarde heeft van belang en niet hoe die waarde verdeeld is over de verschillende cellen. Als er twee cellen in de omgeving zijn die de waarde 1 heeft, dan maakt het niet uit of het twee cellen zijn die naast elkaar liggen of dat ze tegenover elkaar liggen: alleen het feit dat er twee enen zijn is van belang. Conway's Life is een voorbeeld van een totalistic rule.

Daarnaast speelt in de karakterisering het aantal kleuren natuurlijk een rol. Hieronder staat een link naar een cellular automaat waarin een computer (met flip-flops, and-poorten, ALU, memory en alles wat voor een computer nodig is) kan worden gemaakt. De omgeving van een cel in die wereld zijn de acht cellen rondom die cel en het aantal kleuren is vier (zwart voor het niets, koper voor het aangeven van electrische leidingen, en de kleuren wit en blauw voor de beweging van 'electronen'). Ook voor deze automaat gaat het om totalistic rules.

Soms spelen niet alle acht cellen rondom een cel mee voor de bepaling van de nieuwe waarde. Soms beperkt men zich tot alleen de vier cellen die niet diagonaal ten opzichte van de cel staan. Zo'n omgeving van een cel wordt de 'von neumann'-omgeving genoemd, terwijl de omgeving waarin wel alle acht cellen van belang zijn de 'Moore'-omgeving wordt genoemd.

Rules worden vaak onder een code gepresenteerd. Stel dat we ons beperken tot totalistic rules met slechts twee kleuren, uitgaand van een Moore-omgeving. Omdat er van totallistic rules wordt uitgegaan zijn er slechts negen situaties mogelijk (alle acht cellen zijn 0 tot en met alle acht cellen zijn 1). Verder kan de cel waaromheen de omgeving ligt de waarde 0 of 1 hebben. De codering van Conway's Life kan dan de volgende vorm aannemen: [Moore,Doodgaan{1,4,5},Geboorte{3}]. Doodgaan geeft verandering aan als de cel zelf de waarde 1 heeft. Geboorte geeft verandering aan als de cel zelf de waarde 0 heeft. Als er geen verandering optreedt wordt dit niet in de codering opgenomen. Uitgerust met een dergelijke codering is het vervolgens mogelijk programma's te schrijven die niet alleen met de rule van Life kunnen werken, maar waarbij ook andere coderingen kunnen worden opgegeven. Een voorbeeld hiervan is Cellab (zie link hieronder).

Op de site van Fourmilab is meer te vinden over het programma Cellab en een aantal rules.

Op de site van Quinaplus is meer te vinden over de Wireworld computer in twee dimensies.