Was sind zelluläre Automaten?
Den folgenden Kasten-Text habe ich mir von ChatGPT generieren lassen; ich habe ihn dann etwas überarbeitet, aber nicht groß verändert.
KI-generierter Text:
Zelluläre Automaten und ihre Anwendungsmöglichkeiten
Zelluläre Automaten sind mathematische Modelle, mit denen sich komplexe Vorgänge durch einfache Regeln simulieren lassen. Ein zellulärer Automat besteht aus vielen einzelnen Zellen, die beispielsweise in einem zweidimensionalen Gitter angeordnet sind. Jede Zelle besitzt einen bestimmten Zustand, zum Beispiel 0 (tot) oder 1 (lebendig). In jedem Zeitschritt wird der Zustand einer Zelle nach festgelegten Regeln neu berechnet. Dabei spielen meistens die Zustände der benachbarten Zellen eine entscheidende Rolle.
Obwohl die Regeln oft sehr einfach sind, können sich erstaunlich komplexe Muster und Verhaltensweisen entwickeln. Ein bekanntes Beispiel ist das Game of Life, das der Mathematiker John Conway 1970 entwickelte.
Anwendungen in Wissenschaft und Technik
Zelluläre Automaten werden in verschiedenen Bereichen eingesetzt:
- Biologie: Simulation der Ausbreitung von Krankheiten, des Wachstums von Zellpopulationen oder der Entwicklung räumlicher Muster in Organismen.
- Physik und Chemie: Modellierung von Diffusionsvorgängen, Kristallwachstum, chemischen Reaktionen und der Ausbreitung von Feuer.
- Verkehrstechnik: Simulation von Verkehrsströmen und Staus auf Autobahnen. Jedes Fahrzeug folgt dabei einfachen Regeln für Geschwindigkeit, Abstand und Bremsverhalten.
- Umweltwissenschaften: Untersuchung der Ausbreitung von Waldbränden, der Entwicklung von Vegetationsflächen oder der Veränderung von Landschaften.
- Informatik: Erforschung komplexer Systeme, paralleler Berechnungen und der Frage, wie aus einfachen lokalen Regeln komplexes Verhalten entstehen kann.
Warum sind zelluläre Automaten interessant?
Das Besondere an zellulären Automaten ist, dass aus wenigen einfachen Regeln ein komplexes Gesamtsystem entstehen kann, dessen Verhalten sich nicht immer leicht vorhersagen lässt. Dieses Phänomen bezeichnet man als Emergenz.
Zelluläre Automaten zeigen damit ein grundlegendes Prinzip der Natur und der Informatik: Komplexität muss nicht unbedingt durch komplizierte Regeln entstehen. Manchmal genügt es, wenn sehr viele einfache Elemente miteinander wechselwirken.
Das hört sich doch alles sehr interessant an. Bei der Bearbeitung dieses Textes und bei weiteren Recherchen in der Fachliteratur ist mir aber auch klar geworden, dass echte zelluläre Automaten viel komplexer sind als der kleine Modell-Automat, den wir in diesem Abschnitt 9.2 des Informatik-Kurses entwickeln.
Männchen der Perleidechs
Bernard DUPONT from FRANCE, CC BY-SA 2.0, via Wikimedia Commons
_male_found_under_a_stone_by_Jean_NICOLAS_(14166347788).jpg){kind=link}
Dieses Bild zeigt ein Beispiel für zelluläre Automaten in der Biologie: Das Muster auf dem Rücken der Perleidechse bildet sich nach ähnlichen Regeln wie bei einem zellulären Automaten.
Hier noch ein Zitat aus dem Spektrum-Artikel "Zelluläre Automaten in der Natur":
"Kommen zelluläre Automaten in der Natur vor? Manche Verfechter des Konzepts würden diese Frage mit einem klaren Ja beantworten. Mehr noch: Die ganze Welt sei ein zellulärer Automat. John von Neumann (1903–1957) zeigte schon in den 1940er Jahren, dass zelluläre Automaten erstaunlich vielfältige Verhaltensweisen aufweisen; John Horton Conway erfand einen berühmt gewordenen Automaten namens "Game of Life"; Konrad Zuse (1910–1995) arbeitete das Konzept in seinem Artikel "Rechnender Raum" aus, und Stephen Wolfram erhob 2002 in seinem Buch "A New Kind of Science" den – heftig umstrittenen – Anspruch, alle Wissenschaft auf zelluläre Automaten zurückführen zu können ..."
Nun etwas Theorie
Zellulärer Automat
Ein zellulärer Automat ist ein mathematisches Modell, das aus einer Menge von Zellen besteht. Jede Zelle befindet sich in einem bestimmten Zustand. Welche Zustände die Zellen in der nächsten Generation annehmen, wird durch eine Übergangsfunktion festgelegt. Diese berücksichtigt den bisherigen Zustand einer Zelle und die Zustände ihrer Nachbarzellen.
Formal kann ein zellulärer Automat durch ein 4-Tupel Z = (R, N, Q, δ) beschrieben werden, dabei ist
R = ein Raum (z.B. eine zweidimensionale Matrix)
N = eine endliche Nachbarschaft (z.B. die vier Nachbarzellen links, rechts, oben, unten)
Q = eine endliche Zustandsmenge (z.B. { gesund, krank, tot } oder {0, 1})
δ = eine Überführungs-Funktion.
Bei vielen zellulären Automaten hängt der neue Zustand nur von den Zuständen der Nachbarzellen ab. Der bisherige Zustand der betrachteten Zelle spielt dann keine Rolle.
Diese Definition hört sich recht theoretisch an. Aber wenn wir ein einfaches Beispiel betrachten, wird relativ schnell klar, was sich dahinter verbirgt.
Beispiel
Betrachten Sie folgende Abbildung:
Ein zellulärer Automat
Autor: Ulrich Helmich 2016, Lizenz: Public domain.
In der Abbildung sehen wir einen zellulären Automaten mit 16 x 16 Zellen, die in je zwei Zuständen vorkommen können, lebendig (grün) und tot (weiß). Jede Zelle hat genau vier Nachbarzellen. Bei fünf Zellen des Automaten wurde zur Verdeutlichung die Zahl der lebenden Nachbarzellen notiert.
Damit hätten wir die Komponenten R, N und Q dieses Zellulären Automaten schon einmal näher beschrieben:
R = der abgebildete "Raum" aus 16 x 16 Zellen.
N = die vier Nachbarn der betrachteten Zelle.
Q = {0,1} = die Menge der möglichen Zellzustände. Dabei bedeutet 0 "tot" und 1 "lebendig".
Es bleibt nur noch die Übergangs-Funktion δ.
Die Übergangsfunktion
Am anschaulichsten stellt man δ als Tabelle dar:
| Lebende Nachbarn | Neuer Zustand |
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 0 |
| 4 | 0 |
Alternativ könnte man δ auch rein verbal definieren:
"Wenn eine Zelle keine lebenden Nachbarn hat, soll sie im nächsten Zyklus tot sein. Hat eine Zelle einen oder zwei lebende Nachbarn, so soll sie im nächsten Zyklus lebendig sein. Bei drei oder vier lebenden Nachbarn soll eine Zelle im nächsten Zyklus tot sein."
Bei unserer Übergangsfunktion hängt der Zustand einer Zelle in der nächsten Generation ausschließlich davon ab, wie viele lebende Nachbarn sie besitzt. Ob die Zelle selbst bisher lebendig oder tot war, spielt keine Rolle.
Man könnte aber auch eine andere Übergangsfunktion definieren, die zusätzlich den bisherigen Zustand der Zelle berücksichtigt. In diesem Fall müsste unsere Tabelle um eine weitere Spalte erweitert werden, in der der bisherige Zustand der Zelle angegeben wird.
Schauen wir uns nun an, welche Auswirkungen diese Übergangs-Funktion auf die Verteilung der Zellen im Raum hat.
Betrachten wir zunächst die mit der Ziffer "0" markierte Zelle in der Abbildung 9.3 - 1. Diese tote Zelle hat keine lebenden Nachbarn, also wird ihr Zustand in der nächsten Generation wieder "tot" sein. Die mit der Ziffer "1" gekennzeichnete Zelle wird in der nächsten Generation den Zustand 1 oder "lebendig" haben, ebenso die mit der Ziffer "2" gekennzeichnete Zelle. Die lebenden Zellen "3" und "4" werden sterben.
Berechnung der nächsten Generationen↑
Der zelluläre Automat berechnet jetzt für jede einzelne Zelle mithilfe der Übergangs-Funktion den Folgezustand in der nächsten Generation, realisiert diesen neuen Zustand aber erst dann, wenn er mit der letzten Zelle fertig ist. Dadurch wird verhindert, dass bereits veränderte Zellen die Berechnung der übrigen Zellen beeinflussen.
Schauen wir uns das mal für ein sehr kleines Beispiel an:
Berechnung der Folgezustände über fünf Zyklen bzw. Generationen
Autor: Ulrich Helmich 2016, Lizenz: Public domain.
Die Zahlen in den Kästchen zeigen die Anzahl der jeweils lebenden Nachbarn. In der ersten Generation haben sieben tote Zellen genau einen Nachbarn. Diese sieben Zellen werden in der zweiten Generation dann lebendig sein. Die drei lebendigen Zellen der ersten Generation haben einen oder zwei lebende Nachbarn, laut Übergangsfunktion werden diese Zellen in der zweiten Generation ebenfalls lebendig sein.
In der zweiten Generation leben zehn Zellen, und nur sechs Zellen sind noch tot. Mit drei oder vier lebenden Nachbarn ist man in der nächsten Generation tot (weil das Gedränge einfach zu groß ist…), daher sterben fünf von den lebenden Zellen im dritten Zyklus ab. Umgekehrt werden fünf bisher tote Zellen wieder lebendig, weil sie einen oder zwei lebende Nachbarn haben.
Und so geht das immer weiter, über eine beliebige Anzahl von Generationen.
Eine Torus-Welt↑
Bei der Berechnung der Nachbarschaft sind die Randzellen und die Eckzellen problematisch. Randzellen haben drei, Eckzellen sogar nur zwei Nachbarn. Entweder muss dies bei der Übergangs-Funktion berücksichtigt werden, was diese natürlich enorm verkompliziert, oder es muss in die geometrische Trickkiste gegriffen werden. Wir "verkleben" einfach den linken Rand unserer Welt (1) mit dem rechten Rand, so dass wir einen Zylinder erhalten (2). Und jetzt wird es kompliziert: Wir verkleben den oberen Rand des Zylinders mit dem unteren Rand. So erhalten wir einen sogenannten Torus (3):
Eine Fläche wird zu einem Zylinder und dann zu einem Torus
Autor: Ulrich Helmich mit ChatGPT 2026
Das obere Bild wurde von ChatGPT 5.6 erstellt, wer genau hinschaut, findet ein paar kleine Fehler bei der Belegung der Zellen. Diese zu korrigieren war mir zu aufwendig, daher belassen wir es einfach mal dabei. Ich finde die Leistung der KI trotzdem sehr beeindruckend.
Einen Torus kennen Sie sicherlich aus dem Alltag: Ein Fahrradschlauch oder ein Reifen ist im Grunde auch ein Torus. In unserer Torus-Welt hat jetzt jedes Feld vier Nachbarn. Randfelder und Eckfelder gibt es nicht mehr.
Wir wollen jetzt einen solchen zellulären Automaten mithilfe einer Java-Anwendung simulieren. Dazu erzeugen wir ein Spielfeld aus 100 × 100 Zellen mit zwei möglichen Zuständen. Die Anfangszustände werden zufällig festgelegt. Anschließend können wir mithilfe eines Buttons die jeweils nächste Generation berechnen und grafisch darstellen lassen.
Workshop: Eine zweidimensionale Torus-Welt↑
Den eigentlichen Workshop habe ich in die nächste Seite ausgelagert.