Zelluläre Automaten

Fredkins Such-Maschinen für komplexe Muster

Zelluläre Automaten sind mathematische Systeme, die aufgrund einfacher Regeln hochkomplexes Verhalten zeigen. Sie können auch als virtuelle Computer aufgefaßt werden, bei denen die Anfangsbedingungen die Strukturen (Daten) und die Programme die Prozesse (Berechnungen) repräsentieren.

Herbert W. Franke: Zelluläre Automaten: Das Lebensspiel und andere Gitterautomaten

Zelluläre Automaten entwickeln sich durch Selbstreproduktion, wobei beim reversiblen Typ dieselben Strukturen immer wiederkehren, während beim irreversiblen Typ immer neue Strukturen entstehen. Der Physiker Stanislaw Ulam entwickelte das Denkmodell der Zellulären Automaten, die sich zunehmend als ideale Modelle für komplexe Systeme erweisen. Demzufolge spielt sogar die Mathematik eine genetische Rolle, da das Leben eine digitale Selbstbeschreibung und eine analoge Wechselwirkung mit der Umgebung besitzt.

Simuliert wurde die Selbstorganisation von Zellpopulationen in den 60er Jahren zum erstenmal durch John von Neumann , der Analogien zwischen Computern und den Gesetzmäßigkeiten der Natur sah und das Konzept der Selbstreproduktion in seine Automatentheorie integrierte. Seine Kernthese war, daß Computer und Menschen unterschiedliche Klassen von Automaten repräsentieren. Zelluläre Automaten sind Systeme von Zellen, die in einfacher Weise miteinander interagieren, jedoch komplexes Verhalten mit folgenden Merkmalen zeigen:

1. 1. Das System wird von einem 1-, 2-, oder 3-dimensionalen Netzwerk aus Zellen geformt, die mit ihren Nachbarn interagieren.
2. 2. Jede Zelle kann eine von m möglichen diskreten Zuständen annehmen.
3. 3. Das System folgt einer konkreten Zeitdynamik, bei denen die Zellen beim Übergang zu neuen Zuständen die Zustände der jeweiligen Nachbarzellen berücksichtigen.

In seinem Buch "Theory of Self-Reproducing Automata" führte von Neumann den Beweis, daß ein sich selbst reproduzierender Automat (universaler Konstrukteur) möglich ist, wenn die Maschine ein gewisses Maß an Komplexität überschreitet. Chris Langton fand heraus, daß Zelluläre Automaten die Fähigkeit zur Selbstreproduktion besitzen, wobei diese eine Reihe von Zuständen durchlaufen. Jede Zelle prüft in jedem Zustand die Aktivität ihrer Nachbarn und interagiert dann gemäß vorgegebener Regeln. Hierbei zeigen diese je nach Anfangsbedingungen typische Evolutionsmuster, die sich nach Stephen Wolfram , einem weiteren Pionier für Zelluläre Automaten, folgendermaßen klassifizieren lassen:

Zellulärer Automat Zielzustand

1. Klasse 1 homogener Gleichgewichtszustand
2. Klasse 2 konstanter oder periodischer Endzustand
3. Klasse 3 chaotischer Endzustand fraktaler Dimension
4. Klasse 4 komplexe Muster als Attraktor

Wie die Zielzustände der obigen Klassifizierung zeigen, führen uns Zelluläre Automaten direkt zu den Forschungsbereichen der Mustererkennung, der Selbstorganisation, des Chaos, der Fraktale und der Endophysik. Zelluläre Automaten der Klasse 3 liefern nach Wolfram Erklärungsmodelle für die Evolution des Universums, da deren Verhalten ähnlich wie bei dissipativen Systemen irreversibel, d. h. zeitlich nicht symmetrisch ist. Langton zufolge ruft der Übergangsbereich zwischen Chaos und Ordnung das Maximum an Informationserzeugung des zugrunde liegenden Systems hervor. Die Klasse 4 der Zellulären Automaten bringt jedoch noch komplexeres Verhalten hervor, wobei Wolfram annimmt, daß diese zu universelle Berechnungen ("universal computation") fähig sind, d.h. das Verhalten jedes anderen Computersystems simulieren können. Damit würden Zelluläre Automaten den einfachsten universellen Computer repräsentieren. Es scheint möglich, daß bei Wahl geeigneter Anfangsbedingungen auch Zelluläre Automaten der Klasse 3 universelle Computer darstellen.

Fredkin (ein Schüler von Feynmann) setzte sich ebenso wie Toffoli vor allem mit Automaten vom reversiblen Typ auseinander und erarbeitete hierzu eine Hypothese, die als Billardkugelmodell bekannt wurde. Während Boltzmann die Welt als eine gewöhnliche Differentialgleichung, d.h. eine molekulardynamische Simulation, betrachtet, Einstein diese durch eine partielle Differentialgleichung repräsentiert sieht, ist diese laut Fredkin ein Zellulärer Automat, der aus einem spezifischen Code besteht. 1982 beschrieb Fredkin das erste explizit computersimulierbare Modell-Universum - einen Zellulären Automaten vom reversiblen Typ. Er entdeckte, daß jeder irreversible Zelluläre Automat in einen größeren reversiblen Automaten (mit dissipativen Gleichungen) eingebettet werden kann und daß sich selbst organisierende Automaten diesen Typs in der Lage sind, die Naturgesetze abzubilden.

Die moderne Gehirnphysiologie und Informatik nutzt die Theorie der Selbstorganisation für die Erklärung jener Abläufe im Gehirn, bei denen sich Neuronen vernetzen und durch Phasenübergänge neue Muster erzeugen. Zelluläre Automaten können hierbei als eine vereinfachte Vorstufe Neuronaler Netzwerke betrachtet werden, die durch Konnektionismus und Parallelverarbeitung gekennzeichnet sind. Zelluläre Automaten und Fraktale scheinen dieselben deterministischen Wurzeln haben, die auch bei der Erzeugung von Chaos eine Rolle spielen. Bei der Berechnung von reversiblen Zellulären Automaten zeigte sich deterministisch chaotisches Verhalten. Auch wenn man die Ergebnisse von Berechnungen nicht vorhersagen kann, so können Simulationen am Computer zu neuen Erkenntnissen führen, wie etwa B. Wolley meint: "More generally, fractals, cellular automata, chaos, catastrophe and a host of other mathematical developments seem to show that the world, nature and even life itself may, for all messiness and complexity, be computable."