Ein zellularer Automat besteht aus einem regelmäßigen Gitter von "Zellen", die jeweils einen "Zustand" enthalten, der aus einer endlichen Menge ausgewählt wurde und sich im Laufe der Zeit ändern kann. Der Zustand einer Zelle zum Zeitpunkt t + 1 ist eine Funktion des Zustands zum Zeitpunkt t einer endlichen Anzahl von Zellen, die als "Nachbarschaft" bezeichnet wird. Mit jeder neuen Zeiteinheit werden dieselben Regeln gleichzeitig auf alle Zellen des Gitters angewendet, wodurch eine neue „Generation“ von Zellen erzeugt wird, die vollständig von der vorherigen Generation abhängt.
Zellularautomaten, die in Mathematik und theoretischer Informatik studiert haben , sind sowohl ein diskretes dynamisches Systemmodell als auch ein Rechenmodell . Das zelluläre Automatenmodell ist bemerkenswert für den Unterschied zwischen der Einfachheit seiner Definition und der Komplexität, die bestimmte makroskopische Verhaltensweisen erreichen können : Die zeitliche Entwicklung aller Zellen wird nicht (einfach) auf die lokale Regel reduziert , die das System definiert. Als solches ist es eines der Standardmodelle bei der Untersuchung komplexer Systeme .
Der einfachste nicht triviale zellulare Automat, den wir uns vorstellen können, besteht aus einem eindimensionalen Gitter von Zellen, das nur zwei Zustände ("0" oder "1") annehmen kann, wobei für jede Zelle eine Nachbarschaft daraus besteht und die zwei angrenzenden Zellen.
Jede der Zellen kann zwei Zustände annehmen, es gibt 2 3 = 8 mögliche Konfigurationen (oder Muster) einer solchen Nachbarschaft. Damit der zellulare Automat funktioniert, muss aus jedem dieser Gründe definiert werden, wie der Zustand in der nächsten Generation einer Zelle sein muss. Es gibt 2 8 = 256 verschiedene Möglichkeiten, dies zu tun, also 256 verschiedene zellulare Automaten dieses Typs.
Die Automaten dieser Familie sollen "elementar" sein. Sie werden häufig durch eine ganze Zahl zwischen 0 und 255 bezeichnet, deren binäre Darstellung die Folge von Zuständen ist, die der Automat in den aufeinanderfolgenden Mustern 111, 110, 101 usw. einnimmt.
Betrachten wir als Beispiel den in der folgenden Tabelle definierten zellularen Automaten, der die Evolutionsregel angibt:
Anfangsgrund ( t ) | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Nächster Wert der zentralen Zelle ( t +1) | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Das bedeutet, wenn beispielsweise bei einer gegebenen Zeit t , ist eine Zelle im Zustand „1“ ist , seine linken Nachbarn im Zustand „1“ und ihr rechter Nachbar im Zustand „0“ (Spalte 2 der Tabelle), zum Zeitpunkt t + 1 wird es im Zustand "0" sein.
Wenn wir von einem anfänglichen Gitter ausgehen, in dem sich alle Zellen bis auf eine im Zustand "0" befinden, erhalten wir:
Dabei ist jede Zeile das Ergebnis der vorherigen Zeile.
Konventionell wird diese Regel "Regel 30" genannt, da 30 in Dezimalzahl 00011110 in Binärform geschrieben ist und 00011110 die zweite Zeile der obigen Tabelle ist, die die Evolutionsregel beschreibt.
Das " Spiel des Lebens " ist ein zweidimensionaler zellularer Automat, bei dem jede Zelle zwei Werte annehmen kann ("0" oder "1", aber wir sprechen eher von "lebendig" oder "tot") und wo sich ihr zukünftiger Zustand befindet bestimmt durch seinen aktuellen Zustand und durch die Anzahl der lebenden Zellen unter den acht ihn umgebenden:
Diese scheinbar einfachen Regeln bringen eine große Komplexität mit sich.
Nach dem gleichen Prinzip können wir uns eine große Anzahl von Regeln vorstellen, indem wir die Geburts- oder Überlebensschwellen variieren oder zusätzliche Zustände usw. hinzufügen. Unter diesen Variationen können wir zitieren:
Um die Zustandsänderungen einer Zelle zu bestimmen, berücksichtigen einige nur die unmittelbaren Nachbarn der betrachteten Box, andere berücksichtigen auch den Zustand benachbarter Zellen innerhalb eines Radius von zwei Boxen oder sogar mehr. Andere messen bestimmten Boxen in der Nachbarschaft ein größeres Gewicht bei als anderen ( WeightedLife ).
Die möglichen Regeln für die Definition eines zellularen Automaten sind sehr zahlreich, selbst bei einer kleinen Anzahl von Zuständen und einer kleinen Nachbarschaft :
2 Staaten | 3 Staaten | 4 Staaten | 5 Staaten | |
---|---|---|---|---|
2 Nachbarn | 16 | 19 683 | 4,294,967,296 | |
3 Nachbarn | 256 | 7 625 597 484 987 | ||
4 Nachbarn | 65.536 | |||
5 Nachbarn | 4,294,967,296 | |||
6 Nachbarn |
Das Modell zellulärer Automaten bietet daher ein immenses Forschungsfeld. Es ist nicht schwierig, einen Simulator für zellulare Automaten zu programmieren, und das Web ist voll von mehr oder weniger vollendeten Errungenschaften. Die Website von Mirek Wojtowicz bietet beispielsweise Simulationssoftware und eine sehr umfangreiche Beispielgalerie: Mirek's Cellebration . Ein weiteres interessantes Simulatorbeispiel ist Golly . Es ist hauptsächlich dem Spiel des Lebens gewidmet und für diesen Automaten optimiert, indem insbesondere Quadtree in Kombination mit Hash verwendet wird .
In den 1940er Jahren war Stanislaw Ulam Studium Kristallwachstum in dem Los Alamos National Laboratory , Modellierung es auf einem Raster. Zur gleichen Zeit arbeitete John von Neumann , Ulams Kollege in Los Alamos, an selbstreplizierenden Systemen und hatte Schwierigkeiten, sein ursprüngliches Modell eines Roboters zu erklären, der sich aus einer Reihe von abgetrennten Teilen kopieren würde. Ulam schlug vor, sich von seiner Arbeit inspirieren zu lassen, was von Neumann dazu veranlasste, ein abstraktes mathematisches Modell für sein Problem zu entwerfen. Das Ergebnis war der "Kopierer und universelle Konstruktor " ( universeller Konstruktor und Kopie auf Englisch), der erste zellulare Automat: Er basierte auf einem zweidimensionalen Gitter, in dem jede Zelle 29 Zustände annehmen konnte. Von Neumann konstruierte dort ein spezielles Muster und zeigte, dass er endlos Kopien von sich selbst produzieren konnte.
Im Jahr 1969 Gustav Arnold Hedlund veröffentlicht Endomorphismen und Automorphismen des Shift - Dynamical Systems , eine Monographie von etwa 60 Seiten , die auf dem Gebiet der Arbeits 10 Jahren Forschung durch eine Gemeinschaft synthetisiert symbolische Dynamik (ein Zweig der Studie von dynamischen Systemen in den Bereichen Mathematik, insbesondere von M. Morse und GA Hedlund gegründet). Diese Veröffentlichung bildet die mathematische Grundlage für die Untersuchung zellulärer Automaten als bestimmte dynamische Systeme.
Auch im Jahr 1969 Konrad Zuse veröffentlicht Rechnender Raum ( „When Raum Errechnet“) , in dem er vermutet , dass die physikalischen Gesetze waren diskret und dass das Universum war das Ergebnis eines gigantischen zellulären Automaten.
In den 1970er Jahren erzielte ein zweidimensionaler zellularer Automat mit zwei Zuständen , das von John Conway erfundene „ Spiel des Lebens “ , große Erfolge, insbesondere in der aufstrebenden Computergemeinschaft. Es wurde von Martin Gardner in einem Artikel in Scientific American populär gemacht .
1983 veröffentlichte Stephen Wolfram den ersten einer Reihe von Veröffentlichungen, in denen er systematisch eine Art sehr einfacher zellularer Automaten analysierte. Die Komplexität ihres Verhaltens, hervorgerufen durch elementare Regeln, ließ ihn vermuten, dass ähnliche Mechanismen komplexe physikalische Phänomene erklären könnten, Ideen, die er in seinem 2002 veröffentlichten Buch A New Kind of Science entwickelte .
Wenn die Popularität des Modells zellulärer Automaten größtenteils auf einem experimentellen Ansatz beruht, wurde es von Von Neumann von Anfang an als mathematisches Objekt betrachtet . Die meisten formalen Arbeiten an zellularen Automaten verwenden die folgende Definition, obwohl das Modell viele interessante Verallgemeinerungen und Variationen zulässt .
Ein zellularer Automat ist ein -uplet, bei dem:
Die Zuordnung eines Zustands zu jeder Zelle des Netzwerks wird dann als Konfiguration bezeichnet : Eine Konfiguration ist ein Element von , dh eine Funktion von in .
Mit dieser endlichen und lokalen Beschreibung verbinden wir die globale Funktion der Evolution des Automaten , die auf die Konfigurationen einwirkt und die für jede Konfiguration (wo ) definiert ist.
Zelluläre Automaten werden seit den 1960er Jahren mit der Arbeit von GA Hedlund als dynamische Systeme untersucht . Wenn die Größe und das Alphabet angehängt sind, können Raumkonfigurationen der Metrik von Cantor durch den durch definierten Abstand bereitgestellt werden
Die Menge der zellulären Automaten von Alphabet und Dimension wird dann durch das Curtis-Hedlund-Lyondon-Theorem charakterisiert: ist die globale Funktion eines solchen zellularen Automaten genau dann, wenn es sich um eine kontinuierliche Funktion handelt, die mit den Verschiebungsfunktionen pendelt (jede Position in das Zellenarray entspricht einer Verschiebungsfunktion ).
Von dort aus können zelluläre Automaten mit allen Werkzeugen der Theorie der klassischen dynamischen Systeme , der Chaostheorie und der Ergodentheorie untersucht werden , wenn wir den Raum der Konfigurationen eines Maßes ausstatten .
Dieser Zweig der zellulären Automatentheorie bleibt weit offen und ist immer noch Gegenstand der Forschung (siehe hier für ein Beispiel einer wichtigen ungelösten Frage bis heute).
Zelluläre Automaten können sowohl als diskrete dynamische Systeme als auch als Computersysteme betrachtet werden . Somit ist jeder Automat in der Lage, bestimmte Berechnungen durchzuführen oder bestimmte dynamische Verhaltensweisen aufzuweisen. Unabhängig davon, ob einer den einen oder den anderen Standpunkt einnimmt, kann man dieselbe Frage stellen: Gibt es einen Automaten , der in der Lage ist, alles zu tun, was zellulare Automaten können? Ein solcher Automat soll dann universell sein .
Der Begriff der Universalität entspricht einer sehr einfachen und sehr allgemeinen Idee, aber wir müssen darauf achten, dass gemäß der Bedeutung, die wir hinter den Ausdruck "fähig" setzen, die universellen Automaten nicht gleich sind. Wir können zwei Arten von Begriffen der Universalität für zelluläre Automaten unterscheiden: Turing-Universalität, die mit der Fähigkeit zur Berechnung verbunden ist, und intrinsische Universalität, die mit der Fähigkeit verbunden ist, bestimmte dynamische Verhaltensweisen zu erzeugen.
Die bemerkenswerte Tatsache ist, dass es für jeden dieser Begriffe universelle Automaten gibt. Es sollte auch beachtet werden, dass der Begriff der intrinsischen Universalität stärker ist als der der Turing-Universalität: In der Tat kann ein Automat, der alle Automaten simulieren kann, ohne auf Details einzugehen, insbesondere einen Turing-Universal-Automaten simulieren und daher alle Turing-Berechnungen durchführen. Im Gegensatz dazu gibt es Turing-universelle zellulare Automaten, die nicht von Natur aus universell sind.
Turing UniversalitätTuring Universality ist eine Anpassung an zelluläre Universalitätsautomaten zur Berechnung . Wir können diesen Begriff als die Fähigkeit eines Automaten definieren, eine universelle Turingmaschine zu simulieren. Diese Möglichkeit, eine Turing-Maschine mit einem zellularen Automaten zu simulieren, ist sehr einfach und aus der Arbeit von John von Neumann bekannt . Es gibt verschiedene Möglichkeiten, dies zu formalisieren, und die folgende ist eine der einfachsten. Wenn es sich um eine Turing-Maschine handelt, die mit einem Bandalphabet und einer Reihe von Zuständen arbeitet , können wir einen zellularen Automaten definieren , der Folgendes simulieren kann :
Wir stoßen häufig auf eine allgemeinere (aber informellere) Bedeutung der Turing-Universalität: Ein zellularer Automat ist Turing-universell, wenn er ein Turing-vollständiges Berechnungssystem simulieren kann . Der Begriff simulieren wird selten in einem allgemeinen Rahmen formalisiert. Der wichtige Punkt ist, dass die Umwandlung der Ein- / Ausgänge des simulierten Systems in Ein- / Ausgänge des Simulators einfach bleibt: Ohne diese Bedingung erhalten wir aufgrund der Automaten, die nichts tun ( z. B. Identität ) , einen Begriff von keinem Interesse universell dank Eingabe / Ausgabe-Transformationen, die die gesamte Berechnung für sie durchführen.
EigenuniversalitätEin an sich universeller zellularer Automat ist ein Automat, der in der Lage ist, das Verhalten eines zellularen Automaten derselben Dimension Schritt für Schritt zu simulieren . Insbesondere basiert die Idee der schrittweisen Simulation auf den folgenden Prinzipien:
So kann das Spiel des Lebens beispielsweise Schritt für Schritt den Automaten mit zwei Zuständen (schwarz und rot) simulieren , der eine einfache Verschiebung von Zuständen nach Südosten durchführt:
Um das Verhalten einer bestimmten Anfangskonfiguration zu simulieren , reicht es daher aus, eine Konfiguration des Lebensspiels zu erstellen, bei der jede Gruppe entweder mit toten Zellen oder mit einem Segelflugzeug gefüllt ist, abhängig vom Zustand der Zelle, in der sie übereinstimmt .
Es ist bemerkenswert, dass mit diesem sehr einfachen Simulationsprinzip einige Automaten jeden zellularen Automaten aus jeder Konfiguration simulieren können: Dies ist beim Spiel des Lebens der Fall, wie im nächsten Abschnitt erläutert . Um Automaten mit immer mehr Zuständen zu simulieren, verwendet ein an sich universeller Automat natürlich immer größere Gruppen von Zellen. In der Tat gibt es bei einer festgelegten Gruppe von Zellen nur eine begrenzte Anzahl möglicher Simulationen. Wenn wir also eine Entwicklung des Spiels des Lebens auf einem Bildschirm beobachten (wie groß er auch sein mag), sehen wir nicht alle Verhaltensweisen, die das Spiel des Lebens simulieren kann. Dennoch ist dieser Automat in der Lage, alle Verhaltensweisen eines zellularen Automaten zu erzeugen.
BeispieleHistorisch gesehen ist der erste zelluläre Automat, der mit einer Eigenschaft der Universalität konstruiert wurde (in diesem Fall Turing), der universelle Konstruktor von John von Neumann : Es handelt sich um einen Automaten der Dimension 2 mit 29 Zuständen, der sich darüber hinaus selbst replizieren kann.
In Bezug auf den Begriff der intrinsischen Universalität mussten wir bis in die 1970er Jahre mit der Arbeit von ER Banks warten, die einen zellularen Automaten der Dimension 2 mit 2 Zuständen und 5 Nachbarn vorschlugen. Es bietet auch einen an sich universellen eindimensionalen Automaten mit 5 Zuständen, dessen Nachbarschaft jedoch enorm ist.
Das bekannteste Beispiel für einen Universalautomaten ist sicherlich das Spiel des Lebens . Es wurde in dem Buch Winning Ways for your Mathematical Plays als Turing-universal erwiesen . Der Beweis besteht aus Bauteilen von Konfigurationen, die zusammengebaut werden können und allen Komponenten entsprechen, die für die Herstellung von Logikschaltungen erforderlich sind (Drähte, Kreuzungen von Drähten, Vervielfältigung, Logikgatter usw.). Eine vollständige Konstruktion einer Turingmaschine im Spiel des Lebens finden Sie auf Paul Rendells Website . Aus den gleichen Ideen heraus hat sich das Spiel des Lebens in jüngerer Zeit als an sich universell erwiesen.
Für Dimension 1 hat kürzlich ein Durchbruch in Bezug auf die Turing-Universalität stattgefunden: Herr Cook hat bewiesen, dass der elementare zelluläre Automat Nummer 110 Turing-universal ist. Er präsentierte seine Ideen bereits 1998 auf der CA98- Konferenz , aber dieses Ergebnis wurde (teilweise) erst 2002 durch A New Kind of Science von S. Wolfram schriftlich verbreitet . Tatsächlich war Herr Cook bei Wolfram Research angestellt , um an dem Buch A New Kind of Science zu arbeiten, und seine Arbeit wurde nach einer Klage aufgrund einer Geheimhaltungsvereinbarung nicht in den Akten von CA98 veröffentlicht . Der vollständige Beweis für Dr. Cooks Ergebnis wurde schließlich 2004 in einer wissenschaftlichen Zeitschrift veröffentlicht.
Andererseits wissen wir heute noch nicht, ob der Automat 110 an sich universell ist oder nicht. Der kleinste eindimensionale Automat mit einer Nachbarschaft von 3 Zellen, der sich bisher als an sich universell erwiesen hat, hat 4 Zustände.
Im Allgemeinen ist es äußerst schwierig, das Gesamtverhalten eines zellularen Automaten durch Untersuchung seiner lokalen Übergangsregel zu bestimmen. Dies führt zu Unentscheidbarkeitsergebnissen, die sich auf die einfachsten Eigenschaften auswirken. In diesem Bereich können wir die Arbeit von Jarkko Kari zitieren , der durch geschickte Verwendung der bereits auf Fliesen bekannten Ergebnisse gezeigt hat, dass die folgenden Probleme unentscheidbar waren:
Die Tatsache, dass zellulare Automaten jede Turing-Maschine simulieren können , führt auch zu unentscheidbaren Problemen anderer Art. Beispielsweise sind für einige zellulare Automaten die folgenden Probleme ebenfalls unentscheidbar :
Wie oben erläutert, sind die lokalen Regeln von Zellularautomaten für eine erschöpfende Untersuchung zu zahlreich, und die Vorhersage des Verhaltens gemäß der lokalen Regel ist im Allgemeinen ein sehr schwieriges Problem. Aus diesem Grund war das Studium zellulärer Automaten häufig auf bestimmte Familien beschränkt, entweder weil sie sich leichter für Analysen eignen oder weil sie einer interessanten Eigenschaft entsprechen.
Ein zellulären Automaten ist reversibel , wenn es einen zellulären Automaten existiert wie die beiden globalen Funktionen der Evolution und sind das Gegenteil von einander: die Identitätsfunktion. Intuitiv geht "zurück in die Zeit" der Evolution von und umgekehrt "geht zurück in die Zeit" der Evolution von . Nach dem Satz von Hedlund können wir reversible zelluläre Automaten als solche charakterisieren, deren globale Funktion bijektiv ist .
Diese Klasse wurde sehr genau untersucht, insbesondere weil sie ein Modell liefert, das sich der realen physikalischen Welt nähert und im mikroskopischen Maßstab reversibel sein soll (siehe zu diesem Thema den Artikel über Reversibilität und Irreversibilität in der Thermodynamik ). T. Toffoli und N. Margolus gehören zu den ersten, die sich speziell für reversible zelluläre Automaten interessieren. Das Interesse liegt auch in der Suche nach reversiblen Berechnungssystemen , die nach dem Landauer-Prinzip weniger Energie verbrauchen sollen . Es ist nun erwiesen, dass bestimmte reversible zelluläre Automaten universelles Turing sind (Arbeit von Kenichi Morita).
AnerkennungEs ist algorithmisch unmöglich, reversible zellulare Automaten von solchen zu unterscheiden, bei denen die Dimension nicht größer als 2 ist. Andererseits gibt es in Dimension 1 einen sehr effizienten Algorithmus.
Eine andere Möglichkeit, diesen Unterschied zwischen Dimension 1 und größeren Dimensionen darzustellen, ist wie folgt: Die Größe der Nachbarschaft der Umkehrung eines Automaten kann nicht rekursiv gemäß der Größe der Nachbarschaft begrenzt werden, wenn die Dimension 2 oder mehr beträgt, während dies der Fall ist in Dimension 1 polynomiell begrenzt (ein aktuelles Ergebnis zeigt sogar, dass die Grenze linear ist ).
BeispieleEs ist einfach, reversible zellulare Automaten zu konstruieren. Hierfür gibt es verschiedene Konstruktionsformen.
Zelluläre Automaten sind im Allgemeinen dynamische nichtlineare Systeme , was ihre Untersuchung mit herkömmlichen Werkzeugen schwierig macht. Diese allgemeine Wahrheit hindert jedoch bestimmte zelluläre Automaten nicht daran , eine mehr oder weniger strenge Form der Linearität zu besitzen.
DefinitionFormal wird ein Alphabet-Automat als linear bezeichnet, wenn wir ein Gruppengesetz wie das folgende bereitstellen können :
In diesem Fall ist die dem Automaten zugeordnete globale Funktion tatsächlich eine lineare Funktion , wenn wir uns auf eine Operation erstrecken , die Zelle für Zelle auf den Konfigurationsraum einwirkt .
Die Linearität erleichtert das Studium der Dynamik von Automaten erheblich. Es reicht also aus, die Dynamik eines linearen Automaten auf " Basis " des Raumes seiner Konfigurationen zu kennen, um durch Linearität sein Verhalten über den gesamten Raum daraus abzuleiten. Man kann für eine solche Basis die (endliche) Menge von Konfigurationen wählen, die überall gleich ( neutral von ) sind, außer möglicherweise in der zentralen Zelle.
Additive AutomatenEine der am meisten untersuchten Familien linearer Automaten sind die sogenannten additiven Automaten , die von O. Martin, A. Odlyzko und S. Wolfram in. Diese Steuerungen sind wie folgt definiert:
Das typische Beispiel ist eines, bei dem alle Koeffizienten gleich 1 sind: Die lokale Regel besteht dann darin, das Summenmodul aller Zellen in der Nachbarschaft zu nehmen. Somit ist in Dimension 1 der elementare zellulare Automat 90 additiv: Seine Übergangsfunktion besteht darin, die Modulo-2-Summe der Zustände der beiden Nachbarn der Zelle zu bilden. Es reicht aus, das Verhalten dieses Automaten in der Konfiguration überall gleich 0 zu kennen, außer in der Mitte, in der es 1 wert ist, sein allgemeines Verhalten durch das Prinzip der Überlagerung daraus abzuleiten:
Der Elementarautomat 102 ist ebenfalls additiv. Seine Wirkung auf die Konfiguration erzeugt ein Pascal-Dreieck Modulo 2 (das auch eine Annäherung an das Sierpinski-Dreieck ergibt ). Ausgehend von der Zelle nach den Schritten befindet sich also der Status:
Durch Überlagerung leiten wir nach jedem Schritt ausgehend von einer beliebigen Konfiguration einen direkten Ausdruck des Zustands der zentralen Zelle ab :
In einem totalistischen zellularen Automaten hängt der nachfolgende Zustand einer Zelle nur von der Summe der Zustände ihrer Nachbarn ab; Dies ist der Fall beim Spiel des Lebens, bei dem eine lebende Zelle erhalten bleibt, wenn zwei oder drei ihrer Nachbarn leben, und eine tote Zelle geboren wird, wenn drei ihrer Nachbarn leben. Ein totalistischer Automat berücksichtigt daher nicht die Position der Nachbarn einer Zelle in Bezug darauf.
Wenn ein zellularer Automat zusätzlich zu seinem eigenen Zustand nicht totalistisch ist, beeinflusst die Position der Nachbarn einer Zelle ihren nachfolgenden Zustand. Zum Beispiel können wir für einen eindimensionalen zellularen Automaten zwischen der Nachbarzelle links und der Nachbarzelle rechts unterscheiden.
Diese Klassifizierung wurde 1983 von Stephen Wolfram in seinem Artikel Universalität und Komplexität in zellularen Automaten eingeführt und stellt den ersten Versuch dar, zelluläre Automaten nach ihrer Entwicklung aus zufälligen Anfangskonfigurationen zu klassifizieren. Er schlug vier Verhaltensklassen vor:
Eine der Kritikpunkte an Wolframs Klassifikation liegt in seiner Unfähigkeit zu sagen, ob ein gegebener zellularer Automat Turing-universell ist ; Darüber hinaus wurden universelle zellulare Automaten für jede der von Wolfram vorgeschlagenen Klassen gefunden. Dieser Sachverhalt ergibt sich aus dem, was Wolfram nur als zufällige Anfangsbedingungen betrachtete, nicht jedoch aus bestimmten Strukturen, die speziell für diesen Anlass geschaffen wurden. Insbesondere die Übermittlung von Informationen, beispielsweise über Schiffe , wird nicht berücksichtigt.
David Eppstein schlug eine Alternative zu dieser Klassifizierung vor:
A priori erlauben nur die letzten Fälle Universalität, auch wenn nicht alle zellularen Automaten, die darauf reagieren, dies sind. Andererseits wurde auch nicht gezeigt, dass es unmöglich ist, universelle Strukturen für die anderen Fälle aufzubauen, andere Strukturen als die Schiffe können ebenfalls Informationen übertragen.
In der obigen formalen Definition hat das Netzwerk systematisch die Form . Wir können problemlos auf andere reguläre unendliche Graphen verallgemeinern .
Die erste Klassifizierung eines zellularen Automaten betrifft die Art und Weise, wie die Regeln auf das Gitter angewendet werden:
Es ist möglich, das Konzept des zellularen Automaten zu verallgemeinern, zum Beispiel:
Die kontinuierlichen Steuerungen arbeiten nach dem gleichen Prinzip wie zellulare Automaten, verwenden jedoch Gitter oder kontinuierliche Zustände (normalerweise zwischen 0 und 1). Solche Automaten können beispielsweise die Diffusion einer Flüssigkeit simulieren.
Ein probabilistischer zellularer Automat ist ein deterministischer zellularer Automat, bei dem die lokale Regel f durch eine zufällige lokale Dynamik ersetzt wird, dh eine Übergangsmatrix, die entsprechend dem Zustand angibt, in dem wir uns befinden, mit welcher Wahrscheinlichkeit wir in einem folgenden Zustand enden können.
Es ist möglich, einen zellularen Automaten auf dem Bild zu wiederholen, das nach Anwendung desselben probabilistischen zellularen Automaten gefunden wurde. Sie können immer und immer wieder iterieren. Die Suche nach invarianten Gesetzen, bei denen die Ergodizität (Konvergenz) des Ausgangsgesetzes Themen sind, an denen derzeit geforscht wird.
Es wird vermutet (aber nicht bewiesen), dass probabilistische zelluläre Automaten alle ergodisch sind, wenn der Kardinal des Startalphabets 2 ist, und es ist bewiesen, dass dies für alle sehr großen Alphabete falsch ist. Dies wurde von Gàcs im Jahr 2001 für probabilistische zelluläre Automaten mit einem Kardinalalphabet von ungefähr Größe demonstriert .
Die Frage bleibt offen und wird für probabilistische zelluläre Automaten mit einem kleineren Kardinalalphabet nicht vermutet.
In der mathematischen Forschung werden probabilistische zelluläre Automaten auch verwendet, um bestimmte Gesetze über verallgemeinerte Perkolationen im letzten Durchgang zu vermuten.
Wir können das Modell zellulärer Automaten als diskretes Gegenstück zu partiellen Differentialgleichungen betrachten . Somit kann jedes Mal, wenn ein physikalisches Phänomen durch partielle Differentialgleichungen beschrieben wird, eines in Form eines zellularen Automaten vorgeschlagen werden. Es bleibt zu bestimmen, inwieweit das Zellmodell für die Erklärung und / oder Vorhersage des untersuchten Phänomens relevant ist. Im allgemeinen Fall ist nichts garantiert, und die Charakterisierung der globalen Dynamik des Zellmodells gemäß seiner lokalen Definition kann mindestens so schwierig sein wie die Lösung des Systems partieller Differentialgleichungen.
Andererseits kann der zellulare Automat einfach per Computer simuliert werden! Bei der numerischen Analyse bestehen viele Methoden darin, bestimmte Größen (Raum, Zeit, Wert) zu diskretisieren, um numerische Simulationen durchzuführen (siehe Finite-Elemente-Methode , endliches Volumen oder endliche Differenz ).
Unter den Modellen , die ausführlich untersucht worden sind, können wir nennen Netzwerk Gas Automaten ( Gitter gaz Automaten ) , welches Modell Gasteilchen bestimmt durch eine diskrete Version der Navier - Stokes - Gleichungen .
Die erste Formulierung dieses Modells, bekannt unter dem Namen HPP (es handelt sich um einen zellulären Automaten der Dimension ), stammt von J. Hardy, Y. Pomeau und O. Pazzis in den 1970er Jahren. Eine zweite Formulierung, FHP , wurde vorgeschlagen in den 1980er Jahren von U. Frisch, B. Hasslacher und Y. Pomeau: Es verbessert das vorherige, indem es das Zellennetzwerk durch ein hexagonales Netzwerk ersetzt.
Zelluläre Automaten finden auch Anwendung in der Modellierung und Simulation von Waldbränden . Die erste Verwendung geht auf Kourtz und O'Regan im Jahr 1971 zurück. Mit diesen Modellen kann die Ausbreitung des Feuers anhand verschiedener Parameter wie Richtung und Kraft des Windes oder der Luftfeuchtigkeit leicht beobachtet werden .
Die Muster bestimmter Muscheln wie Zapfen und Becken werden durch Mechanismen erzeugt, die dem Modell zellulärer Automaten ähneln. Die für die Pigmentierung verantwortlichen Zellen befinden sich auf einem schmalen Streifen entlang des Mundes der Schale. Jede Zelle sezerniert Pigmente entsprechend der Sekretion (oder dem Mangel an Sekretion) ihrer Nachbarn, und alle Zellen produzieren das Muster der Schale, wenn sie wächst. Beispielsweise weist die Conus-Textilart ein Muster auf, das der oben beschriebenen Regel 30 ähnelt .
K. Nagel und M. Schreckenberg schlugen in den 1990er Jahren ein Autobahnverkehrsmodell vor, das auf einem eindimensionalen zellularen Automaten basiert:
Dieses Modell entspricht einem zellularen Automaten, wenn die zufällige Störung fehlt ( ). Wenn zusätzlich (ein Fahrzeug steht entweder still oder hat seine maximale Geschwindigkeit), wird das Modell auf den elementaren zellularen Automaten 184 reduziert: Die Zellen können nur zwei Werte annehmen, die dem Leerstand oder dem Vorhandensein eines Fahrzeugs entsprechen .
Mehrere Wissenschaftler wie Andrew Ilachinski haben angenommen, dass das Universum als zellulärer Automat betrachtet werden könnte. Ilachinski begründet dies mit folgender Bemerkung: "Betrachten wir die Entwicklung von Regel 110 : Wenn es eine Art" alternatives Gesetz der Physik "wäre, wie würde die rationale Beschreibung der beobachteten Muster lauten? Ein Beobachter, der die zur Erzeugung der Bilder angewandte Regel nicht kennt, könnte die Bewegung diskreter Objekte annehmen. " Der Physiker James Crutchfield hat eine strenge mathematische Theorie herausgegeben, die auf diesem Prinzip basiert und die Entstehung statistischer" Teilchen "in zellulären Automaten demonstriert. In der Erweiterung könnte das Universum , das als eine Menge von Teilchen beschrieben werden kann, somit als zellulärer Automat betrachtet werden.
Im Oktober 2014 muss noch eine einheitliche Theorie formuliert werden, die auf dieser Annahme basiert. Dennoch hat die Forschung in dieser Richtung einigen Forschern geholfen, das Universum als diskretes System zu definieren: