Zum Inhalt springen

Zellulärer Automat

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 31. Januar 2005 um 01:19 Uhr durch Kotasik (Diskussion | Beiträge). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Zelluläre Automaten (auch: Zellulare Automaten) dienen der Modellierung 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.
Ein Zellularautomat ist durch folgende Größen festgelegt:

  • ein Raum R (Zellraum)
  • eine endliche Nachbarschaft N
  • eine endliche Zustandsmenge Q
  • einer lokalen Überführungsfunktion

Der Zellraum ist in der Regel 1-dimensional oder 2-dimensional. Der Übergang einer Zelle von einem Zustand in den nächsten wird durch Zustandsübergangsregeln definiert, die streng deterministisch oder stochastisch sein können. Die Zustandsübergänge erfolgen für alle Zellen nach der gleichen Überführungsfunktion und gleichzeitig. Die Zellzustände sind wie die Zeitschritte diskret. In der Regel ist die Anzahl der möglichen Zustände klein: Nur wenige Zustandswerte reichen zur Simulation selbst hochkomplexer Systeme aus.
Man unterscheidet 2 verschiedene Nachbarschaften (auch Nachbarschaftsindex genannt):

  • Moore-Nachbarschaft
  • Von-Neumann-Nachbarschaft


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 universellem Berechnungsmodell. Er stellte einen Zellularautomaten vor mit 29 Zuständen vor, der ein gegebenes Muster immer wieder selbst reproduzieren konnte. Er beschrieb damit als erster einen Zellularautomaten, der berechnungs- und kontruktionsuniversell ist.

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


1969 veröffentlicht Konrad Zuse sein Buch "Calculating Space", worin er annimt, dass die Naturgesetze diskreten Regeln folgen und man das gesamte Universum als Ergebnis eines gigantischen Zellularautomaten sei.

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



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 obenstehende Bild enthält drei verschiedene Bildausschnitte.) Die Raumdimension ist endlich aber ohne Enden, denn ihr rechtes und linkes Ende ist 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, welches 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. Sonst existieren keine weiteren Regeln.

Obwohl es im Gegensatz zu Computer-Games 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.

Siehe auch

Musterbildung, Pascalsches Dreieck, Greenberg-Hastings Automat, Räuber-Beute-Modell, Automaten, Chaos, Ordnung, Konrad Zuse (Rechnender Raum), Wireworld


Abgerufen von „https://de.wikipedia.org/w/index.php?title=Zellulärer_Automat&oldid=4553419“