© Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer Nature 2024
K. Mainzer (Hrsg.)Philosophisches Handbuch Künstliche Intelligenzhttps://doi.org/10.1007/978-3-658-19606-6_15

Grundlagen zellulärer Automaten

Klaus Mainzer1  
(1)
TUM Senior Excellence Faculty, Technische Universität München (TUM), München, Deutschland
 
 
Klaus Mainzer
Email: mainzer@tum.de
1 Einleitung
2 Dynamik zellulärer Automaten
3 Komplexität zellulärer Automaten
4 Symmetrie im Universum zellulärer Automaten
5 Ausblick of ein berechenbares Universum dynamischer Systeme
Literatur

Zusammenfassung

Zelluläre Automaten waren erste Modelle, mit denen John von Neumann und Konrad Zuse die Selbstorganisation des Lebens simulierten. Sie wurden zur Grundlage erster Modelle künstlichen Lebens. Stephen Wolfram u. a. versuchten, durch Computerexperimente mit komplexen Automaten die Vielfalt komplexer Strukturen quasi-empirisch zu beschreiben. Tatsächlich erweisen sich zelluläre Automaten aber mathematisch als komplexe Systeme, deren Dynamik in Phasenübergängen durch Differenzialgleichung bzw. Differenzengleichungen modelliert werden kann. Damit werden ihre komplexen Muster- und Strukturbildungen analytisch exakt beschreibbar und prognostizierbar wie bei komplexen dynamischen Systemen der Physik. Bemerkenswert ist, dass damit auch fundamentale Symmetriegesetze wie in der Physik deutlich werden, auf die sich die Vielfalt der Muster und Strukturen reduzieren lässt.

Schlüsselwörter
Zellulärer AutomatSelbstorganisationDynamisches komplexes SystemUniverselle BerechenbarkeitSymmetrien

1 Einleitung

Die Entdeckung der DNA-Struktur und des genetischen Kodes war ein erster Schritt zum Verständnis eines molekularen Mechanismus, der sich selbst reproduziert (Mainzer 2019). Die Computerpioniere von Neumann und Zuse zeigten unabhängig voneinander, dass für die Selbstreproduktion nicht die Art der materiellen Bausteine grundlegend ist, sondern eine Organisationsstruktur, die eine vollständige Beschreibung von sich selbst enthält und diese Information zur Schaffung neuer Kopien (Klone) verwendet (von Neumann 1966; Zuse 1969).

Die Analogie mit dem Zellverband eines Organismus entsteht, wenn man sich das System eines zellulären Automaten als unbegrenztes Schachbrett vorstellt, auf dem jedes Quadrat eine Zelle repräsentiert. Die einzelnen Zellen der parkettierten Ebene lassen sich als endliche Automaten auffassen, deren endlich viele Zustände durch verschiedene Farben oder Zahlen unterschieden werden. Im einfachsten Fall gibt es nur die beiden Zustände „schwarz“ (1) oder „weiß“ (0). Eine Umgebungsfunktion gibt an, mit welchen anderen Zellen die einzelne Zelle verbunden ist. Sie kann z. B. die Form eines Kreuzes oder Quadrates festlegen.

Der Zustand einer Zelle hängt von Zuständen in der jeweiligen Umgebung ab und wird durch (lokale) Regeln bestimmt. Da alle Regeln in einem Schritt ausgeführt werden, arbeitet das Automatennetz des zellulären Automaten synchron und taktweise. Die aus einer Konfiguration von zellulären Zuständen durch Regelanwendung entstandene Konfiguration heißt Nachfolger der ursprünglichen Konfiguration. Die aus einer Konfiguration durch wiederholte Regelanwendung entstandenen Konfigurationen heißen Generationen der ursprünglichen Konfiguration. Eine Konfiguration ist stabil, wenn sie mit ihrem Nachfolger übereinstimmt. Sie „stirbt“ in der nächsten Generation, wenn alle ihre Zellen im Zustand „weiß“ (0) sind.

Ein Beispiel für einen 2-dimensionalen zellulären Automaten mit zwei Zuständen „lebendig“ (schwarz) und „tot“ (weiß) ist folgende Version von John Conways „Game of Life“ (Spiel des Lebens) mit lokalen Regeln: (1) Eine lebendige Zelle überlebt zur nächsten Generation, wenn zwei oder drei Zellen der Nachbarschaft ebenfalls lebendig sind. (2) Eine Zelle stirbt, wenn sich in der Nachbarschaft mehr als drei („Überbevölkerung“) oder weniger als zwei lebendige Zellen befinden („Isolation“). (3) Eine tote Zelle darf dann und nur dann lebendig werden, wenn exakt drei der Nachbarzellen lebendig sind. Conways „Game of Life“ ist ein zellulärer Automat, der in nachfolgenden Generationen komplexe Muster erzeugt, die an die Gestalt zellulärer Organismen erinnern. Er ist sogar ein universeller zellulärer Automat, da er jede Musterbildung eines zellulären Automaten simulieren kann (Berlekamp et al. 1982).

Technisch können zelluläre Automaten durch einen Computer simuliert werden. Ein entsprechendes Computerprogramm für einen zellulären Automaten verwendet im Prinzip die gleichen Methoden, als würde man zelluläre Musterentwicklung mit Papier und Bleistift durchführen. Zunächst wird ein Arbeitsbereich für die Zellen festgelegt. Dabei entspricht jede Zelle einem Speicherelement im Computer. Bei jedem Entwicklungsschritt muss das Programm einzeln nacheinander jede Zelle aufsuchen, die Zustände der Nachbarzellen bestimmen und den nächsten Zustand der Zelle berechnen. In diesem Fall ist ein zellulärer Automat auf einem sequenziellen Digitalcomputer simulierbar. Besser und effektiver wäre ein Netz aus vielen Prozessoren in zellulärer Verschaltung, in denen die Verarbeitung parallel wie in einem zellulären Organismus abläuft. Umgekehrt lässt sich jeder Computer als universelle Turingmaschine durch einen universellen zellulären Automaten simulieren.

Nach John von Neumann muss ein sich selbst reproduzierender Automat die Leistungsfähigkeit einer universellen Turingmaschine haben, also jede Art von zellulärem Automaten simulieren können. In der präbiologischen Evolution hatten die ersten sich selbst reproduzierenden Makromoleküle und Mikroorganismen sicher nicht den Komplexitätsgrad eines universellen Computers. Daher entwickelte Chris Langton einfachere zelluläre Automaten ohne die Fähigkeit universeller Berechenbarkeit, die sich spontan in bestimmten Perioden wie Organismen reproduzieren können. Anschaulich erinnern ihre PC-Bilder an einfache zelluläre Organismen mit kleinen Schwänzen, aus denen sich ähnliche kleine Organismen bilden:

Die Zustände der Zellen werden in Abb. 1 durch Zahlen markiert (Langton 1989, 1991). Leere Zellen haben den Zustand 8 und bilden die virtuelle Umwelt der virtuellen Organismen. Zellen im Zustand 2 hüllen den virtuellen Organismus wie eine Haut ein und grenzen ihn von der Umwelt ab.
Abb. 1

Zelluläre Automaten simulieren zelluläre Selbstorganisation. (Langton 1989; Mainzer 2019, Abb. 89)

Die innere Schleife trägt den Kode für die Selbstreproduktion. Zu jedem Zeitpunkt werden die Kodenummern entgegen dem Uhrzeigersinn schrittweise weiterbewegt. Je nachdem, welche Kodenummer das schwanzartige Ende erreicht, wird es um eine Einheit erweitert oder wird eine Linksbiegung bewirkt.

Nach vier Durchläufen ist die zweite Schleife vollendet. Beide Schleifen trennen sich, und der zelluläre Automat hat sich selbst reproduziert. Schließlich bedeckt eine Kolonie solcher Organismen den Bildschirm. Während sie sich an den Außenrändern reproduzieren, werden die mittleren bei der Selbstproduktion von ihren eigenen Nachkommen blockiert. Wie bei einem Korallenriff bilden sie ein totes zelluläres Skelett, auf dem sich das virtuelle Leben weiterentwickelt.

Zweidimensionale zelluläre Automaten bestehen aus einem Netz einzelner Zellen, die durch die Geometrie der Zellanordnung, die Nachbarschaft jeder Einzelzelle, ihre möglichen Zustände und die davon abhängenden Transformationsregeln für zukünftige Zustände charakterisiert sind. Zur Analyse der Evolutionsmodelle genügen eindimensionale zelluläre Automaten, die aus einer Zeile von Zellen in einem zweidimensionalen Parkett bestehen (Wolfram 1986, 2002). In einem einfachen Fall hat jede Zelle zwei Zustände 0 und 1, die grafisch z. B. durch ein weißes bzw. schwarzes Quadrat dargestellt werden können. Der Zustand jeder Zelle ändert sich in einer Folge von diskreten Zeitschritten nach einer Transformationsregel, in der die vorherigen Zustände der jeweiligen Zelle und ihrer beiden Nachbarzellen berücksichtigt sind.

2 Dynamik zellulärer Automaten

Einer einfache Version sind 1-dimensionale zelluläre Automaten (CA) mit zwei Zuständen, die aus identischen Zellen mit einer periodischen Randbedingung bestehen. In diesem Fall handelt es sich um einen Ring von L = I+1 Zellen, die hintereinander von i = 0 bis i = I bezeichnet werden (Abb. 2(a)). Jede Zelle i hat zwei Zustände ui ϵ {0, 1}, die mit den Farben Blau und Rot markiert sind. Eine Uhr gibt den Takt in diskreten Zeitabständen von Iterationen oder Generationen vor. Der Zustand $$ {u}_i^{t+1} $$ von allen Zellen i zum Zeitpunkt t+1 (d. h. die nächste Generation) ist determiniert durch die Zustände ihrer nächsten Nachbarn $$ {u}_{i\hbox{--} 1}^t $$, $$ {u}_{i+1}^t $$, und von ihnen selbst $$ {u}_i^t $$ zum Zeitpunkt t (Abb. 2(c)), d. h. durch eine Boolesche Funktion $$ {u}_i^{t+1} $$ = N ($$ {u}_{i\hbox{--} 1}^t $$, $$ {u}_i^t $$, $$ {u}_{i+1}^t $$) entsprechend zu der Booleschen Wahrheitswerttafel von 8 = 23 verschiedenen Mustern von 3 Inputs (Abb. 2(d)).
Abb. 2

Schema eines 1-dimensionalen zellulären Automaten mit zwei Zuständen und lokaler Regel N. (Mainzer und Chua 2011, Abb. 2.2)

2.1 Von einfachen lokalen Regeln zu globalen komplexen Mustern

Diese acht Muster aus 3 Inputs lassen sich anschaulich mit den acht Ecken eines Würfels darstellen (Abb. 2(b)), der deshalb Boolescher Würfel genannt wird (Chua et al. 2002). Der Output für jedes vorgeschriebene Muster aus 3 Inputs wird den entsprechenden Farben (rot für 1, blau für 0) an den Ecken des Booleschen Würfels (in Abb. 2(d) noch unspezifiziert) zugeordnet. Da es 28 = 256 verschiedene Kombinationen von acht Bits gibt, liegen entsprechend genau 256 Boolesche Würfel mit verschiedenen Farbkombinationen der Ecken vor. Daraus ergibt sich eine Gallerie von bunten Würfeln.

Es ist zweckmäßig, die 8-Bit Muster für jede Boolesche Funktion mit einer Dezimalzahl N zu verknüpfen, die das entsprechende 8-Bit Wort repräsentiert, also N = β 7∙27 + β 6∙26 + β 5∙25 + β 4∙24 + β 3∙23 + β 2∙22 + β 1∙21 + β 0∙20 mit β i ϵ {0, 1}. Da β i = 0 für jede blaue Ecke in Abb. 2(b) ist, ergibt sich N einfach durch Addieren der Gewichte (angezeigt neben jedem Muster in Abb. 2(b)), die mit allen roten Ecken verbunden sind. So ist beispielsweise für den Booleschen Würfel in Abb. 3(b) N = 0∙27 + 1∙26 + 1∙25 + 0∙24 + 1∙23 + 1∙22 + 1∙21 + 1∙20 = 26 + 25 + 23 + 22 + 21 = 110.
Abb. 3

Beispiel der lokalen Regel 110. (Mainzer und Chua 2011, Abb. 2.2)

Für das Beispiel der lokalen Regel 110 werden der Ring und die farbigen Ecken des Booleschen Würfels in Abb. 3(a)-(b) gezeigt. Für jede gegebene binäre Bit-Anfangskonfiguration zum Zeitpunkt t = 0 wird die lokale Regel N genutzt, um den Zustand $$ {u}_i^{t+1} $$ für jede Zelle i zum Zeitpunkt t+1 abzudaten. Dabei werden die Zustände der drei Nachbarzellen i–1, i, und i+1, zentriert an der Stelle i, verwendet. Das Raum-Zeit Muster, das sich in den Zeitschritten t = 0, 1, 2, … , 11 ergibt, ist in Abb. 3(c) mit dem Anfangszustand in t = 0 gezeigt.

Im Prinzip könnte man die Muster von zellulären Automaten entsprechend dieser Regeln auch Schritt für Schritt zeichnen. Heutige Computer mit großer Geschwindigkeit und Rechenkapazität ermöglichen allerdings umfangreiche Computerexperimente, um komplexe Musterbildungen dieser Automaten in kurzer Zeit zu untersuchen. Stephen Wolfram entdeckte dabei bemerkenswerte Analogien mit Musterbildungen in Physik und Biologie (Wolfram 2002). In der Welt der zellulären Automaten scheinen sich Phänomene ähnlich zur physikalischen Welt zu entwickeln. Einige Automaten erzeugen symmetrische Muster, die an Farbmuster von Seemuscheln, Tierfellen oder Federn erinnern. Andere Automaten reproduzieren Rhythmen wie oszillierende Wellen. Einige dieser Automaten stoppen ihre Entwicklung nach endlich vielen Schritten, unabhängig von ihrem Anfangszustand, und verbleiben in einem konstanten Farbzustand ähnlich zu einem System, das einen finalen Gleichgewichtszustand für alle zukünftigen Entwicklungsschritte erreicht. Einige Automaten entwickeln komplexe Muster, die an Wachstum von Korallen und Pflanzen erinnern und dabei empfindlich abhängig von kleinsten Veränderungen der Anfangszustände sind. Dieses Phänomen ist als Schmetterlingseffekt wohlbekannt, wenn lokale Ereignisse zu globalen Effekten in chaotischen und instabilen Situationen (wie z. B. Wetter und Klima) führen. Auch solche chaotischen Muster können durch zelluläre Automaten erzeugt werden.

Man kann diese Muster nach äußeren Klassifikationsmerkmalen zusammenfassen, so wie Zoologen und Botaniker Tiere und Pflanzen in Taxonomien zusammenfassen. Aber äußere Merkmale sind manchmal irreführend. Es stellt sich die fundamentale Frage: Gibt es wie in der Natur auch Gesetze komplexer Musterbildung für zelluläre Automaten? Kann die Entwicklung komplexer Muster in mathematisch präziser Weise wie in der Physik vorausgesagt werden? Daher plädieren wir für eine mathematisch präzise Erklärung der Dynamik zellulärer Automaten. Dazu müssen zelluläre Automaten zunächst wie komplexe dynamische Systeme in der Physik durch Differenzialgleichungen bestimmt werden.

2.2 Zelluläre Automaten als dynamische Systeme

Jede Zelle i wird als dynamisches System mit intrinsischem Zustand xi , Output yi und drei Inputs ui–1, ui und ui+1 definiert, wobei ui–1 den Input der linken Nachbarzelle i–1, ui den Selbstinput der Zelle i und ui+1 den Input der rechten Nachbarzelle i+1 im Ring von Abb. 2(a) bezeichnen. Jede Zelle entwickelt sich gemäß seiner vorgeschriebenen Dynamik und seiner eigenen Zeitskala. Wenn die Zellen gekoppelt werden, entwickelt sich das Gesamtsystem konsistent mit eigener Regel und Wechselwirkungsregeln für die einzelnen Zellen, die durch Kopplungsgesetze definiert werden.

Jeder Input wird als Zahlenkonstante ui ∈ {–1, 1} angenommen. Ausgehend vom Anfangszustand xi(0) = 0 konvergiert der Output yi zu einer der beiden Konstanten –1 oder 1. Tatsächlich benötigt ein dynamisches System eine gewisse Zeit, um zu einem Attraktor zu konvergieren. Für den Zweck idealisierter zellulärer Automaten wird allerdings angenommen, dass jeder Attraktor augenblicklich (instantan) erreicht wird. Unter dieser Annahme und unter Berücksichtigung binärer Inputs und Outputs kann ein dynamisches System durch eine nichtlineare Abbildung definiert werden, die eindeutig durch eine Wahrheitswerttafel für drei Inputvariablen (ui–1, ui, ui+1) beschrieben wird. Die Wahl von {–1, 1} und nicht {0, 1} als binäre Signale ist wichtig, da der Zustand xi und der Output yi sich in reeller Zeit (im Sinn reeller Zahlen) durch eine sorgfältig entworfene skalare gewöhnliche Differenzialgleichung entwickelt. Nach dieser Differenzialgleichung tendiert der Output yi, der durch eine Outputgleichung yi = y(xi) definiert ist, entweder zu 1 oder zu –1, nachdem die Lösung xi (mit Anfangszustand xi(0) = 0) den stationären Zustand erreicht hat. In dieser Weise können die Attraktoren des dynamischen Systems genutzt werden, um eine binäre Wahrheitswerttafel zu kodieren.

Neben der intrinsischen Zeitskala der einzelnen Zellen (die in zellulären Automaten keine Rolle spielt) wird ein externer Uhrenmechanismus eingeführt, um den Input ui jeder Zelle i am Ende jedes Uhrenzyklus zurückzusetzen, indem der stationäre Zustand des Outputs yi ∈ {–1, 1} als upgedateter Input ui ∈ {–1, 1} für die nächste Iteration zurückgeleitet wird. Dieser Mechanismus entspricht der periodischen Randbedingung eines 1-dimensionalen zellulären Automaten in Abb. 2(a).

Obwohl zelluläre Automaten nur mit den Evolutionen des Rings in diskreten Zeiten zu tun haben, ist jeder Computer, die zur Simulation zellulärer Automaten benutzt wird, als technisch-physikalische Maschine immer ein System mit stetiger (reeller) Zeit mit praktisch sehr kleiner Zeitskala, deren Intervalle aber ungleich Null sind. Computer benutzen Transistoren als Geräte und jede Iteration eines zellulären Automaten beinhaltet die physikalische Evolution von Millionen von Transistoren mit eigener intrinsischer Dynamik. Diese Transistoren entwickeln sich entsprechend einem großen System von nicht linearen Differenzialgleichungen, die den gesamten internen Schaltkreis des Computers bestimmen und den gewünschten Output zurückgeben, nachdem sie zu ihren Attraktoren in einem Zeitraum ungleich Null konvergiert sind.

Diese Analyse führt zu dem wichtigen Resultat, dass sogar in diskreten Systemen wie zellulären Automaten zwei verschiedene Zeitskalen involviert sind. Die erste Zeitskala bezieht sich auf die Regel N, während sich die zweite Zeitskala auf die globalen Muster der Evolution bezieht. Um die komplexe Dynamik der globalen Muster zu verstehen, müssen beide Zeitskalen berücksichtigt werden. Indem sich die Wahrheitswerttafeln zellulärer Automaten in einem entsprechenden nichtlinearen dynamischen System entfalten, kann die Theorie nichtlinearer Differenzialgleichungen ausgenutzt werden, um alle Phänomene der Musterbildung durch eine präzise mathematische Theorie zu erklären und nicht nur als empirische Beobachtungen.

Dazu werden das binäre Symbol 0 durch die reelle Zahl –1 und die Input- und Outputwerte 0 und 1 in der Wahrheitswerttafel von Abb. 2(d) durch die reelle Zahlen –1 and 1 ersetzt. Ein Vorteil des Arbeitens mit der numerischen anstelle der symbolischen Wahrheitswerttafel sind die bemerkenswerten Einsichten, die sich aus der äquivalenten Darstellung mit Booleschen Würfeln ergeben. Dabei sind die acht Würfelecken (–1,–1,–1), (–1,–1,1), (–1,1,–1), (–1,1,1), (1,–1,–1), (1,–1,1), (1,1,–1) and (1,1,1) exakt mit den Koordinaten (ui – 1, ui, ui + 1) eines Koordinatensystems lokalisiert, dessen Ursprung im Zentrum des Würfels ist. Die Ecke n = 0, 1, 2, … , 7 entspricht der Reihe n der Wahrheitswerttafel und ist blau markiert, falls der Output –1 ist, und rot für Output 1.

Die Wahl von {–1, 1} anstelle von {0, 1} als binäre Signale ist notwendig, wenn die Wahrheitswerttafel auf ein dynamisches System abgebildet wird, dessen Zustände sich in reeller Zeit gemäß einer gewöhnlichen Differenzialgleichung entwickeln, die immer auf dem reellen Zahlensystem beruht. Jede Zelle i ist nur mit ihrer linken Nachbarzelle i–1 und ihrer rechten Nachbarzelle i+1 gekoppelt. Als dynamisches System hat jede Zelle i eine Zustandsvariable xi, eine Outputvariable yi und drei konstante binäre Inputs ui–1, ui, und ui+1 (Abb. 4).
Abb. 4

Zelle als dynamisches System mit Zustandsvariable xi, Outputvariable yi und drei konstanten binären Inputs ui–1, ui und ui+1. (Mainzer und Chua 2011, Abb. 2.3)

Daher ist das dynamische System durch folgende Gleichungen bestimmt:
$$ {\displaystyle \begin{array}{l}\mathrm{Zustandsgleichung}:{\dot{x}}_i=f\left({x}_i;{u}_{i\hbox{--} 1},{u}_i,{u}_{i+1}\right)\\ {}x(0)=0\left(\mathrm{Anfangsbedingung}\right)\\ {}\mathrm{Outputgleichung}:{y}_i=y\left({x}_i\right)\end{array}} $$

Jeder zelluläre Automat kann auf ein nichtlineares dynamisches System abgebildet werden, dessen Attraktoren genau die damit verbundene Wahrheitswerttafel N = 0, 1, 2, 3, … , 255 kodieren. Funktion f modelliert die zeitabhängige Zustandsveränderung und ist durch eine skalare gewöhnliche Differenzialgleichung folgender Form definiert:

$$ \dot{x}=g\left({x}_i\right)+w\left({u}_{i\hbox{--} 1},{u}_i,{u}_{i+1}\right)\ \mathrm{mit}\ g\ \left({x}_i\right)\triangleq {x}_i+\left|{x}_i+1\left|\hbox{--} \right|{x}_i\hbox{--} 1\right|. $$

Es gibt viele Möglichkeiten nichtlinearer Basisfunktionen für g(xi) und w(ui–1, ui, ui+1). Wir wählen die Funktion |x| = x absoluter Werte für positive Zahlen x und |x| = –x für negative Zahlen x als nichtlineare Basisfunktion, weil damit die resultierende Gleichung in einer optimalen kompakten Form ausgedrückt werden kann. Daraus kann die Lösung der Zustandsgleichung in einer expliziten Form abgeleitet werden. Die Skalarfunktion w(ui–1, ui, ui+1) kann als zusammengesetzte Funktion w(σ) einer einzigen Variablen σ ≜ b1 ui–1 + b2 ui + b3 ui+1 mit w(σ) ≜ {z2 ± |[z1 ± |zo + σ |]|} gewählt werden. Mit dieser Funktion lässt sich die entsprechende Differenzialgleichung definieren, um die Wahrheitswerttafeln von allen 256 Booleschen Würfeln zu erzeugen. Daher entspricht jede Regel eines zellulären Automaten einer besonderen Menge von sechs reellen Zahlen { zo, z1, z2; b1, b2, b3} und zwei ganzen Zahlen ± 1. Nur acht Bits werden benötigt, um eindeutig die Differenzialgleichung zu bestimmen, die mit jeder Regel N eines zellulären Automaten verbunden ist.

Es lässt sich beweisen, dass, sobald die Parameter, die eine besondere Regel N definieren, spezifiziert sind, für jeden der acht Inputs ui–1, ui und ui+1, die in der entsprechenden Wahrheitswerttafel von N aufgelistet sind, die Lösung xi der skalaren Differenzialgleichung entweder monoton vom Anfangszustand xi = 0 zu einem positiven Gleichgewichtswert $$ \overline{x_i} $$ (n) ≥ 1, der deshalb Attraktor Q+(n) genannt wird, wächst oder monoton zu einem negativen Gleichgewichtszustand $$ \overline{x_i} $$ (n) ≤ –1, der deshalb Attraktor Q–(n) genannt wird, abnimmt, wenn der Input (ui–1, ui, ui+1) aus den Koordinaten der Ecke n des entsprechenden Booleschen Würfels oder dazu äquivalent aus der Reihe n der entsprechenden Wahrheitswerttafel für n = 0, 1, 2, … , 7 gewählt wird (Chua et al. 2002). Die Ecke n ist rot gefärbt, wenn ihr Gleichgewichtswert $$ \overline{x_i} $$ (n) ≥ 1 ist, und blau, wenn $$ \overline{x_i} $$ (n) ≤ –1 ist. Dann ist die Farbe aller acht Ecken für den entsprechenden Booleschen Würfel eindeutig durch die Gleichgewichtslösungen der acht entsprechenden Differenzialgleichungen spezifiziert.

In Allgemeinen lässt sich zusammenfassen: Sobald die Parameter der Regel eines zellulären Automaten spezifiziert sind, wird die entsprechende Wahrheitswerttafel oder der entsprechende Boolesche Würfel durch die skalare Differenzialgleichung alleine eindeutig erzeugt. Falls die Outputgleichung des dynamischen Systems yi = y(xi) ≜ $$ \frac{1}{2} $$ (|xi + 1| – | xi – 1|) lautet, dann ist yi = +1, wenn xi ≥ 1 ist, und yi = –1, wenn xi ≤ –1 ist. Der Output eines stationären Zustands im Gleichgewicht ist explizit gegeben durch die Formel yi = sgn {w(σ)} für jede Funktion w(σ) ≜ w(ui–1, ui, ui+1) mit Signumfunktion sgn (x) = +1 für positive Zahlen x, sgn (x) = –1 für negative Zahlen x und sgn (0) = 0. Für den besonderen Wert w(σ) in Abb. 5 ist der Output (Farbe) im Gleichgewicht explizit gegeben durch den
Abb. 5

Zelluläre Automaten mit Regeln 2, 110, 150, 232 als dynamische Systeme. Die Anfangsbedingung ist x (0) = 0. (Mainzer und Chua 2011, Abb. 2.4)

$$ \mathrm{Attraktor}-\mathrm{Farbkode}:{y}_i=\operatorname{sgn}\left\{{z}_2\pm \mid \right[{z}_1\pm \mid {z}_o+\sigma \left|\Big]\right|\Big\}. $$

Abb. 5 zeigt vier Beispiele dynamischer Systeme und die Regeln, die sie kodieren. Jede Regel ist durch ihre Regelnummer N = 0, 1, 2, … , 255 gekennzeichnet. Die Wahrheitswerttafel jeder Regel N wird durch das entsprechende dynamische System erzeugt, das im oberen Teil des Quadranten definiert ist. Dadurch ist bewiesen, dass jedes dynamische System und die Regel des zellulären Automaten, die es kodieren, ein und dasselbe sind. Die Wahrheitswerttafel jeder Regel in Abb. 5 ist in einem Format mit nur $$ {2}^{2^3} $$ = 256 verschiedenen 1x3 Nachbarmustern besetzt. Jedes Farbbild besteht aus 30 x 61 Pixeln, die durch einen 1-dimensionalen zellulären Automaten mit 61 Zellen und einer Randbedingung mit einer speziellen Regel N erzeugt werden.

Als Beispiel wird nun eine Regel aus Abb. 4 (Regel 110) untersucht, die sich später als einfachste universelle Turingmaschine herausstellt. Mit ihrer Differenzialgleichung können σ = b1 ui–1 + b2 ui + b3 ui+1 mit b1 = 1, b2 = 2 und b3 = –3 und w(σ) ≜ {z2 ± |[z1 ± |zo + σ |]|} mit z2 = –2, z1 = 0 und zo = –1 identifiziert werden. Daher ist der Attraktor-Farbkode explizit durch yi = sgn[–2 + |ui–1 + 2ui – 3ui+1 – 1)|] gegeben.

2.3 Digitale Dynamik mit Differenzengleichungen

Die Dynamik eines dynamischen Systems wird durch stetige Differenzialgleichungen modelliert. Um die Dynamik durch digitale zelluläre Automaten zu berechnen, muss ein Programm eine „do loop“ (Schleifen)-Instruktion benutzen, die den Output $$ {y}_i^t $$ jeder Zelle bei der Iteration t zurück zu ihren Inputs führt, um den Output $$ {y}_i^{t+1} $$ bei der nächsten Iteration t+1 zu erhalten. Mit den Hochindizes t und t+1 als Iterationszahlen von Eins bis zur nächsten Generation lässt sich jede Regel N explizit in Form einer nichtlinearen Differenzengleichung ausdrücken mit
$$ {u}_i^{\left(t+1\right)}=\operatorname{sgn}\left\{{z}_2+{c}_2|\right)\left[{z}_1+{c}_1\mid \left({z}_o+{b}_1{u}_{\left(i-1\right)}^t+{b}_2{u}_i^t+{b}_3{u}_{\left(i+1\right)}^t\right)\mid \right]\mid \Big\}, $$
wobei die acht Parameter { zo, z1, z2; b1, b2, b3; c1, c2 } für jede Regel gegeben sind. Daher lässt sich als erstes Hauptresultat festhalten, dass jeder der 256 1-dimensionalen zellulären Automaten, den Stephen Wolfram experimentell im Computerexperiment untersucht hatte, durch eine einzige skalare nichtlineare Differenzialgleichung oder eine entsprechende nichtlineare Differenzengleichung mit maximal acht Parametern erzeugt werden kann. Diese Gleichungen ermöglichen es auch, alle universellen zellulären Automaten im Sinn einer universellen Turingmaschine (UTM) systematisch zu bestimmen. Ein Beispiel ist Regel 110 (Chua et alt. 2003). Für Regel 110 (Abb. 6) erhalten wir $$ {u}_i^{t+1} $$ = sgn (–2+| $$ {u}_{i\hbox{--} 1}^t $$ + 2 $$ {u}_i^t $$ – 3 $$ {u}_{i+1}^t $$–1|). Diese Art der Differenzengleichung kann mit elementaren Kenntnissen in basaler Mathematik verstanden werden. Gleichwohl erklärt sie wesentliche Eigenschaften der nichtlinearen Dynamik.
Abb. 6

Zellulärer Automat als dynamisches System mit Differenzengleichung. (Mainzer und Chua 2011, Abb. 2.5)

3 Komplexität zellulärer Automaten

Die farbigen Würfel enthalten alle Informationen über die komplexe Dynamik von zellulären Automaten. Ein großer Vorteil der Booleschen Würfel ist die Möglichkeit, mit ihrer geometrischen Darstellung einen Index der Komplexität zu definieren (Chua et al. 2002). Jeder der 256 Würfel ist anschaulich durch verschiedene Cluster von roten oder blauen Ecken charakterisiert, die durch parallele Ebenen separiert werden können. Analytisch können die separierenden Ebenen im Koordinatensystem der Booleschen Würfel definiert werden. Der Komplexitätsindex eines zellulären Automaten mit lokaler Regel N ist dann durch die minimale Anzahl von parallelen Ebenen definiert, die notwendig sind, um die roten Ecken des entsprechenden Booleschen Würfels N von den blauen Ecken zu trennen. Abb. 7 zeigt drei Beispiele von Booleschen Würfeln für die drei möglichen Komplexitätsindizes κ = 1, 2, 3 mit einer, zwei oder drei separierenden parallelen Ebenen. Es gibt 104 lokale Regeln mit Komplexitätsindex κ = 1. Ähnlich gibt es 126 lokale Regeln mit Komplexitätsindex κ = 2 und nur 26 lokale Regeln mit Komplexitätsindex κ = 3. Diese analytisch begründeten Komplexitätsindizes sind von dem von Wolfram vorgeschlagenen Komplexitätsindex zu unterscheiden, der nur auf phänomenologischen Eigenschaften von beobachteten Mustern beruht.

3.1 Komplexitätsindex von zellulären Automaten

Im Zusammenhang mit farbigen Würfeln von zellulären Automaten bezieht sich Separabilität auf die Anzahl paralleler Ebenen, mit denen die Würfelecken in gleichfarbige Cluster separiert werden. Für z. B. Regel 110 lassen sich zwei separierende parallele Ebenen des entsprechenden farbigen Würfels einführen, die in Abb. 7b durch zwei verschiedene Farben unterschiedenen werden: Die roten Ecken 2 und 6 liegen oberhalb einer gelben Ebene. Die blauen Ecken 0, 4 und 7 liegen zwischen der gelben und einer leicht bläulichen Ebene. Die roten Ecken 3, 1 und 5 liegen unterhalb der leicht bläulichen Ebene. Es ist bekannt, dass der zelluläre Automat der Regel 110 einer der wenigen Typen der 256 Automaten ist, die universelle Turingmaschinen sind. Im Sinn von Wolframs Klasse 3 von Computerexperimenten werden sehr komplexe Muster erzeugt (Wolfram 2002).
Abb. 7

Beispiele für die Komplexitätsindezes κ = 1, 2, 3 mit parallelen Ebenen, die alle Ecken einer Farbe von solchen einer verschiedenen Farbe separieren für Regel 232 (a), Regel 110 (b) und Regel 150 (c). (Mainzer und Chua 2011, Abb. 3.1)

Beispiel eines Automaten, der nur sehr einfache Muster erzeugen kann, ist Regel 232. Es gibt nur eine separierende Ebene, die den entsprechenden Booleschen Würfel zerschneidet, um farbige Punkte zu trennen (Abb. 7a): Rote Ecken 3, 5, 6 und 7 liegen oberhalb einer leicht bläulichen Ebene. Die blauen Ecken 0, 1, 2 und 4 liegen unterhalb der leicht blauen Ebene. Ein farbiger Boolescher Würfel mit drei parallelen separierenden Ebenen wird in Abb. 7c gezeigt. Er stellt den zellulären Automaten der Regel 150 dar: Die blaue Ecke 6 liegt oberhalb einer grünen Ebene. Die roten Ecken 2, 4 und 7 liegen zwischen einer gelben Ebene und einer grünen Ebene. Die blauen Ecken 0, 3 und 5 liegen zwischen der gelben Ebene und einer leicht blauen Ebene. Die blaue Ecke 1 liegt unterhalb der leicht blauen Ebene. Es ist offensichtlich unmöglich, die 8 Ecken in drei farbige Cluster zu separieren und sie gleichzeitig durch zwei parallele Ebenen zu trennen, ganz gleich wie die Ebenen positioniert werden.

Eine Regel, deren farbige Ecken durch nur eine Ebene getrennt werden, heißt linear separierbar. Eine Prüfung der 256 Booleschen Würfel zeigt, dass 104 von ihnen linear separierbar sind. Die verbleibenden 152 Regeln sind nichtlinear separierbar. Jede Regel kann durch verschiedene Anzahlen von parallelen Ebenen separiert werden. Im Allgemeinen gibt es eine einzige ganze Zahl κ als Komplexitätsindex von Regel N, mit der die geometrische Struktur des entsprechenden Booleschen Würfels charakterisiert wird, nämlich die minimale Anzahl von parallelen Ebenen, die notwendig sind, um die farbigen Ecken zu trennen. Alle linear separierbaren Regeln haben einen Komplexitätsindex κ = 1. Eine Analyse der verbleibenden 152 linear nicht-separierbaren Regeln zeigt, dass sie einen Komplexitätsindex von entweder 2 oder 3 hat. So hat z. B. Regel 110 einen Komplexitätsindex κ = 2, während Regel 150 einen Komplexitätsindex κ = 3 hat. Keine Regel mit Komplexitätsindex κ = 1 ist in der Lage, komplexe Muster zu erzeugen, sogar nicht für zufällige Anfangsbedingungen. Die Emergenz von komplexen Phänomenen hängt signifikant von einem Komplexitätsindex von mindestens κ = 2 ab. In diesem Sinn kann der Komplexitätsindex 2 als Schwellenwert für die Komplexität 1-dimensionaler zellulärer Automaten betrachtet werden.

3.2 Berechenbarkeitskomplexität und universelle Berechenbarkeit

Eine weitere Motivation zur Einführung eines Komplexitätsindex ist die Komplexität von Berechnungen. Die Klasse von zellulären Automaten mit Komplexitätsindex κ = 2 enthält Beispiele mit universeller Berechnung (z. B. N = 110). Allerdings sind die lokalen Regeln mit Komplexitätsindex κ = 1 zu universellen Berechnungen nicht in der Lage. Daraus folgt, dass κ = 2 auch ein Schwellenwert für Berechenbarkeitskomplexität ist.

Universelle Berechenbarkeit ist ein bemerkenswertes Konzept der Berechenbarkeitskomplexität, das auf Alan Turings universelle Rechenmaschine (Turing 1936) zurückgeht. Universelle zelluläre Automaten sind seit Conways Spiel des Lebens (Martin 1994; Rendell 2002) bekannt. Eine universelle Turingmaschine kann per Definition jede Turingmaschine simulieren. Nach der Church-Turing These kann jeder Algorithmus oder jede effektive Prozedur durch eine Turingmaschine realisiert werden. Hier kommt Turings bekanntes Halteproblem zur Anwendung. Nach diesem Beweis gibt es keinen Algorithmus, der für ein beliebiges Computerprogramm und eine beliebige Anfangsbedingung entscheiden kann, ob es irgendwann stoppt oder nicht. (Ein Computerprogramm kann nicht stoppen, wenn es einer geschlossenen Schleife folgen muss.) Daraus folgt für ein System mit universeller Berechenbarkeit (im Sinn einer universellen Turingmaschine), dass nicht voraussagbar ist, ob es irgendwann stoppen wird oder nicht. Nehmen wir an, dass das möglich wäre. Dann könnten wir im Fall einer universellen Turingmaschine auch entscheiden, ob irgendeine Turingmaschine (die durch die universelle Maschine simuliert werden kann) anhalten würde oder nicht. Das ist aber ein Widerspruch zu Turings Resultat des Halteproblems. Daher sind Systeme mit universeller Berechenbarkeit nicht voraussagbar.

Unvoraussagbarkeit ist offenbar ein hoher Grad von Komplexität. Es ist überraschend, dass Systeme mit einfachen Verhaltensregeln wie zelluläre Automaten zu komplexer Dynamik führen, die nicht mehr voraussagbar ist. Es stellt sich die Frage, ob solche unvoraussagbaren Automaten auch in der Natur existieren.

4 Symmetrie im Universum zellulärer Automaten

Ein äußerer Überblick über die diskreten Entwicklungen der 256 lokalen Regeln zeigt einige Ähnlichkeiten und teilweise Symmetrie unter den erzeugten Mustern. Das erinnert an mehr oder weniger zufällige Beobachtungen in den Naturwissenschaften, die nach gemeinsamen mathematischen Erklärungen mit grundlegenden Gesetzen verlangen. Die Vereinigungstheorie der Physik beruht auf der Annahme fundamentaler mathematischer Symmetrien (Mainzer 1996, 2005). Unter dieser Annahme hat sich die Vielfalt und Komplexität natürlicher Phänomene aus wenigen Symmetrieprinzipien entwickelt. Sie sind der „Heilige Gral“ des Universums, nach dem viele Wissenschaftler und Forschungsgruppen gesucht haben. Für das Universum der zellulären Automaten befinden sich die fundamentalen Symmetrien in der Gallerie der Booleschen Würfel (Chua et al. 2004).

4.1 Lokale Äquivalenz von zellulären Automaten

Die Booleschen Würfel von vielen verschiedenen Paaren von lokalen Regeln beziehen sich auf passende Symmetrietransformationen. Ein Beispiel ist die Komplementierung der Farben der Würfelecken der Regeln 145 und 110. Ihre entwickelten Muster sind so verschieden, dass es unmöglich scheint, sie aufeinander zu beziehen. Was steht hinter dieser Vielfalt? Im Fall der Regeln 145 und 110 werden die entsprechenden Booleschen Würfel durch eine „rote ↔ blaue Ecken-Transformation“ aufeinander bezogen. Sie wird als lokale Komplementierungsoperation TC bezeichnet, weil die Komplementierung lokal beschränkt ist. Intuitiv mag man erwarten, dass ihre entsprechenden Entwicklungsmuster durch eine globale Komplementrierungsoperation aufeinander bezogen sein müssen. Diese Intuition trifft aber beim Vergleich von zwei Entwicklungsmuster im Allgemeinen nicht zu (Abb. 8). Sie trifft nur in einem lokalen Sinn mit Bezug auf spezielle Iterationen zu. Wenn man beispielsweise mit demselben Anfangsmuster (einzelner roter zentraler Pixel) in der ersten Reihe startet, dann findet man, dass der Output (erste Iteration) von Regel 145 tatsächlich das Komplement von demjenigen von Regel 110 ist, nämlich zwei blaue Pixel für 145 und zwei rote Pixel für 110 an den entsprechenden Stellen links vom Zentrum. Alle anderen Pixel an entsprechenden Stellen sind auch gegenseitige Komplemente.
Abb. 8

Die Entwicklungen der Regeln 110 und 145 zeigen nur eine lokale Komplement-Beziehung in der ersten Iteration. Demgegenüber zeigen 110 und 137 eine globale Symmetrie- Beziehung. (Mainzer und Chua 2011, Abb. 4.1)

Allerdings liefert die nächste Iteration (Reihe 3) nach Regeln 145 und 110 in Abb. 8 keine gegenseitigen Komplemente. Der Grund ist, dass anders als der Anfangsinput $$ {u}_i^0 $$, i = 0, 1, 2, … , n, der für beide 145 und 110 derselbe ist, der nächste Input $$ {u}_i^1 $$, i = 0, 1, 2, … , n (für t = 1 in Reihe 2), der zur Auffindung der nächsten Iteration (Reihe 3) benötigt wird, verschieden ist und es keinen Grund gibt, dass die Outputs $$ {u}_i^2 $$ (for t = 2) an verschiedenen entsprechenden Stellen das gegenseitige Komplement sind. In diesen Fällen ist ein Paar von lokalen Regeln nur äquivalent im lokalen Sinn von „lokal in der Iterationzeit“ und nicht lokal im üblichen Sinn einer räumlichen Nachbarschaft.

Die entsprechende Definition lautet:

Lokale Äquivalenz: Zwei lokale Regeln N und N’ heißen lokal äquivalent unter einer Transformation T : N → N’ genau dann, wenn der Output $$ {u}_i^1 $$ von N nach einer Iteration von jedem anfänglichen Inputmuster $$ {u}_i^0 $$ gefunden werden kann durch Anwendung des transformierten Inputs T($$ {u}_i^0 $$) auf Regel N’ und dann gefolgt von der Anwendung der inversen Transformation T–1 : N’ → N auf $$ {u}_i^1 $$.

4.2 Globale Äquivalenz von zellulären Automaten

Globale Aspekte können in den Entwicklungsmustern für die Regeln 110, 137 (Abb. 8), 124 und 193 (Abb. 9) gefunden werden. Obwohl die betreffenden Booleschen Würfel dieser drei Regeln nicht aufeinander bezogen zu sein scheinen, sind ihre Outputmuster so präzise aufeinander bezogen, dass sich die Entwicklungsmuster für alle Zeitpunkte t jeder der lokalen Regeln 110, 124, 137, und 193 voraussagen lässt. Beispielsweise kann man das erzeugte Outputmuster der Regel 124 durch eine Spiegelung des Musters nach der Regel 110 entlang der zentralen Geraden erhalten, d. h. als bilaterale Transformation. Den Output der Regel 193 lässt sich durch Anwendung des Komplements von $$ {u}_i^0 $$ (vgl. die blauen zentralen Pixels inmitten eines roten Hintergrunds) auf Regel 110 erzeugen und dann durch Bildung des Komplements des Entwicklungsmusters von 110. Den Output der Regel 137 ergibt sich durch Wiederholung des oben beschriebenen Algorithmus für Regel 193 und dann gefolgt durch eine Spiegelung entlang der zentralen Geraden. Es lässt sich beweisen, dass diese Algorithmen für alle anfänglichen Inputmuster gültig bleiben. Dieses Resultat ist höchst bemerkenswert, weil es erlaubt, die Entwicklungsmuster aus beliebigen Anfangskonfigurationen von drei Regeln für alle Iterationen vorauszusagen und nicht nur für eine Iteration wie im Fall lokaler Äquivalenz.
Abb. 9

Die Entwicklungen der Regeln 110, 124, 193 zeigen globale symmetrische Beziehungen. (Mainzer und Chua 2011, Abb. 4.2)

Die entsprechend Definition lautet allgemein:

Globale Äquivalenz: Zwei lokale Regeln N und N’ heißen global äquivalent unter einer Transformation T : N → N’ genau dann, wenn der Output $$ {u}_i^t $$ von N für jedes t durch Anwendung des transformierten Inputs T($$ {u}_i^0 $$) auf die lokale Regel N’ gefunden werden kann, gefolgt von einer Anwendung der inversen Transformation T–1 : N’ → N auf $$ {u}_i^1 $$ für jedes t = 1, 2, … .

Die vier Regeln 110, 124, 137 und 193 sind global äquivalent in dem Sinn, dass die Entwicklungsmuster von jeweils drei Regeln dieser Klasse aus der vierten Regel für alle Iterationen vorausgesagt werden können. Daher haben diese vier Regeln identische nicht lineare Dynamik für alle anfänglichen Inputmuster. Sie repräsentieren nur eine einzige Entwicklungsregel und bilden in diesem Sinn eine Äquivalenzklasse. Diese globale Eigenschaft ist nicht nur wahr für vier Regeln, sondern auch für alle Regeln. Danach lassen sich die 256 Regeln in 88 globale Äquivalenzklassen einteilen. Es erweist sich als zweckmäßig, diese Äquivalenzklassen mit dem Symbol $$ {\varepsilon}_m^{\kappa } $$ zu unterscheiden, wobei κ der Komplexitätsindex und m die Nummer der Äquivalenzklasse sind. Es gibt 38 zelluläre Automaten, die zu den Äquivalenzklassen $$ {\varepsilon}_m^1 $$ mit Komplexitätsindex κ = 1 und m = 1, 2, … , 38 gehören. Die Äquivalenzklassen $$ {\varepsilon}_m^2 $$ mit Komplexitätsindex κ = 2 werden mit m = 1, 2, … , 41 unterschieden. Ferner gibt es neun globale Äquivalenzklassen mit Komplexitätsindex κ = 3. Sie werden durch $$ {\varepsilon}_m^3 $$ mit m = 1, 2, … , 9 unterschieden.

Diese Result ist bedeutsam, weil es zeigt, dass man nur gründlich die Dynamik und das langfristige Verhalten der 88 repräsentativen lokalen Regeln studieren muss. Zudem haben 38 dieser 88 dynamisch verschiedenen Regeln den Komplexitätsindex κ = 1 und sind daher trivial. Es bleiben also nur 50 lokale Regeln (41 Regel mit κ = 2 und 9 Regel mit κ = 3), die einer weiteren gründlichen Untersuchung bedürfen.

4.3 Symmetrie mit globalen Transformationen

Es lässt sich beweisen, dass jede lokale Regel zu einer globalen Äquivalenzklasse gehört, die durch bestimmte globale Transformationen definiert ist. Es gibt drei globale Transformationen, nämlich globale Komplementierung $$ \overline{\mathbf{T}} $$, links-rechts Komplementierung T⋆ und links-rechts Transformation T†, die als Symmetrietransformationen im Universum der zellulären Automaten aufgefasst werden können. Die vier Regeln 110, 124, 137 und 193 sind global äquivalent zueinander in dem Sinn, dass ihre langfristige Dynamik (für t → ∞) mathematisch identisch ist mit Bezug auf die drei globalen Transformationen T†, T⋆ und $$ \overline{\mathbf{T}} $$.Die anschauliche Bedeutung dieser Symmetrietransformationen wird in Abb. 10 deutlich. Alle vier Muster der Regeln 110, 124, 137 und 193 haben in diesem Bild 60 Reihen, die den Iterationsnummern t = 0, 1, 2, …, 59 entsprechen, and 61 Spalten, die den 61 Zellen (n = 60) entsprechen. Alle Muster haben eine zufällige Anfangsbedingung (t = 0) oder ihre Spiegelung, Komplementierung oder beides. Die zwei Muster 124 und 110 oben werden durch eine links-rechts Transformation T† erzeugt und sind durch eine bilaterale Spiegelung an einer imaginären vertikalen Linie zwischen den zwei Mustern aufeinander bezogen. Die zwei Muster 193 und 137 unten sind ebenso durch T† aufeinander bezogen und zeigen dieselbe bilaterale Spiegelungssymmetrie. Die zwei vertikal situierten lokalen Regeln 137 und 110, ebenso wie 193 und 124 sind durch eine globale Komplementierung $$ \overline{\mathbf{T}} $$ aufeinander bezogen. Die zwei diagonal situierten lokalen Regeln 124 und 137, ebenso wie 193 und 110 sind durch eine links-rechts Komplementierung T⋆ aufeinander bezogen.
Abb. 10

Globale Äquivalenz von Regeln 110, 124, 137 und 193. (Mainzer und Chua 2011, Abb. 4.3)

Die geometrische Definition dieser Symmetrietransformationen ist leicht zu verstehen und kann mit Hilfe der Würfel zellulärer Automaten veranschaulicht werden. Mathematisch werden diese Transformationen durch 3 x 3 Matrizen $$ {\overline{\mathbf{T}}}_{\boldsymbol{u}} $$, $$ {\mathbf{T}}_{\boldsymbol{u}}^{\boldsymbol{\star}} $$, and $$ {\mathbf{T}}_{\boldsymbol{u}}^{\dagger } $$ definiert. Jede der drei Matrizen transformiert die drei Axen (ui–1, ui, ui+1), die durch das Zentrum des Booleschen Würfels gezeichnet sind, in ein Tripel von Axen ($$ {u}_{i\hbox{--} 1}^{'} $$, $$ {u}_i^{'} $$, $$ {u}_{i+1}^{'} $$). Diese Repräsentationen mit Matrizen benötigen zur Berechnung nur basale Mathematik. Eine analytische Definition ist in Mainzer und Chua 2011 gegeben.

4.4 Global Symmetrie der Kleinschen Vierergruppe V

Die drei globalen Transformationen T†, T⋆ und $$ \overline{\mathbf{T}} $$ werden durch Elemente der klassischen nichtzyklischen 4-elementigen Abelschen Gruppe V erzeugt, die als „Vierergruppe“ nach dem Mathematiker Felix Klein benannt ist (Speiser 1956). Die vier Elemente von V werden durch die 3 x 3 Matrizen T0, $$ {\overline{\mathbf{T}}}_{\boldsymbol{u}} $$, $$ {\mathbf{T}}_{\boldsymbol{u}}^{\boldsymbol{\star}} $$ und $$ {\mathbf{T}}_{\boldsymbol{u}}^{\dagger } $$ dargestellt. Das Symbol T0 bezeichnet die Identität oder Einheitsmatrix für jede Dimension. Die tatsächlichen Transformationen, die es ermöglichen, die langfristigen Korrelationen unter den Elementen von jeder der 88 globalen Äquivalenzklassen aller 256 zellulären Automaten zu bestimmen, sind jedoch die 4 x 4 Matrizen T0, T†, T⋆ und $$ \overline{\mathbf{T}} $$. Abb. 11 zeigt, dass sie durch die Gruppenmultiplikationstafel der Kleinschen Vierergruppe V aufeinander bezogen sind. Diese Symmetriegruppe ist die einzige abstrakte mathematische Gruppe, die es möglich macht, die langfristigen Korrelationen innerhalb aller Elemente der vier Regeln 110, 124, 137 und 193 vorauszusagen.
Abb. 11

Globale Symmetrie und Kleinsche Vierergruppe. (Mainzer und Chua 2011, Abb. 4.7)

Diese Resultate sind global im Sinn von asymptotischem Zeitverhalten t →∞. Damit zeigt sich: Obwohl es 256 verschiedene lokale Regeln 1-dimensionaler zellulärer Automaten gibt, ergeben sich nur 88 verschiedene globale Verhaltensweisen. Das ist ein fundamentales Ergebnis, das durch die Identifikation von 88 globalen Äquivalenzklassen $$ {\varepsilon}_m^{\kappa } $$ vorausgesagt werden kann.

4.5 Der heilige Gral von Symmetrie und Berechenbarkeit

Da für die lokale Regel 110 universelle Berechenbarkeit nachgewiesen wurde, folgt, dass alle vier lokalen Regeln der Vierergruppe V universelle Turingmaschinen sind. Die fundamentale Bedeutung des Universalitätsresultats besteht darin, die Symmetrie der Booleschen Würfel zu nutzen, um Äquivalenzklassen unter den 256 Regeln zu identifizieren. Die Entdeckung der Vierergruppe V und die Rotationsgruppe R führten zu den Hauptklassifikationen der 256 lokalen Regeln in 88 globale Äquivalenzklassen $$ {\varepsilon}_m^{\kappa } $$ und 30 lokale Äquivalenzklassen $$ {S}_m^{\kappa } $$ . Die Bedeutung der 88 globalen Äquivalenzklassen $$ {\varepsilon}_m^{\kappa } $$ ist ähnlich zur Klassifikation von Algorithmen in verschiedene Komplexitätsklassen (wie z. B. N- oder NP-Klassen) in dem Sinn, dass jede Eigenschaft, die auf ein Element von $$ {\varepsilon}_m^{\kappa } $$ zutrifft, auch auf die anderen Elemente in derselben globalen Äquivalenzklasse zutrifft.

Die Universalität der vier Regeln 110, 124, 137 und 193 und ihr identisches langfristiges dynamisches Verhalten mit Bezug auf die Symmetrietransformationen der Vierergruppe V sind in dem kommutative Diagramm von Abb. 12 dargestellt. Daher repräsentiert die Kleinsche Vierergruppe das fundamentale Symmetriegesetz der 256 1-dimensionalen zellulären Automaten. Es ist der „Heilige Gral“ einer Vereinigungstheorie (unified theory) im Universum der zellulären Automaten, die alle Information ihrer nichtlinearen Dynamik enthält.
Abb. 12

Universelle Symmetrie und Berechenbarkeit im Universum zellulärer Automaten. (Mainzer und Chua 2011, Abb. 4.9)

5 Ausblick of ein berechenbares Universum dynamischer Systeme

1-dimensionale zelluläre Automaten mit L = I+1 Zellen sind komplexe Systeme mit nicht linearer Dynamik (Alligood et al. 1996; Mainzer 2009; Shilnikov et al. 2001), die durch eine der 256 lokalen Regeln N bestimmt sind. Ihre Zustandsräume enthalten alle verschiedene Zustände der zellulären Reihen ($$ {x}_0^t $$, … , $$ {x}_{I\hbox{--} 1}^t $$, $$ {x}_I^t $$) im Schritt t der Zeit (Iteration oder Generation). Eine ganze Liste von nachfolgenden Reihen mit keinen identischen Reihen und ausgehend von der Anfangskonfiguration wird Orbit im Zustandsraum eines zellulären Automaten genannt. Auf diesem Hintergrund kann auch die Attraktordynamik komplexer Systeme im Rahmen der Theorie zellulärer Automaten untersucht werden (Mainzer und Chua 2011).

Das sind erste Schritte, das Universum als einen Automaten und ein dynamisches System zu verstehen. Der Erfolg dieses Forschungsprogramms hängt von der Digitalisierung der Physik ab. Die Frage „Ist das Universum ein Computer“ führt zu der Frage: Wie weit ist es möglich, die Gesetz der Physik auf berechenbare digitale Physik abzubilden? (Deutsch 1985) Digitalisierung ist nicht nur spannend zur Beantwortung philosophischer Fragen des Universums. Digitalisierung ist das Schlüsselparadigma moderner Forschung und Technologie. Nahezu alle Arten von Forschung und technischer Innovation hängen von computer-gestützter Modellierung ab. Die entstehende Komplexität von Natur und Gesellschaft kann ohne Computer mit wachsender Rechen- und Speicherkapazität nicht beherrscht werden.

Um diese komplexe digitale Welt besser verständlich und anschaulich zu machen, eignen sich zelluläre Automaten als vereinfachte Approximationen. Der hier erklärte analytische Zugang zeigt bereits wesentliche Prinzipien nichtlinearer Dynamik, wie wir sie in der Expansion des Universums und der Evolution des Lebens finden. Die Emergenz neuer Strukturen und Muster hängt von Phasenübergängen komplexer dynamischer Systeme in der Welt der Quanten, Molekülen, Zellen, Organismen und der ökologischen und sozialen Systeme ab (Mainzer 2007). Zelluläre Automaten erweisen sich als ein anschauliches Paradigma der Modellierung komplexer dynamischer Systeme mit vielen zweckmäßigen Anwendungen (Hoekstra et al. 2010). In zellulären Automaten führen sehr einfache lokale Wechselwirkungsregel von Zellen zur Emergenz von komplexen globalen Strukturen. Dieses lokale Prinzip der Aktivität trifft ebenfalls zu in der Welt der komplexen Systeme mit Elementarteilchen, Atomen, Molekülen, Zellen, Organen, Organismen, Populationen und sozialen Systemen (Mainzer und Chua 2013). Obwohl lokale Wechselwirkungen eine komplexe Vielfalt von Entitäten im Universum erzeugen, lassen sie sich mathematisch auf wenige fundamentale Symmetriegesetze reduzieren. Symmetrien spielen eine Schlüsselrolle in der physikalischen Welt ebenso wie im Universum der Automaten.