Zellulärer Automat

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

Eigenschaften 
Ein zellulärer Automat ist durch folgende Größen festgelegt:
 ein Raum  (Zellularraum)
 eine endliche Nachbarschaft 
 eine Zustandsmenge 
 eine lokale Überführungsfunktion .

Der Zellularraum besitzt eine gewisse Dimensionalität, er ist in der Regel ein- oder zweidimensional, kann aber durchaus auch höherdimensional sein. Man beschreibt das Aussehen eines zellulären Automaten durch eine globale Konfiguration, welche eine Abbildung aus dem Zellularraum 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 derselben Ü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.

Bei zweidimensionalen zellulären Automaten unterscheidet man zwei verschiedene Nachbarschaften:
 Moore-Nachbarschaft
 Von-Neumann-Nachbarschaft
Der einfachste zelluläre Automat  ist eindimensional, mit Zellen auf einer geraden Linie, wobei jede Zelle nur zwei mögliche Zustände haben kann, z. B. schwarz und weiß. In einem zweidimensionalen Raum sind Quadrate, Sechsecke und Würfel übliche Zellformen. Theoretisch kann ein zellulärer Automat beliebig viele Dimensionen haben und jede Zelle kann beliebig viele mögliche Zustände haben. Der Zustand jeder Zelle ändert sich in diskreten Schritten und in regelmäßigen Zeitintervallen. Dieser Zustand hängt zu jedem Zeitpunkt ab von

 seinem eigenen Zustand im vorherigen Schritt
 den Zuständen seiner unmittelbaren Nachbarn im vorherigen Schritt

Wenn eine grafische Darstellung eines solchen Automaten betrachtet wird, sieht er wie ein gerastertes animiertes Objekt aus.

Geschichte 
Zellularautomaten wurden um 1940 von Stanislaw Ulam in Los Alamos vorgestellt. John von Neumann, ein damaliger Kollege Ulams, 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. Er ist nach von Neumann geeignet für Probleme biologischer Organisation, Selbstreproduktion und der Evolution von Komplexität. Damit ist der Zellularautomat auch eine wichtige Grundlage für künstliches Leben.

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, Abschnitt „Beispiel: Zellulärer Automat“ genauer beschrieben.

In den 1970er Jahren erlangte John Horton Conways Game of Life Berühmtheit.

1969 veröffentlichte Konrad Zuse sein Buch „Rechnender Raum“, worin er annimmt, dass die Naturgesetze diskreten Regeln folgen und das gesamte Geschehen im Universum das Ergebnis der Arbeit eines gigantischen Zellularautomaten sei.

1983 veröffentlichte Stephen Wolfram eine Reihe von grundlegenden Arbeiten zu Zellularautomaten und 2002 das Buch A New Kind of Science.

Klassifikation 
Stephen Wolfram definiert in A New Kind of Science und in etlichen Arbeiten aus der Mitte der 1980er Jahre vier Klassen, in die man die zellulären Automaten und ihre Überführungsfunktionen je nach ihrem Verhalten unterteilen kann. Frühere Autoren versuchten lediglich, die Art der Muster für bestimmte Vorschriften zu ermitteln.

Dem Aufwand nach geordnet waren dies die Klassen:
 Klasse 1: Fast alle ursprünglichen Muster entwickeln sich schnell zu einem stabilen und homogenen Zustand. Dadurch verschwindet jede Zufälligkeit in den ersten Mustern.
 Klasse 2: Fast alle ursprünglichen Muster entwickeln sich schnell in stabile oder oszillierende Strukturen. Einige Zufälligkeiten der ersten Muster kann man herausfiltern, jedoch können manche zurückbleiben. Lokale Änderungen am ursprünglichen Muster neigen dazu lokal zu bleiben.
 Klasse 3: Fast alle ursprünglichen Muster entwickeln sich pseudozufällig oder chaotisch. Jede stabile Struktur kann schnell durch Rauschen zerstört werden. Lokale Änderungen am ursprünglichen Muster neigen dazu, sich bis ins Unendliche auszubreiten.
 Klasse 4: Fast alle ursprünglichen Muster entwickeln sich in Strukturen, die vielschichtig und interessant interagieren. Endlich informative Ursprungsmuster können, wie in Klasse 2 üblich, stabile oder oszillierende Strukturen ergeben, aber die Anzahl der erforderlichen Schritte, um diesen Zustand zu erreichen, kann selbst für einfache Muster sehr groß sein. Lokale Änderungen am ursprünglichen Muster können sich bis ins Unendliche verbreiten.
Stephen Wolfram hat vermutet, dass nicht alle zellulären Automaten der Klasse 4 dazu imstande sind, universelle Berechnungen auszuführen. Die Universalität hat sich vor allem für die Regel 110 und Conways Spiel des Lebens bestätigt.

Zelluläre Automaten der Klasse 4 haben besondere Eigenschaften. Aus Regel 110 entstehen regelmäßige Muster, die aber nicht so regelmäßig sind wie in Regel 108, sowie ein chaotisches Verhalten, das aber nicht so chaotisch ist wie in Regel 90.

Eine grundlegende Eigenschaft, die ein zellulärer Automaten der Klasse 4 haben muss, ist, dass die Überführungsfunktion lokale, stabile und nichtperiodische Konfigurationen von Zellen hervorbringt, die ihre Form erhalten können. Diese Konfigurationen können als Codierungspakete mit Informationen angesehen werden, die über die Zeit erhalten bleiben und sich von einem Ort zum anderen bewegen. Diese Informationen können sich zeitlich und räumlich ausbreiten, ohne zu zerfallen.

Es ist es ein wichtiges Merkmal der universellen Berechnung, ob ein bestimmter Algorithmus bei einer bestimmten Eingabe anhält oder nicht. Die Unentscheidbarkeit des Halteproblems bedeutet, das man dies im Allgemeinen nicht vorhersagen kann. Aufgrund diesen Erkenntnissen vermutete Stephen Wolfram, dass die zellulären Automaten der Klasse 4 die einzigen sind, die zur universellen Berechnung in der Lage sind. Wenn man die anfängliche Konfiguration eines solchen Automaten als Eingabedaten interpretiert, kann dieser Automat jede berechenbare Funktion bewerten und eine universelle Turingmaschine emulieren.

Wolframs eindimensionales Universum 

Stephen Wolframs zellulärer Automat ist ein besonders schönes und einfaches Modell-Universum. Es besteht aus nur einer Raum- und einer Zeitdimension. Im Bild ist die Raumdimension waagerecht eingezeichnet und die Zeitdimension verläuft senkrecht nach unten. (Das Bild enthält drei verschiedene Bildausschnitte.) Die Raumdimension ist endlich, aber unbegrenzt, 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 Nahwirkung 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 Modelluniversum 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 Strukturen existieren sowohl ortsfeste als auch bewegliche Arten. Die maximale Austauschgeschwindigkeit dieses Universums kann nur zwei Raumeinheiten je 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 8 Regelelemente. Ein Beispiel dazu steht weiter unten. Insgesamt gibt es 256 solcher Regeln. Selbst unter diesen noch einfacheren Regeln zeigen einige eine erstaunliche Komplexität. Eine der interessantesten ist die „Regel 110“:

Regel 110

Siehe auch: Regel 30

Programmierung 
Dieses Codebeispiel in der Programmiersprache Python kann alle 256 eindimensionalen zellulären Automaten simulieren und erzeugt als Ausgabe ein Bild im Grafikformat Portable Graymap (.pgm). Beim Aufruf muss die gewünschte Regelnummer aus dem Intervall von 0 bis 255 eingegeben werden.

from optparse import OptionParser

if __name__=="__main__":
    parser = OptionParser()
    parser.add_option("-r", dest="rule", help="Rule number 0..255.")
    parser.add_option("-f", dest="file_path", help="File path")

    (option, args) = parser.parse_args()
    rule = option.rule
    file_path = option.file_path

    w = 1000
    r = s = [0] * w
    r[int(w/2)] = 1
    z = []
    d = 0

    for j in range(0, int(w/2)):
        n = (r[0] << 1) + r[1]
        o = ""
        for i in range(1, w):
            o += " 0 " if r[i]==1 else "15 "
        z.append(o + "\n")
        for i in range(2,w):
            n = (n << 1) + r[i]
            if n >= 8: n-=8
            s[i-1] = (int(rule) >> n)%2
        r = s
        d += 1

    f = open(file_path,'w')
    f.write("P2\n")
    f.write(str(w-1) + " " + str(d) + "\n")
    f.write("15\n")
    for i in range(len(z)-1, 0, -1):
        f.write(z[i])
    f.close()

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.
 Langton-Schleifen simulieren zur Selbstreplikation fähige Organismen in einem zellulären Automaten.
 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.
 Das FHP-Modell dient der Simulation von Gasen und Flüssigkeiten.
 Ein sehr einfacher zellulärer Automat ist der ASEP.

Garten von Eden und Zwillinge 
Der Garten von Eden ist eine Konfiguration (Muster) des zellulären Automaten, die keine Vorläufer hat. Sie enthält mindestens eine endliche Konfiguration, die ebenfalls keine Vorläufer hat, einen Waisen (englisch: orphan). Ein Zwilling einer endlichen Konfiguration ist eine andere endliche Konfiguration, die die gleichen zukünftigen Muster hat. Ein zellulärer Automat ist injektiv, falls unterschiedliche Teile des Musters auch in Zukunft unterschiedlich bleiben, lokal injektiv, falls keine Zwillinge vorhanden sind, und surjektiv, wenn jede Konfiguration einen Vorläufer hat.

Edward F. Moore (1962) und John Myhill (1963) bewiesen den Garten-von-Eden-Satz in der  Theorie zellulärer Automaten: Ein zellulärer Automat im euklidischen Raum ist lokal injektiv genau dann, wenn er surjektiv ist. Das lässt sich auch so ausdrücken, dass zelluläre Automaten genau dann einen Garten von Eden haben, wenn sie keine Zwillinge haben. Dabei bewies Moore einen Teil der Äquivalenz (Automaten mit Zwillingen haben Waisen), Myhill die Umkehrung (ein Automat mit Waisen hat auch Zwillinge).

Siehe auch 
 Ameise (Turingmaschine)
 Emergenz
 Evakuierungssimulation
 Künstliches Leben
 Musterbildung
 Räuber-Beute-Modell
 Turingmaschine
 Wator
 Wireworld
 Pascalsches Dreieck kann mit zellulären Automaten simuliert werden
 Endlicher Automat

Literatur 
 Melanie Mitchell: Complexity. A Guided Tour. Oxford University Press, Oxford u. a. 2009, ISBN 978-0-19-512441-5, .
 Klaus Mainzer, Leon Chua: The Universe as Automaton. From Simplicity and Symmetry to Complexity. Springer, Heidelberg u. a. 2012, ISBN 978-3-642-23476-7, .

Weblinks 

Sekundärliteratur
 
 Jürgen Schmidhuber: Webseite über Konrad Zuses Theorie des Rechnenden Raumes (Auszug aus Elektronische Datenverarbeitung 8 (1967) S. 336–344)
Visualisierungen und Implementierungen
 Wolfram’s 1-dimensionales Universum als C#-Implementierung
 2.5d zellulärer Automat (3d game of life) mit Dokumentation und Quellcode
  als Java-Applet
 Zyklischer Zellulärer Automat als Java-Applet
 Zellomat3D – 3D-zellulärer Automat
 NetLogo – Agenten-basierte Modellierungs- und Simulationsumgebung
 Random Design – Zufallserzeugte zelluläre Automaten
 Ordnungsprozess in einem Monte-Carlo-basierten zellulären Automat (Youtube-Video)
 Otomata – Sequencer als interaktiver zellulärer Automat
 Cafun – Freeware Java Implementierung zur Simulation und Visualisierung zellulärer Automaten mit XML-basierter Konfiguration
 Golly – Simulation zahlreicher verschiedener zellulärer Automaten mit Beispielen

Einzelnachweise 

Dynamisches System
Automatentheorie
Wikipedia:Artikel mit Video