... denn gemeinsam sind wir stark. (Volksmund)
Ein zellularer Automat (im folgenden kurz ZA genannt) ist ein diskretes dynamisches System, das sich durch die wiederholte Anwendung einfacher deterministischer Regeln entwickelt. Da es sich um ein deterministisches System handelt, ändert sich der Zustand des Systems als eine Funktion des aktuellen Zustands. Ein ZA ist daher ein Beispiel eines (endlichen oder unendlichen) Automaten. Wie wir noch sehen werden, läßt sich ein ZA aber noch treffender als ein Spezialfall eines Automatennetzwerks betrachten.
Eine andere Sichtweise zellularer Automaten ist die als Parallelrechner,
dessen Daten die Anfangskonfiguration darstellt.
Zellulare Automaten sind auch aus philosophischer Sicht äußerst interessante
und anregende Konstrukte.
Schließlich kann man einen ZA als eigenes logisches Universum mit einer eigenen Physik betrachten. Ein solches ZA-Universum kann trotz seiner einfachen mathematischen Konstruktion komplexes und überraschendes Verhalten hervorbringen.
Zur Definition eines ZA benötigen wir zuerst einen zellularen Raum (im folgenden ZR). Darunter verstehen wir einen n-dimensionalen Raum, der entsprechend einer gewünschten Geometrie in diskrete Zellen eingeteilt wird. Das können die Einheitsintervalle auf einer Geraden, Einheitsquadrate in der Ebene oder generell Einheitshyperwürfel im n-dimensionalen Raum sein. Es sind jedoch auch andere Geometrien denkbar, z. B. kann die Ebene in sechseckige Bienenwabenzellen eingeteilt werden, oder in gleichseitige Dreiecke.
Wie bei der Definition der Nachbarschaft
aber klar wird, können wir uns ohne Beschränkung der Allgemeinheit auf
die Einteilung des Raums in Hyperwürfel beschränken. Einen ZR betrachten
wir daher am einfachsten als Zn, wobei n die Dimension
des ZR, unds Z die Menge der ganzen Zahlen ist.
Aus diesem unendlichen ZR können wir nun (müssen es aber nicht) einen endlichen (oder aber immer noch unendlichen) ZR machen, indem wir Randbedingungen definieren. Unter Randbedingung verstehen wir an dieser Stelle, daß der ZR nicht aus Zn, sondern aus einer Teilmenge davon besteht. Den Begriff der Randbedingung werden wir aber bei der Definition der Zustandsüberführungsfunktion noch präzisieren müssen.
Wir benötigen für die Definition des ZA weiters eine endliche Menge
Z von Zuständen, die jede Zelle des ZR annehmen kann. Diese Zustände können
wir ohne Beschränkung der Allgemeinheit mit ganzen Zahlen numerieren, sodaß
wir im folgenden als Zustandsmenge die Menge {0, 1, ... z-1} für einen
ZA mit z Zuständen verwenden werden.
ZAs mit der Zustandsmenge {0, 1} nennen wir binäre ZAs.
Der Begriff der Nachbarschaft einer Zelle ist ein zentraler für ZAs. Salopp gesagt, besteht die Nachbarschaft einer Zelle aus einer endlichen Menge von Zellen, wobei alle Zellen "dieselbe" Nachbarschaft besitzen, und zwar in dem Sinne, daß wir die Nachbarschaft einer Zelle nur mit relativen Bezügen zu dieser Zelle spezifizieren. Dadurch genügt es, die Nachbarschaft für eine Zelle zu definieren, für jede andere Zelle erhalten wir die Nachbarschaft durch eine einfache Verschiebung.
Formal läßt sich das folgendermaßen ausdrücken (erinnern wir uns, daß
Elemente von Zn nichts anderes als Vektoren sind):
Die Nachbarschaftsbeziehung N eines ZA ist eine endliche Teilmenge
von Zn.
Die Nachbarschaft einer Zelle a ist dann die Menge aller a+b, wobei
b aus N ist.
Die Zellen
a-3, a-2, a-1, a und a+1 gehören zur Nachbarschaft.
Die Zellen a-3, a-2,
a+1 und a+2 gehören zur Nachbarschaft.
Eine
mögliche Nachbarschaft eines 2-dimensionalen ZA.
Nachbarschaft
in Conway's "Game of Life".
Mit der Zustandsmenge Z und der Nachbarschaft N haben wir nun das Rüstzeug, um aus jeder Zelle einen endlichen Automat im klassischen Sinn des Wortes zu machen. Der Zustand des Automats ist (natürlich) der Zustand der Zelle, die Eingabe besteht aus den Zuständen der Zellen aus der Nachbarschaft dieser Zelle (alles zum Zeitpunkt t). Wir brauchen nun nur noch eine Zustandsüberführungsfunktion ZF, die den Zustand der Zelle zum Zeitpunkt t+1 berechnet. Der Automat hat weiters keine Ausgabe.
Damit haben wir auch den Begriff des Zeittakts eingeführt. Ein ZA entwickelt sich nämlich in diskreter Zeit, d. h. der Zustand des ZA (damit ist die Gesamtheit der Zustände seiner Zellen gemeint) zu einem bestimmten Zeitpunkt t+1 ist eine Funktion des Zustands zum Zeitpunkt t.
Wie bereits bei der Definition des ZR angedeutet, müssen wir den Begriff der Randbedingung näher spezifizieren. Ein Problem ergibt sich nämlich daraus, daß die Nachbarschaft einer Zelle Zellen enthalten kann, die nicht im ZR liegen. Der Zustand dieser Zellen wird aber für die Berechnung der Zustandsüberführungsfunktion benötigt. Als weiteren Teil der Randbedingung wollen wir daher fordern, daß darin der Zustand solcher Zellen festgelegt wird.
Wir haben bereits den Zustand einer Zelle und den Zustand des ZA als Gesamtheit der Zustände seiner Zellen definiert. Wie alle dynamischen Systeme benötigt auch ein ZA einen Anfangszustand, d. h. eine anfängliche Belegung der Zellen mit Zuständen. Falls wir es mit einem unendlichen ZA zu tun haben, müssen wir an den Anfangszustand und an die Zustandsüberführungsfunktion allerdings einige Bedingungen stellen, um die Simulation des ZA per Computer zu ermöglichen.
Die vorliegende Charakterisierung von zellularen Automaten muß um einige Einschränkungen erweitert werden, um unendliche ZAs mit Hilfe von Computern (bzw. überhaupt) berechenbar zu machen. Ein endliches System wie ein Computer oder auch ein menschlicher Simulator kann von Natur aus keinen unendlichen ZA simulieren. Aus diesem Grund wollen wir uns einen unendlichen ZA als einen "potentiell" unendlichen ZA vorstellen, und nun formal präzisieren, was wir damit meinen, nämlich daß es eine endliche Teilmenge des ZR gibt, in dem sich das wirklich "interessante" Geschehen abspielt, während alle Zellen außerhalb dieser Teilmenge nicht nur irrelevant sind, sondern ohne individuelle Betrachtung berechnet werden können.
Als erstes fordern wir, daß die Zustandsmenge einen besonderen Zustand enthält, den wir mit 0 bezeichnen wollen. Die Zustandsüberführungsfunktion soll, wenn alle Eingangszustände diesen Wert 0 haben, als Ergebnis wieder 0 liefern. Jede Zelle, deren Nachbarschaft zur Gänze aus diesem 0-Zustand besteht, nimmt daher im nächsten Zeittakt ebenfalls den 0-Zustand an.
Zweitens definieren wir den Träger eines zellularen
Raums als die Menge aller Zellen, deren Zustand nicht der 0-Zustand
ist.
Um einen Zeittakt
eines ZA durch einen Computer berechnen lassen zu können, fordern wir,
daß der Träger aus nur endlich vielen Zellen bestehen soll. Es ist leicht
einzusehen (und auch zu beweisen), daß dann auch die Menge aller Zellen,
in deren Nachbarschaft Zellen
mit einem von 0 verschiedenen Zustand vorkommen, endlich ist, und nur diese
müssen für die Berechnung des Folgezustands des ZA in Betracht gezogen
werden. Außerdem hat auch der Folgezustand wieder einen endlichen Träger,
womit die Simulierbarkeit über beliebig viele Zeittakte sichergestellt
ist.
Um die Simulierbarkeit eines ZA zu garantieren, genügt es daher, für den Anfangszustand einen endlichen Träger zu fordern.
Die vorgestellte Definition eines zellularen Automaten ist als "Grundversion" zu betrachten. Es gibt jedoch interessante Varianten, die wir kurz betrachten wollen.
Um im ZR eine spezielle Topologie zu erreichen, brauchen wir den Rahmen der Grundversion nicht zu sprengen. Es genügt, bei der Definition der Randbedingungen die nötige Portion Phantasie zu besitzen. Einen eindimensionalen endlichen ZR kann man ringförmig schließen, indem man die Indizes der Zellen modulo der Anzahl der Zellen rechnet, sodaß die erste Zelle rechte Nachbar der letzten Zelle ist. In ähnlicher Weise kann man einen rechteckigen ZR auf eine Zylinderfläche projizieren, indem man den linken und den rechten Rand als benachbart definiert, oder gar auf die Oberfläche eines Torus, indem man zusätzlich den oberen und den unteren Rand als benachbart definiert. Wenn man den linken und den rechten Rand antiparallel verbindet, erhält der ZR die Topologie eines Möbiusbands. Der Phantasie sind hier keine Grenzen gesetzt.
In der Grundversion gingen wir davon aus, daß beim Fortschreiten vom Zeittakt t zu t+1 die Folgezustände aller Zellen gleichzeitig berechnet werden, wobei die Zustandsüberführungsfunktion die Zustände zum Zeitpunkt t als Eingabe erhält. Diese Vorgehensweise wollen wir "Synchroner Update" nennen. Bei endlichen ZAs ist jedoch auch denkbar, daß die Zustandsüberführungsfunktion sequentiell auf die einzelnen Zellen angewandt wird (wobei wir natürlich eine beliebige Reihenfolge der Zellen vorgeben können). Wir sprechen dabei von "Sequentiellem Update". Es ist auch eine Mischform vorstellbar, in der der ZR in Blöcke eingeteilt wird, wobei die Zellen eines Blocks synchron, die Blöcke selbst jedoch sequentiell neu berechnet werden.
Die Zustandsüberführungsfunktion könnten wir so erweitert denken, daß für die Berechnung des Zustands zum Zeitpunkt t+1 nicht nur der Zustand zum Zeitpunkt t, sondern auch der zu früheren Zeitpunkten bis t-p herangezogen wird. Wir könnten sogar für jede Vergangenheitsgeneration eine eigenes Nachbarschaftsbeziehung festlegen.
Aus der Sicht der theoretischen Informatik stellt sich die Frage nach der Berechnungsmöglichkeiten mit Hilfe zellularer Automaten. Als erstes springt ihre Fähigkeit zur Parallelverarbeitung ins Auge. Das allein aber bedeutet noch nicht, daß sich mit Hilfe zellularer Automaten nichttriviale Probleme lösen lassen. Wenn man sich aber etwas mit den Möglichkeiten von zellularen Automaten vertraut macht, dürfte es nicht überraschen, daß sie sehr wohl hochkomplexe Aufgaben lösen können. Smith bewies bereits 1971 in [Sm71] folgenden Satz:
Jede Turing-Maschine TM kann durch einen eindimensionalen zellularen Automaten simuliert werden.
Auf einen formalen Beweis wollen wir hier verzichten, es ist aber leicht einzusehen, wie das bewerkstelligt werden könnte. Jede Zelle des ZA enspricht einer Zelle auf dem Band der Turing-Maschine, dabei muß im Zustand jeder Zelle das aktuelle Bandsymbol und der interne Zustand des Kopfs der Turing-Maschine sowie ein Flag, ob sich der Kopf der Turing-Maschine gerade auf dieser Zelle befindet, repräsentiert werden. Es ist dann klar, daß die Zustandsüberführungsfunktion des ZA so aus der Zustandsüberführungsfunktion der Turing-Maschine konstruiert werden kann, daß sich der durch dieses Flag simulierte Kopf in gewünschter Weise bewegt und auch die gewünschten Bandsymbole geschrieben werden.
Smith zeigte auch eine andere Möglichkeit zur Simulation, die eine Nachbarschaft von 6 Zellen benötigt und mit nur 1+max (|Q|, |S|) Zuständen auskommt, wobei Q die Zustandsmenge und S das Bandalphabet der Turing-Maschine ist.
Da universelle Turing-Maschinen (das sind Turing-Maschinen, die als Eingabe eine codierte Version einer beliebigen Turing-Maschine erhalten und deren Verhalten simulieren) existieren, folgt unmittelbar, daß auch universelle zellulare Automaten existieren. Da eine universelle Turing-Maschine mit 7 Zuständen und 4 Bandsymbolen existiert [Mi67], existiert daher ein universeller eindimensionaler zellularer Automat mit 8 Zuständen und einer Nachbarschaft von 6 Zellen.
Dieses Ergebnis, so erfreulich es auch aus theoretischer (und vielleicht auch praktischer) Sicht ist, macht jedoch jegliche Hoffnung zunichte, alleine aufgrund des Anfangszustands und der Zustandsüberführungsfunktion ohne Simulation vorherzusagen, wie sich ein zellularer Automat entwickeln wird. Das ergibt sich aus der Unentscheidbarkeit des Halteproblems für Turing-Maschinen.
Das dynamische Verhalten zellularer Automaten kann allgemein als komplex bezeichnet werden. Wolfram [Wo84] schlug aufgrund umfangreicher Simulationen folgende Einteilung eindimensionaler zellularer Automaten vor:
Diese Klassifikation ist empirisch und schwierig anzuwenden. Aufgrund der Fähigkeit zellularer Automaten, Turing-Maschinen zu simulieren, ist es unentscheidbar, ob ein ZA zur Klasse 1 gehört. In der Tradition der Chaostheorie sprechen wir bei periodischen Schleifen, auf die sich die Anfangszustände hinentwickeln, von Attraktoren. Zellulare Automaten können auch in dem Sinn chaotisches Verhalten aufweisen, als daß minimale Veränderungen in der Ausgangskonfiguration in enormen Unterschieden in späteren Generationen resultieren können.
Endlichen ZAs müssen Schleifen aufweisen (d. h. zur Klasse 1 oder 2 gehören), da es nur eine endliche Zahl von Konfigurationen gibt. Falls es für einen ZA mehrere Attraktoren gibt, hat jeder einen gewissen "Einzugsbereich" aus der Menge der möglichen Konfigurationen.
