Zellulärer Automat

Zelluläre oder auch Zellulare Automaten dienen der Modellierung räumlich diskreter dynamischer Systeme, wobei die Entwicklung einzelner Zellen zum Zeitpunkt t+1 primär von den Zellzuständen in einer vorgegebenen Nachbarschaft und vom eigenen Zustand zum Zeitpunkt t abhängt.

Beschreibung

Ein Zellularautomat ist durch folgende Größen festgelegt:

ein Raum R (Zellraum)
eine endliche Nachbarschaft N
eine Zustandsmenge Q
eine lokale Überführungsfunktion $\delta:Q^N \to Q$

Der Zellraum besitzt eine gewisse Dimensionalität, die in der Regel 1-dimensional oder 2-dimensional ist, aber durchaus auch höher sein kann. Man beschreibt das Aussehen eines Zellularautomaten durch eine globale Konfiguration, welches eine Abbildung aus dem Zellraum in die Zustandsmenge ist, das heißt man ordnet jeder Zelle des Automaten einen Zustand zu. Der Übergang einer Zelle von einem Zustand (lokale Konfiguration) in den nächsten wird durch Zustandsübergangsregeln definiert, die deterministisch oder stochastisch sein können. Die Zustandsübergänge erfolgen für alle Zellen nach der selben Überführungsfunktion und gleichzeitig. Die Zellzustände können wie die Zeitschritte diskret sein. In der Regel ist die Anzahl der möglichen Zustände klein: Nur wenige Zustandswerte reichen zur Simulation selbst hochkomplexer Systeme aus.

Man unterscheidet zwei verschiedene Nachbarschaften (auch Nachbarschaftsindex genannt):

Geschichte der Zellularautomaten

Zellularautomaten wurden um 1940 von Stanislaw Ulam in Los Alamos vorgestellt. John von Neumann, ein damaliger Kollege von Ulam, griff die Idee auf und erweiterte sie zu einem universellen Berechnungsmodell. Er stellte einen Zellularautomaten mit 29 Zuständen vor, der ein gegebenes Muster immer wieder selbst reproduzieren konnte. Er beschrieb damit als erster einen Zellularautomaten, der berechnungs- und konstruktionsuniversell ist.

Bis zu den 1960er Jahren waren die Analogrechner den Digitalrechnern bei einigen Fragestellungen überlegen. Ein analoger Zellulärer Automat zur Simulation von Grundwasserströmungen wird im Artikel Analogrechner genauer beschrieben.

In den 1970er Jahren erlangte John Horton Conways Game of Life Berühmtheit. Es besteht aus einem 2-dimensionalen Raum, auf dem die Moore-Nachbarschaft definiert wurde. Jede Zelle kann einen von zwei Zuständen annehmen Q = {0,1}, die man als tot oder lebendig interpretieren kann. Dann gilt folgende Überführungsfunktion:

\delta(l) = \begin{cases} \mbox{0, falls } \sum_{n \in N} l(n) \leq 2 \\ \mbox{1, falls } \sum_{n \in N} l(n) = 3 \\ \mbox{l(0), falls } \sum_{n \in N} l(n) = 4 \\ \mbox{0, falls } \sum_{n \in N} l(n) \geq 5 \\ \end{cases}

1969 veröffentlichte Konrad Zuse sein Buch "Rechnender Raum", worin er animmt, dass die Naturgesetze diskreten Regeln folgen und das gesamte Universum das Ergebnis eines gigantischen Zellularautomaten sei.

1983 veröffentlichte Stephen Wolfram eine Reihe von grundlegenden Arbeiten zu Zellularautomaten. Stephen Wolframs 1-dimensionales Universum ist ein zellulärer Automat mit nur einer Raum- und einer Zeit-Dimension.

EIDU-9 Wolframs 1-dimensionales Universum.jpg

Stephen Wolframs zellulärer Automat ist ein besonders schönes und einfaches Modell-Universum. Es besteht aus nur einer Raumdimension und einer Zeitdimension. Im Bild ist die Raumdimension waagrecht eingezeichnet und die Zeitdimension verläuft senkrecht nach unten. (Das oben stehende Bild enthält drei verschiedene Bildausschnitte.) Die Raumdimension ist endlich, aber ohne Enden, denn ihr rechtes und linkes Ende sind topologisch miteinander verbunden.

Die Raum-Zeit-Elemente dieses Universums können nur leer oder voll sein. Beim Urknall (in den obersten Bildzeilen) werden diese Raum-Zeit-Elemente mit 50-prozentiger Wahrscheinlichkeit gefüllt. Es gibt nur ein Naturgesetz, das eine Nahewirkung darstellt. Der Nahbereich umfasst die linken zwei Nachbarn eines Raum-Zeit-Elements, das Raum-Zeit-Element selbst, und die rechten zwei Nachbarn des Raum-Zeit-Elements. Wenn zwei oder vier Raum-Zeit-Elemente im Nahbereich voll sind, dann ist im nächsten Zeitintervall dieses Raum-Zeit-Element auch voll, ansonsten ist es im nächsten Zeitintervall leer. Es existieren keine weiteren Regeln.

Obwohl es im Gegensatz zu Computer-Spielen keine Fernwirkung und keinerlei Kontrollinstanz gibt, entwickelt sich dieses Modell-Universum zu verblüffender Komplexität. Nach dem Urknall findet eine Eliminationsphase statt, so wie im echten Universum auch. Danach entstehen kurzlebige, aber geordnete Strukturen, die irgendwann erlöschen. Einige der geordneten Strukturen sind aber langzeitstabil, manche davon oszillieren, andere davon sind in der Zeit formstabil. Sowohl von den oszillierenden als auch von den formstabilen existieren sowohl ortsfeste als auch bewegliche Arten. Die maximale Austauschgeschwindigkeit dieses Universums kann nur zwei Raumeinheiten pro eine Zeiteinheit betragen. Wenn zwischen den stabilen bewegten Objekten Kollisionen stattfinden, dann setzt wieder Chaos ein, und eine weitere Eliminationsphase findet statt.

Vereinfacht man noch weiter und berücksichtigt neben dem Zustand des Elementes selbst nur jeweils das rechte und das linke Nachbarelement, gibt es genau 256 Regeln. Selbst unter diesen noch einfacheren Automaten zeigen einige eine erstaunliche Komplexität. Die interessanteste ist die "Regel 110":

Regel 110

neuer Zustand der Zelle	0	1	1	0	1	1	1	0
momentaner Zustand	111	110	101	100	011	010	001	000

CA rule110 x400 y200 single.png

CA rule110 x3200 y3200 single.png

Beispiele für zelluläre Automaten

Conways Spiel des Lebens (Game of Life) ist ein einfacher zweidimensionaler zellulärer Automat der verblüffende Strukturen erzeugt.
Das Pascalsche Dreieck kann ebenfalls als einfacher zellulärer Automat interpretiert werden.
Das Nagel-Schreckenberg-Modell ist ein Zellularautomat zur Simulation des Straßenverkehrs insbesondere auf Autobahnen.

Siehe auch

Weblinks

http://www.entwurfsforschung.de/RaumProzesse/Grundlagen.htm
Applet eines Greenberg-Hastings-Automaten
Agenten-basierte Modellierungs- und Simulationsumgebung
Konverter von Turing-Maschine zur Regel 110
Webseite von Jürgen Schmidhuber über Konrad Zuses Theorie des Rechnenden Raumes (Auszug aus Elektronische Datenverarbeitung 8 (1967) S. 336-344)
Siehe auch einen Text von Karl Bednarik unter der GNU Freie Dokumentationslizenz.

Dynamik | Automatentheorie

Gourt Home::Gourt :: Zellulärer Automat

Beschreibung

Geschichte der Zellularautomaten

Beispiele für zelluläre Automaten

Siehe auch

Weblinks