Zellulärer Automat


Zellulärer Automat

Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich 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.

Inhaltsverzeichnis

Beschreibung

Ein Zellularautomat ist durch folgende Größen festgelegt:

  • ein Raum R (Zellularraum)
  • eine endliche Nachbarschaft N
  • eine Zustandsmenge Q
  • eine lokale Überführungsfunktion \delta\colon Q^N \to Q.

Der Zellularraum besitzt eine gewisse Dimensionalität, er ist in der Regel 1- oder 2-dimensional, kann aber durchaus auch höherdimensional sein. Man beschreibt das Aussehen eines Zellularautomaten 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.

Man unterscheidet zwei verschiedene Nachbarschaften (auch Nachbarschaftsindex genannt):

Geschichte der Zellularautomaten

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.

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 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.

Wolframs eindimensionales Universum

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. Die interessanteste ist die „Regel 110“:

Regel 110

neuer Zustand der Zelle 0 1 1 0 1 1 1 0
momentaner Zustand 111 110 101 100 011 010 001 000
Die ersten 200 Entwicklungsschritte (von unten nach oben) von Regel 110, wenn zu Beginn nur eine Zelle voll ist und alle anderen leer sind.
Die ersten 3200 Entwicklungsschritte von Regel 110. Gezeigt ist nur die linke Seite.


Zelluläre Automaten programmieren

Dieses kurze Skript, geschrieben 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, 0 bis 255 eingegeben werden.

import sys
 
if len(sys.argv) != 2 or int(sys.argv[1]) not in range(0,256):
    sys.exit()
 
w = 999
r = s = [0] * w
r[w/2] = 1
z = ""
d = 0
 
for j in range(0,w/2):
    n = (r[0] << 1) + r[1]
    o = ""
    for i in range(1,w):
        o += " 0 " if r[i]==1 else "15 "
    z = z + o + "\n"
    for i in range(2,w):
        n = (n << 1) + r[i]
        if n >= 8: n-=8
        s[i-1] = (int(sys.argv[1]) >> n)%2
    r = s
    d += 1
 
print "P2"
print str(w-1) + " " + str(d)
print "15"
print z

Beispiele für zelluläre Automaten

Siehe auch

Weblinks

 Commons: Cellular automata – Sammlung von Bildern, Videos und Audiodateien

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • zellulärer Automat — zellulärer Automat,   ein Automat, der aus zahlreichen identischen Zellen besteht, die flächig oder seltener in einem räumlichen Gitter angeordnet sind. Die einzelnen Zellen stellen oft eigenständige Automaten dar, die nur wenige Zustände… …   Universal-Lexikon

  • Abstrakter Automat — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Zellularautomat — Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich 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… …   Deutsch Wikipedia

  • Zellulare Automaten — Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich 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… …   Deutsch Wikipedia

  • Zelluläre Automaten — Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich 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… …   Deutsch Wikipedia

  • Game of Life — Figur: Glider Das Spiel des Lebens (engl. Conway s Game of Life) ist ein vom Mathematiker John Horton Conway 1970 entworfenes System zweidimensional angeordneter zellulärer Automaten. Es ist eine einfache und bis heute populäre Umsetzung der… …   Deutsch Wikipedia

  • Analog-Computer — Analogcomputer oder Analogrechner sind Rechner, die Berechnungen auf der Basis zu den Problemstellungen gleichartig wirkender mechanischer oder elektrischer Vorgänge bzw. Abbildungen durchführen. Bei Analogrechnern wird die Eigenschaft ausgenutzt …   Deutsch Wikipedia

  • Analogcomputer — oder Analogrechner sind Rechner, die Berechnungen auf der Basis zu den Problemstellungen gleichartig wirkender mechanischer oder elektrischer Vorgänge bzw. Abbildungen durchführen. Bei Analogrechnern wird die Eigenschaft ausgenutzt, dass es in… …   Deutsch Wikipedia

  • Analoge Prozessorarchitektur — Analogcomputer oder Analogrechner sind Rechner, die Berechnungen auf der Basis zu den Problemstellungen gleichartig wirkender mechanischer oder elektrischer Vorgänge bzw. Abbildungen durchführen. Bei Analogrechnern wird die Eigenschaft ausgenutzt …   Deutsch Wikipedia

  • Agentenbasierte Modellierung — ist eine spezielle, individuen basierte Methode der computergestützten Modellbildung und Simulation, eng verknüpft mit komplexen Systemen, Multiagenten Systemen, evolutionärer Programmierung und zellulären Automaten. Inhaltsverzeichnis 1… …   Deutsch Wikipedia