9 Zelluläre Automaten
Bei der Beschreibung von Prozessen in der Natur spielt nicht nur die Veränderung der Zustandsgrößen im Laufe der Zeit eine Rolle. Häufig möchte man zusätzlich auch Informationen über die räumliche Verteilung haben. Stellt man sich eine Rasenfläche vor, und möchte man die Grasmenge auf dieser Fläche modellieren, so kann man natürlich ein Modell entwickeln, dass die Grasmenge auf dieser Fläche im Laufe der Jahreszeiten beschreibt. Dann hat man aber keinerlei Informationen darüber, ob auf dieser Rasenfläche an einigen Stellen braune Stellen oder dicke Grasbüschel existieren. Hierzu benötigt man ein Modell, das die Grasfläche räumlich beschreibt. Hierzu kann man die Rasenfläche zum Beispiel in Quadrate einteilen. Man kann nun Wachstumsregeln aufstellen, die das Graswachstum beschreiben. Ist z.B. ein Quadrat von braunen Stellen umgeben, d.h., dass auf den Nachbarquadraten sehr wenig Gras ist, so wird das Gras auch in der Mitte schlecht wachsen, da der Schutz vor Wind fehlt. Sind um ein Quadrat dicke Grasbüschel, so werden die Nährstoffe knapp und auch dann kann das Gras schlecht wachsen.
Das Konzept der sogenannten zellulären Automaten wurde 1940 vom Mathematiker Stanislav Ulam (1909-1984) entwickelt. John von Neumann (1903-1957), ein bedeutender Mathematiker und Begründer der Informatik, entwickelte das Konzept weiter. Einer der berühmtesten Automaten ist Game of Life (\(\sim\)1970) von John Horton Conway (1937-2020).
9.1 Universum nach Stephan Wolfram
Ein eindimensionaler Automat wurde vom britischen Physiker Stephen Wolfram (*1959) entwickelt. Wolfram ist der Entwickler von Mathematica und der Suchmaschine Wolfram Alpha. Sein Buch (Wolfram 2002) beschreibt viele Anwendungen zellulärer Automaten.
Ein einfaches Beispiel ist folgender Automat: Wir teilen den Raum in eine Reihe von Zellen auf (z.B. 150). Jede Zelle kann den Zustand tot oder lebendig (0 oder 1) annehmen. Nun kann man mit einer lebendigen Zelle in der Mitte starten.
Die Konstellation im nächsten Schritt ergibt sich nach folgender Regel:
Eine Zelle erhält den neuen Zustand 1, wenn in dem Dreierblock aus ihr selbst und ihren zwei Nachbarn ein oder zwei lebendige Zellen waren.
Eine Zelle erhält den neuen Zustand 0, wenn in dem Dreierblock aus ihr selbst und ihren zwei Nachbarn null oder 3 lebendige Zellen waren.
Nun kann man die Generationen untereinander auftragen und erhält folgendes Ergebnis (Abbildung 9.1).
Wenn die letzte Zelle wieder an die erste angehängt wird (Ring), haben auch die Randzellen 2 Nachbarn. Man kann dann mehr Generationen rechnen, ohne Randeffekte zu erhalten.
Man kann die Regeln wie folgt formalisieren:
Man kann sich nun viele Regeln ausdenken, die jeweils eindeutig durch eine achtstellige Binärzahl dargestellt werden, wenn man sich auf die Reihenfolge der Triplets einigt. Wolfram hat die obige Reihenfolge benutzt und die achtstellige Binärzahl in eine Dezimalzahl gewandelt. So konnte er alle möglichen Regeln einfach von 0 bis 255 “benennen”. Insgesamt gibt es also 256 Regelsätze. Die obige Regel ist dann die Nummer 126 (Binär 01111110).
9.2 Conway’s Game of Life
Ein berühmter Automat ist LIFE. Er wurde von John Horton Conway im Jahre 1970 zur Beschreibung einer fiktiven Bevölkerung entwickelt. Jedes Quadrat, auch Zelle genannt, kann hierbei zwei Zustände annehmen, tot (0) oder lebendig (1). Conway hat folgende Regeln aufgestellt:
Eine Zelle wird geboren, wenn sie drei lebende Nachbarn hat.
Eine Zelle bleibt am Leben, wenn sie zwei oder drei lebende Nachbarn hat.
Eine Zelle stirbt an Vereinsamung oder Überbevölkerung, wenn sie weniger als zwei oder mehr als drei lebende Nachbarn hat.
Nachbarn sind die 8 Zellen um eine Zelle herum.
Mit diesen Regeln ergeben sich interessante Ergebnisse. Es gibt Konstellationen, die sich über die Zeit nicht ändern, andere die Zyklen durchlaufen, welche die sich über das Feld bewegen (Gleiter) und solche, die in gewissen Abständen Gleiter aussenden.
9.3 Zirkulärer Raum
Der zirkuläre Raum ist ein berühmtes Beispiel für Selbstorganisation. Nach einer geringen Anzahl von Schritten bilden sich Strukturen heraus.
Es gibt N mögliche Zustände
Der Zustand der Zelle wird um Eins erhöht, wenn mindestens ein Nachbar den Zustand der Zelle plus Eins hat.
Jede Zelle hat 4 Nachbarn (links, rechts, oben und unten)
Der Zustand 0 wird mit dem Zustand N gleichgesetzt
9.4 Charakteristika von zellulären Automaten
Die Charakteristika von zellulären Automaten kann man wie folgt zusammenfassen:
Entwicklung in Raum und Zeit
diskrete Anzahl an Zellen
endliche Anzahl an Zuständen für jede Zelle (kann man aufweichen)
Änderung der Zustände in diskreten Zeitschritten
Zustand hängt von den Nachbarzellen ( und evtl. der Zelle selbst) ab
alle Zellen Verhalten sich nach den gleichen Regeln
9.4.1 Nachbarschaftsbeziehungen
Der Zustand einer Zelle hängt von den Zuständen seiner Nachbarn ab. Man kann verschiedene Nachbarschaftsbeziehungen betrachten.
4 Nachbarn (oben,unten, rechts und links)
8 Nachbarn (alle direkt angrenzenden Zellen)
die Zelle selbst kann zu den Nachbarn gezählt werden
entferntere Zellen werden hinzugenommen
9.4.2 Randbedingungen
Man kann die Ränder offen lassen, so dass die Randzellen einfach weniger Nachbarn haben. In diesem Fall wird der Zustand der Randzellen je nach Automat anders ausfallen als der der Zellen in der Mitte. Will man dies vermeiden schließt man das Feld zu einem Torus. Dann haben alle Zellen gleich viele Nachbarn.
9.4.3 Erweiterungen
Man kann neben diskreten Zuständen auch kontinuierliche Werte für die einzelnen Zellen zulassen. Damit lassen sich Prozesse wie Diffusion und Advektion beschreiben (siehe Kapitel 10).