Elementaire cellulaire automaat
Een elementaire cellulaire automaat is een eendimensionale cellulaire automaat met twee toestanden. De nieuwe toestand van een cel hangt alleen af van die cel en de naastgelegen cellen. Er zijn slechts 8 (23) verschillende mogelijkheden voor de toestanden van drie cellen naast elkaar waardoor er 256 (28) elementaire cellulaire automaten bestaan. Deze soort cellulaire automaten werden voor het eerst bestudeerd door Stephen Wolfram in 1983.
Een voorbeeld van een elementaire cellulaire automaat is regel 110 die gebruikmaakt van de volgende regels:
| huidig patroon | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| nieuw toestand voor middelste cel | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Deze cellulaire automaat wordt regel 110 genoemd aangezien het binaire getal 01101110 (de onderste rij in de tabel hierboven) in het decimale stelsel gelijk is aan 110. De 256 elementaire cellulaire automaten krijgen op deze wijze elk een eigen naam op basis van de regels.
Voorbeelden bewerken
Enkele noemenswaardige elementaire cellulaire automaten zijn:
- Regel 30 (genereert complexe, schijnbaar willekeurige patronen met toch eenvoudige regels)
- Regel 110 (enige waarvan turingvolledigheid is bewezen)
- Regel 184 (gebruikt om het zogeheten majority problem op te lossen)
Externe links bewerken
- (en) Elementary Cellular Automaton, MathWorld
- (en) Elementary Cellular Automata, Wolfram Atlas