imported>Henrykrumb: Neuronale Zelluläre Automaten: Belege und Verweise ergänzt

2025-08-13T19:33:17Z

Neuronale Zelluläre Automaten: Belege und Verweise ergänzt

Neue Seite

[[Datei:Gospers glider gun.gif|frame|rechts|Beispiel für ein raumzeitliches Muster, das sich in einem zellulären Automaten ausbildet<ref>Daniel Dennett, (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X </ref>]]

'''Zelluläre''' oder auch '''zellulare [[Automatentheorie|Automaten]]''' dienen der [[Modell]]ierung räumlich diskreter [[Dynamisches System|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 <math>R</math> (''Zellularraum'')
* eine endliche Nachbarschaft <math>N</math>
* eine Zustandsmenge <math>Q</math>
* eine lokale Überführungsfunktion <math>\delta\colon Q^N \to Q</math>.

Der ''Zellularraum'' besitzt eine gewisse [[Dimension (Mathematik)|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-Simulation]]en 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.<ref>TechTarget: [https://www.techtarget.com/searchenterprisedesktop/definition/cellular-automaton cellular automaton]</ref>

Für einen eindimensionalen zellulären Automat sind 2<sup>8</sup> = 256 verschiedene Regeln (Überführungsfunktionen) möglich, denn für jeden der 2<sup>3</sup> = 8 Zustände einer Zelle und ihrer zwei Nachbarzellen (3 benachbarte Zellen) sind unabhängig voneinander 2 neue Zustände möglich.<ref name=":0">Stanford Encyclopedia of Philosophy: [https://plato.stanford.edu/entries/cellular-automata/supplement.html Supplement to Cellular Automata - The 256 Rules]</ref><ref>Wolfram MathWorld: [https://mathworld.wolfram.com/ElementaryCellularAutomaton.html Elementary Cellular Automaton]</ref>

== Geschichte ==
Zellularautomaten wurden um 1940 von [[Stanislaw Ulam]] in [[Los Alamos (New Mexico)|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 [[Digitalrechner]]n bei einigen Fragestellungen überlegen. Ein analoger Zellulärer Automat zur [[Simulation]] von [[Grundwasser]]strömungen wird im [[Analogrechner#Beispiel: Zellulärer Automat|Artikel Analogrechner, Abschnitt „Beispiel: Zellulärer Automat“]] genauer beschrieben.

In den 1970er Jahren erlangte [[John Horton Conway]]s [[Conways Spiel des Lebens|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|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 [[Boolean|boolesche Werte]] dargestellt werden, kann man die Regeln für eindimensionale zelluläre Automaten in einfacher Form darstellen. Ist <math>a_i(t)</math> der Zustand der Zelle mit dem Index <math>i</math> zum Zeitpunkt <math>t = 0, 1, 2, \ldots</math>, 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:
:<math>a_i(t + 1) = f(a_{i - 1}(t), a_{i}(t), a_{i + 1}(t))</math>.

Für Regel 30, Regel 90 und Regel 110 zum Beispiel erhält man folgende konkrete Überführungsfunktionen:<ref name=":0" />
:<math>f_{30}(a_{i - 1}(t), a_{i}(t), a_{i + 1}(t)) = a_{i - 1}(t) \; \mathrm{XOR} \; (a_{i}(t) \; \mathrm{OR} \; a_{i + 1}(t))</math>
:<math>f_{90}(a_{i - 1}(t), a_{i}(t), a_{i + 1}(t)) = a_{i - 1}(t) \; \mathrm{XOR} \; a_{i + 1}(t)</math>
:<math>f_{110}(a_{i - 1}(t), a_{i}(t), a_{i + 1}(t)) = (a_{i - 1}(t) \; \mathrm{OR} \; a_{i}(t)) \; \mathrm{XOR} \; (a_{i - 1}(t) \; \mathrm{AND} \; a_{i}(t) \; \mathrm{AND} \; a_{i + 1}(t))</math>

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 [[Halteproblem]]s 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.<ref>Stanford Encyclopedia of Philosophy: [https://plato.stanford.edu/entries/cellular-automata/ Cellular Automata]</ref>

== 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|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.<gallery>
Datei:Animated spaceships.gif|Raumschiffe in [[Conways Spiel des Lebens|Conways ''Spiel des Lebens'']]
Datei:Gospers glider gun.gif|Eine Kanone, die Gleiter ausstößt
Datei:JdlV osc 5.64.gif|Ein Oszillator
Datei:Highlife replicator.gif|Ein Replikator in ''Highlife''
Datei:Color coded racetrack large channel.gif|Gleiter (gelb), Kanonen (grün) und Reflektoren (pink) in [[Conways Spiel des Lebens|Conways ''Spiel des Lebens'']]
Datei:Conways game of life breeder animation.gif|Ein Brüter
Datei:Pentomino animation 1 minute small.gif|Ein Methusalem
Datei:GOLMaxDens20x20.png|Ein Stillleben
</gallery>

== Wolframs eindimensionales Universum ==
[[Datei:EIDU-9 Wolframs 1-dimensionales Universum.jpg|mini|450px|Wolframs eindimensionales Universum]]
[[Stephen Wolfram]]s 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.
{| class="wikitable"
|-
!colspan="7"| Regeln von Wolfram’s erstem Beispiel
|-
| Anzahl lebender Nachbarn || 0 || 1 || 2 || 3 || 4 || 5
|-
| Ergebnis Folgegeneration || 0 || 0 || 1 || 0 || 1 || 0
|}
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, ähnlich wie im echten Universum. 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. Eine der interessantesten ist die „Regel 110“:

'''Regel 110'''
{| class="wikitable"
|- style="text-align:center"
|style="text-align:left"| '''neuer Zustand der mittleren Zelle'''
| 0
| 1
| 1
| 0
| 1
| 1
| 1
| 0
|-
|'''momentaner Zustand dreier benachbarter Zellen'''
|111
|110
|101
|100
|011
|010
|001
|000
|}

{| class="center"
| [[Datei:CA rule110 x400 y200 single.png|links|mini|450px|Die ersten 200 Entwicklungsschritte (von unten nach oben) von Regel 110, wenn zu Beginn nur eine Zelle ''voll'' ist und alle anderen ''leer'' sind.]]
| [[Datei:CA rule110 x3200 y3200 single.png|links|mini|225px|Die ersten 3200 Entwicklungsschritte von Regel 110. Gezeigt ist nur die linke Seite.]]
|}
<div style="clear:both;"></div>

Siehe auch: [[Regel 30]]

== Beispiele für zelluläre Automaten ==
[[Datei:Waldbrandsimulation.FullHD.webm|mini|rechts|1200 Videoframes einer mit einem zellulären Automaten implementierten Waldbrandsimulation in [[Full HD]] (1920 × 1080 Bildpunkte).<ref>{{Internetquelle |url=https://de.wikibooks.org/wiki/Waldbrandsimulation |titel=Waldbrandsimulation – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher |sprache=de |abruf=2022-11-13}}</ref>]]

* [[Conways Spiel des Lebens]] (Game of Life) ist ein einfacher zweidimensionaler zellulärer Automat, der verblüffende Strukturen erzeugt.
* [[Langton-Schleife]]n simulieren zur [[Selbstreplikation]] fähige Organismen in einem zellulären Automaten.
* Das [[Pascalsches Dreieck|Pascalsche Dreieck]] kann ebenfalls als einfacher zellulärer Automat interpretiert werden.
* Das [[Nagel-Schreckenberg-Modell]] ist ein Zellularautomat zur Simulation des [[Straßenverkehr]]s, insbesondere auf [[Autobahn]]en.
* Das [[FHP-Modell]] dient der Simulation von [[Gas]]en und [[Flüssigkeit]]en.
* Ein sehr einfacher zellulärer Automat ist der [[ASEP]].
* [[Rule 110]] ist ein zellulärer Automat, welcher [[turing-vollständig]] ist

== Garten Eden und Zwillinge ==
Der Garten Eden ist eine Konfiguration (Muster) des zellulären Automaten, die keine Vorläufer hat. Sie enthält mindestens eine endliche Konfiguration, die ebenfalls keine Vorläufer hat, einen Waisen (englisch ''orphan''). Ein Zwilling einer endlichen Konfiguration ist eine andere endliche Konfiguration, die die gleichen zukünftigen Muster hat. Ein zellulärer Automat ist injektiv, falls unterschiedliche Teile des Musters auch in Zukunft unterschiedlich bleiben, lokal injektiv, falls keine Zwillinge vorhanden sind, und surjektiv, wenn jede Konfiguration einen Vorläufer hat.

[[Edward F. Moore]] (1962<ref>Moore, ''"Machine models of self-reproduction'', Proc. Symp. Applied Mathematics, Band 14, 1962, S. 17–33</ref>) und [[John Myhill]] (1963<ref>Myhill, ''The converse of Moore’s Garden-of-Eden theorem'', Proceedings of the American Mathematical Society, Band 14, 1963, S. 685–686</ref>) bewiesen den ''Garten-Eden-Satz'' in der Theorie zellulärer Automaten: Ein zellulärer Automat im euklidischen Raum ist lokal injektiv genau dann, wenn er surjektiv ist. Das lässt sich auch so ausdrücken, dass zelluläre Automaten genau dann einen Garten Eden haben, wenn sie keine Zwillinge haben. Dabei bewies Moore einen Teil der Äquivalenz (Automaten mit Zwillingen haben Waisen), Myhill die Umkehrung (ein Automat mit Waisen hat auch Zwillinge).

== Anwendungen ==

=== Bildverarbeitung ===
[[Bildverarbeitung]] muss in der Lage sein, die Komponenten des Bildes unabhängig von ihrer Position und Drehung zu erkennen, und es sollte auch gegenüber kleinen Unterschieden tolerant sein. Sie sollte ähnliche Strukturen erkennen und ein quantitatives Ergebnis dafür zurückgeben.<ref>Jan Helm, Technische Universität Berlin: [https://www.researchgate.net/publication/358187601_Cellular_automata_and_their_applications Cellular automata and their applications]</ref>

Viele Bildverarbeitungsprogramme werden mit zellulären Automaten realisiert. Es gibt viele Systeme, die ein sogenanntes ''Attraktor''-Verhalten haben. Als Veranschaulichung kann man Berge verwenden. Ein Tropfen Regen kann überall in den Bergen fallen, aber – in einem idealisierten Modell – fließt es zu einer begrenzten Anzahl von niedrigsten Punkten. Nahe beieinander liegende Tropfen fließen tendenziell zum gleichen niedrigsten Punkt. Tropfen auf der anderen Seite einer [[Wasserscheide]] fließen zu anderen niedrigsten Punkten. Bilder bestehen jedoch aus digitalen [[Pixel]]n. Anstatt eine physische Bewegung zu betrachten, muss man digitale Werte betrachten, die von [[Computerprogramm]]en verarbeitet werden. Ein ähnliches Attraktor-Verhalten kann dort auftreten. Zum Beispiel gibt es viele zelluläre Automaten, bei denen man die Farben einiger Zellen in ihren Anfangszuständen ändern kann, aber immer noch in demselben festen Endzustand endet.<ref>Stephen Wolfram: [https://writings.stephenwolfram.com/2015/05/wolfram-language-artificial-intelligence-the-image-identification-project/ Wolfram Language Artificial Intelligence: The Image Identification Project]</ref>

Die integrierte Bildverarbeitung von [[Stephen Wolfram]] in [[Mathematica]] ist ein leistungsstarkes und präzises Instrument zur Erkennung und quantitativen Beschreibung morphologischer Komponenten. [[Wolfram Research]] bietet integrierte Unterstützung sowohl für die automatisierte als auch für die interaktive Bildverarbeitung, die vollständig in die leistungsstarken mathematischen und algorithmischen Funktionen der Wolfram-Sprache integriert ist. Sie können Bilder erstellen und importieren, sie mit eingebauten Funktionen manipulieren, lineare und nichtlineare Filter anwenden und auf verschiedene Weise visualisieren.<ref>Wolfram: [https://reference.wolfram.com/language/tutorial/ImageProcessing.html Image Processing]</ref>

=== Kryptografie ===
Einige [[Kryptographie|kryptographische]] Verfahren basieren auf zellulären Automaten. Zelluläre Automaten wurden von Guan und Kari für [[Asymmetrisches Kryptosystem|asymmetrische Kryptosysteme]] vorgeschlagen. Für solche Systeme sind zwei Schlüssel erforderlich: ein [[öffentlicher Schlüssel]] für die Verschlüsselung, und ein geheimer [[privater Schlüssel]] für die Entschlüsselung. Auch [[Symmetrisches Kryptosystem|symmetrische Kryptosysteme]] können mit zellulären Automaten realisiert werden. Der Verschlüsselungsprozess basiert dort auf der Generierung pseudozufälliger Bitfolgen.<ref>Pascal Bouvry, Franciszek Seredyński, Albert Zomaya: [https://www.researchgate.net/publication/220698034_Application_of_Cellular_Automata_for_Cryptography Application of Cellular Automata for Cryptography]</ref>

=== Künstliches Leben ===
Im Bereich des [[Künstliches Leben|künstlichen Lebens]] wird versucht, lebensechte [[Computermodell]]e zu schaffen, die Ideen aus dem biologischen Leben übernehmen, beispielsweise dezentrale und lokale Steuerung. Die bei der künstlichen Entwicklung angewandten Techniken basieren häufig auf der indirekten Kodierung von Entwicklungsregeln analog zum Genom eines biologischen Organismus. Diese Art der Kodierung erleichtert die Skalierung eines Organismus, da die Informationen im Genom viel kleiner sind als im resultierenden [[Phänotyp]].

Eines der einfachsten Computermodelle für künstliches Leben ist ein zellulärer Automat. Im Jahr 2002 wurde eine zellulärer Automat mit Regeln beschrieben, die durch ein [[Künstliches neuronales Netz|künstliches neuronales Netzwerk]] definiert werden. Heutzutage wird diese Art von Ansatz als neuronaler zellulärer Automat (NCA) bezeichnet. Im Jahr 2017 haben Forscher einen NCA präsentiert, der Eigenschaften hat, die durch Neuroevolution mit sogenanntem ''Compositional Pattern-Producing Network'' erlernt wurden.<ref>{{Internetquelle |autor=Mathias Berild Ose |url=https://ntnuopen.ntnu.no/ntnu-xmlui/bitstream/handle/11250/2459261/17066_FULLTEXT.pdf?sequence=1 |titel=Evolving Compositional Pattern Producing Networks For Cellular Automata Transition Rules |werk=ntnu.no |hrsg=NTNU |datum=2017 |sprache=en |abruf=2025-08-13}}</ref> Im Jahr 2020 haben Forscher einen differenzierbaren NCA entwickelt, der Wachstumseigenschaften und Regenerationseigenschaften besitzt. Bei ihrer Arbeit wird ein NCA mit einem [[Gradientenverfahren]] darauf trainiert, aus einer aktiven Zelle ein farbiges Bild zu erzeugen.<ref>{{Internetquelle |autor=Alexander Mordvintsev, Ettore Randazzo, Eyvind Niklasson, Michael Levin |url=https://distill.pub/2020/growing-ca/ |titel=Growing Neural Cellular Automata - Differentiable Model of Morphogenesis |werk=distill.pub |datum=2020 |sprache=en |abruf=2025-08-13}}</ref>

=== Robotik ===
Formationen oder Schwärme von [[Roboter]]n, die bei Rettungsaktionen, bei der Landschaftsvermessung oder im Krieg eingesetzt werden, können mithilfe von zellulären Automaten gesteuert werden. Dabei werden Roboter als Zellen in einem zellularen Automaten modelliert. Das Verhalten jedes einzelnen Roboters ist reaktiv gegenüber seinen Nachbarn und sorgt so für Ordnung in der gesamten Gruppe. Jeder Roboter muss lediglich seine relative Position und Ausrichtung zu jedem Roboter in seiner Nachbarschaft kennen, um einen Bewegungspfad zu berechnen und seine gewünschte Position zu erreichen. Somit wird eine Formation mithilfe einer verteilten Steuerungsarchitektur aufgebaut und aufrechterhalten, die kein globales Informationssystem und keinen zentralen Anführer erfordert.<ref>Ross Mead, Robert Louis Long, Jerry B. Weinberg: [https://www.researchgate.net/publication/221063986_Fault-Tolerant_Formations_of_Mobile_Robots Fault-Tolerant Formations of Mobile Robots]</ref>

Das [[Schwarmverhalten]] von Menschen wird aufgrund ihrer breiten Anwendbarkeit untersucht. Die Analyse eines Schwarms unter unsicheren Bedingungen ist relevant, weil Fußgänger bei Fluchtversuchen manchmal schlimme Fehler machen. Bei solchen Untersuchungen werden Simulationen anhand von Umgebungsabstraktionen strukturiert und die Ergebnisse helfen dabei, Sicherheitsstandards für Gebäude zu bestimmen. Ein weiteres Forschungsgebiet, das mit diesem Ziel in Einklang steht, ist die Untersuchung von mobilen Schwärmen von Robotern. Beispiele für ein solches natürliches kollektives Verhalten sind die Pheromon-Interaktion, die von Ameisenvölkern eingesetzt wird, und der Schwänzeltanz der Bienen.

Mehrere von der Biologie inspirierte [[Algorithmus|Algorithmen]] der [[Schwarmintelligenz]] wurden im Kontext der kollektiven [[Robotik]] untersucht. Aus der Analyse früherer Studien zur Evakuierung von Menschenmengen konnte eine Parallele zwischen der Dynamik von Fußgängern in Umgebungen mit begrenzter Leistung und dem Verhalten eines Roboterteams bei der Durchführung von Nahrungssuche-Aufgaben gezogen werden. Darüber hinaus sollten Konflikte zwischen dem Roboter und der Umgebung kontrolliert werden, eine ähnliche Situation wie Konflikte zwischen Menschen und Hindernissen, die ihre ursprüngliche Route ändern können.

Bei der Simulation von Fußgängern besteht das Ziel darin, Modelle zu finden, die das natürliche Verhalten der Menschenmenge während eines Evakuierungsszenarios nachbilden. Andererseits können in der Robotik ähnliche Modelle zur Steuerung des Roboterverhaltens verwendet werden, was zu einer effizienten Ausführung der Aufgabe führt.<ref>Danielli A. Lima, Gina M. B. Oliveira: [https://www.sciencedirect.com/science/article/pii/S0307904X17301701?ref=pdf_download&fr=RR-2&rr=82ac5dd60e2f4480 A cellular automata ant memory model of foraging in a swarm of robots]</ref>

=== Physik ===
Man kann das Universum als eine riesige numerische Berechnung betrachten, die auf einer Art zellulärem Automaten läuft. Ein Großteil der Schwierigkeiten beim Verständnis von Raum und Zeit in der [[Moderne Physik|modernen Physik]] beruht auf der Annahme, dass Raum und Zeit tatsächlich grundlegende Einheiten in unserem Universum sind. In der Theorie der zellulären Automaten ist dies definitiv nicht der Fall. Raum und Zeit sind das Ergebnis komplexer Wechselwirkungen von Teilchen. Um Materie zu erforschen, muss man Teilchen nutzen, um Teilchen zu untersuchen.

Zelluläre Automaten können verwendet werden, um Wechselwirkungen von Teilchen zu simulieren. Es gibt spezielle Computer mit einer Architektur für zelluläre Automaten, die für physikalische Modellierungen und Simulationen eingesetzt werden. Im Gegensatz zu gewöhnlichen Computern aktualisieren solche Computer alle ihre Speicherplätze in einem einzigen Taktzyklus, wodurch sie wesentlich schneller und leistungsfähiger sind. Es ist wichtig zu beachten, dass der Taktzyklus Ereignisse im Zusammenhang mit dem zellulären Automaten markiert und keine Ereignisse in unserem Zeitmaß.<ref>Tom Ostoma, Mike Trushyk: [https://arxiv.org/ftp/physics/papers/9907/9907013.pdf Cellular Automata Theory and Physics]</ref>

== Probabilistische Zelluläre Automaten ==
Bei probabilistischen zellulären Automaten sind die Regeln mit denen Übergänge erfolgen nicht deterministisch, sondern zufällig. In diesem Aspekt ähneln probabilistische zelluläre Automaten den [[Monte-Carlo-Simulation]]en.

Probabilistische zelluläre Automaten stehen im Gegensatz zu deterministischen zellulären Automaten. Ein Beispiel für einen deterministischen Zellulären Automaten ist der Q2R Automat, der das [[Ising-Modell]] der [[Theoretische Physik|theoretischen Physik]] beschreibt. Der Q2R Automat ist [[deterministisch]], [[Reversibler Prozess|reversibel]] und sehr schnell. Es wurde allerdings gezeigt, dass der [[Metropolis-Algorithmus]], der auf [[Zufallsvariable]]n und [[Zufallszahl]]en basiert, geeigneter ist, das Ising-Modell zu beschreiben.<ref>Alejandro Salcido: [https://books.google.de/books?id=P9CcDwAAQBAJ&pg=PA441&hl=de#v=onepage&q&f=false Cellular Automata - Simplicity Behind Complexity, S. 440–441]</ref>

== Siehe auch ==
* [[Ameise (Turingmaschine)]]
* [[Emergenz]]
* [[Evakuierungssimulation]]
* [[Künstliches Leben]]
* [[Musterbildung]]
* [[Räuber-Beute-Beziehung|Räuber-Beute-Modell]]
* [[Turingmaschine]]
* [[Wator]]
* [[Wireworld]]
* [[Pascalsche Pyramide|Pascalsches Dreieck]] kann mit zellulären Automaten simuliert werden
* [[Endlicher Automat]]

== Literatur ==
* Melanie Mitchell: ''Complexity. A Guided Tour.'' Oxford University Press, Oxford u. a. 2009, ISBN 978-0-19-512441-5, {{Google Buch|BuchID=sSgzHayrDBsC}}.
* [[Klaus Mainzer]], [[Leon Chua]]: ''The Universe as Automaton. From Simplicity and Symmetry to Complexity.'' Springer, Heidelberg u. a. 2012, ISBN 978-3-642-23476-7, {{Google Buch|BuchID=21X_4SF9vP4C}}.

== Weblinks ==
{{Commonscat|Cellular automata}}
'''Sekundärliteratur'''
* {{SEP|http://plato.stanford.edu/entries/cellular-automata/|Cellular Automata|Francesco Berto, Jacopo Tagliabue}}
* Jürgen Schmidhuber: [http://www.idsia.ch/~juergen/digitalphysics.html Webseite] über [[Konrad Zuse]]s Theorie des ''Rechnenden Raumes'' ([ftp://ftp.idsia.ch/pub/juergen/zuse67scan.pdf Auszug] aus ''Elektronische Datenverarbeitung'' 8 (1967) S. 336–344)
'''Visualisierungen und Implementierungen'''
* [http://download.chip.eu/de/Wolframs-Universum_6503402.html Wolfram’s 1-dimensionales Universum als C#-Implementierung]
* [http://www.ca.kaifranz.de/ 2.5d zellulärer Automat] (3d game of life) mit Dokumentation und Quellcode
* {{Webarchiv | url=http://www.uni-tuebingen.de/uni/bcm/schoenfisch/green.html | wayback=20100618062231 | text=Greenberg-Hastings-Automaten}} als [[Java-Applet]]
* [http://site2004.de/java/automat.html Zyklischer Zellulärer Automat] als Java-Applet
* [http://www.loop.li/zellomat3d/ Zellomat3D] – 3D-zellulärer Automat
* [[NetLogo]]<ref>{{Internetquelle |url=http://ccl.northwestern.edu/netlogo/models/CA1DElementary |titel=NetLogo Models Library: CA 1D Elementary Cellular Automata |zugriff=2018-11-26|sprache=en}}</ref> – Agenten-basierte Modellierungs- und Simulationsumgebung
* [http://www.flowinguniverse.com/cellular_randomdesign_e/ Random Design] – Zufallserzeugte zelluläre Automaten
* [https://www.youtube.com/watch?v=wdafwUKV5WI Ordnungsprozess in einem Monte-Carlo-basierten zellulären Automat] (Youtube-Video)
* [http://www.earslap.com/projectslab/otomata Otomata] – Sequencer als interaktiver zellulärer Automat
* [http://www.cafun.de/ Cafun] – Freeware Java Implementierung zur Simulation und Visualisierung zellulärer Automaten mit XML-basierter Konfiguration
* [http://golly.sourceforge.net/ Golly] – Simulation zahlreicher verschiedener zellulärer Automaten mit Beispielen

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4190671-8}}

{{SORTIERUNG:Zellularer Automat}}
[[Kategorie:Dynamisches System]]
[[Kategorie:Automatentheorie]]
[[Kategorie:Wikipedia:Artikel mit Video]]

Zellulärer Automat - Versionsgeschichte

imported>Henrykrumb: Neuronale Zelluläre Automaten: Belege und Verweise ergänzt