Zellulärer Automat

frame|rechts|Beispiel für ein raumzeitliches Muster, das sich in einem zellulären Automaten ausbildetDaniel Dennett, (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X

Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich diskreter dynamischer Systeme. Sie bestehen aus einzelnen Zellen, die zu diskreten Zeitpunkten gleichzeitig ihren Zustand ändern. Die Änderung erfolgt für alle Zellen nach den gleichen Regeln. Sie hängt von den Zellzuständen in einer vorgegebenen Nachbarschaft und vom Zustand der Zelle selbst ab. Häufig sind die Zellen in einem regelmäßigen Gitter angeordnet (Gittermodell).

Eigenschaften Ein zellulärer Automat ist durch folgende Größen festgelegt: einen 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

Ähnlich wie bei Monte-Carlo-Simulationen spielen Randbedingungen wie z. B. periodische Randbedingungen eine wichtige Rolle für die Bestimmung der Nachbarn und die Eigenschaften des Modells.

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.TechTarget: cellular automaton

Für einen eindimensionalen zellulären Automat sind 28 = 256 verschiedene Regeln (Überführungsfunktionen) möglich, denn für jeden der 23 = 8 Zustände einer Zelle und ihrer zwei Nachbarzellen (3 benachbarte Zellen) sind unabhängig voneinander 2 neue Zustände möglich.Stanford Encyclopedia of Philosophy: Supplement to Cellular Automata - The 256 RulesWolfram MathWorld: Elementary Cellular Automaton

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 kann. Er beschrieb damit als erster einen Zellularautomaten, der berechnungs- und konstruktionsuniversell ist. Er ist nach von Neumann für Probleme biologischer Organisation, Selbstreproduktion und der Evolution von Komplexität geeignet. 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 vermutete, dass nicht alle zellulären Automaten der Klasse 4 dazu imstande seien, 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.

Wenn die Zustände der Zellen als boolesche Werte dargestellt werden, kann man die Regeln für eindimensionale zelluläre Automaten in einfacher Form darstellen. Ist der Zustand der Zelle mit dem Index zum Zeitpunkt , dann lässt sich der Zustand auf einfache Weise als dreiwertige boolesche Funktion darstellen. Die Parameter sind die Zustände der Zelle und der zwei Nachbarzellen im vorherigen Schritt: .

Für Regel 30, Regel 90 und Regel 110 zum Beispiel erhält man folgende konkrete Überführungsfunktionen:

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, dass man dies im Allgemeinen nicht vorhersagen kann. Aufgrund dieser Erkenntnisse vermutete Stephen Wolfram, dass die zellulären Automaten der Klasse 4 die einzigen seien, 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.Stanford Encyclopedia of Philosophy: Cellular Automata

Muster Zelluläre Automaten erzeugen Muster, die klassifiziert werden können. Im zweidimensionalen Fall sind das zum Beispiel

Raumschiff (Spaceship): Ein Raumschiff taucht nach einer endlichen Anzahl von Zeitschritten an einer anderen Stelle, aber in derselben Ausrichtung wieder auf. Diese Anzahl wird Periode genannt. Der Gleiter (Glider) in Conways Spiel des Lebens ist das kleinste Raumschiff und hat die Periode 4. Kanone (Gun): Eine Kanone hat einen Hauptteil, der sich wie ein Oszillator periodisch wiederholt, und stößt periodisch Raumschiffe aus. Die Periode der Kanone ist ein Vielfaches der Periode der Raumschiffe. Oszillator (Oscillator): Ein Oszillator taucht nach einer endlichen Anzahl von Zeitschritten an derselben Stelle und in derselben Ausrichtung wieder auf. Replikator (Replicator): Ein Replikator erzeugt Kopien von sich selbst, die dieselbe Ausrichtung wie das Original haben. Im eindimensionalen Automaten mit der Regel 90 ist jedes Muster ein Replikator. Der zweidimensionale Automat Highlife bringt verschiedene Arten von Replikatoren hervor. Reflektor (Reflector): Ein Reflektor interagiert mit einem Raumschiff und ändert seine Bewegungsrichtung, ohne sich zu beschädigen. Brüter (Breeder): Ein Brüter ein Muster, das quadratisches Wachstum zeigt, indem es mehrere Kopien eines sekundären Musters erzeugt, von denen jedes dann mehrere Kopien eines tertiären Musters erzeugt. Es gibt vier verschiedene Basistypen von Brütern. Methusalem (Methuselah): Ein Methusalem ist ein kleines Muster aus Zellen, dessen Stabilisierung eine große Anzahl von Zeitschritten erfordert. Martin Gardner definiert sie als Muster aus weniger als 10 Zellen, deren Stabilisierung länger als 50 Zeitschritte dauert. Muster müssen sich irgendwann stabilisieren, um als Methusalem betrachtet zu werden. Stillleben (Still life): Ein Stillleben ist ein Muster, das sich nicht verändert. Es kann als Oszillator mit Periode 1 definiert werden.

Wolframs eindimensionales Universum mini|450px|Wolframs eindimensionales Universum Stephen Wolframs zellulärer Automat ist ein besonders 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 (periodische Randbedingungen).

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. Regeln von Wolfram’s erstem Beispiel Anzahl lebender Nachbarn 0 1 2 3 4 5 Ergebnis Folgegeneration 0 0 1 0 1 0