Cellulaire automaat
Een cellulaire automaat (Engels: cellular automaton) is een discreet model uit de automatentheorie dat onder andere wordt toegepast in de wiskunde (berekenbaarheidstheorie) en theoretische biologie.
Het model bestaat uit een één- of meer-dimensionaal raster van cellen met elk een eindig aantal toestanden. Een volgende toestand wordt door toepassing van een gegeven set regels berekend uit de huidige toestand van de cel en die van zijn directe buren. Door het herhaald toepassen van dezelfde regels ontstaan vaak spontaan patronen die nu en dan grote gelijkenis vertonen met wat in de natuur wordt aangetroffen, zoals in de groeipatronen van kristallen en in kolonies koralen.
Een bekend voorbeeld van een cellulaire automaat is de Game of Life van John Conway.
Geschiedenis
bewerkenIn de jaren 50 probeerde John von Neumann een machine te maken die zichzelf kon nabouwen (de zogeheten universele constructor). Hij trachtte een wiskundige abstractie te maken voor zelfreproductie zoals dat in de natuur plaatsvindt. Na verschillende mogelijkheden bekeken te hebben, kwam hij tot de conclusie dat een tweedimensionaal systeem voldoende moest zijn voor zelfreproductie. Hij slaagde hierin en construeerde de eerste cellulaire automaat met 29 verschillende toestanden en allerlei regels die de mechanismen in elektronica en mechanische machines konden emuleren. Hij gaf een beschrijving van zijn zelfreproducerende machine die uit 200.000 cellen bestond. In 1960 werden de details van het bewijs uitgewerkt door Arthur Burks.
In 1970 kwam John Conway met zijn Game of Life, een tweedimensionale cellulaire automaat die overeenkomsten vertoont met echte levende wezens, zoals emergentie en zelforganisatie. Het werd populair na vermelding in de column Mathematical Games van Martin Gardner in Scientific American. Ondanks de eenvoudige regels konden complexe patronen ontstaan die zichzelf herhaalden of die zich voortbewogen over het raster. Een voorbeeld hiervan is de glider, het bekendste patroon in Game of Life dat zich voortbeweegt.
In 1983 en in 2002 (in zijn boek A New Kind of Science) bestudeerde Stephen Wolfram eendimensionale cellulaire automaten met twee toestanden; de zogenoemde elementaire cellulaire automaten. Deze kregen elk een eigen nummer aan de hand van de regels die de cellulaire automaat gebruikte. Deze cellulaire automaten vertoonden bepaalde eigenschappen zoals het genereren van willekeurige patronen (Regel 30) of Turingvolledigheid (Regel 110).
Zie ook
bewerkenExterne links
bewerken- (en) History of cellular automata, Stephen Wolfram, A New Kind of Science
