Diploide Zellularautomaten

Zellularautomaten sind ein untereinander verbundenes Netz von einzelnen Zellen, die strengen Regeln folgen und sich untereinander in unmittelbaren Nachbarschaft beeinflussen. Hier werden elementare Zellularautomaten betrachtet, die zuerst von Stephen Wolfram beschrieben wurden. Es handelt sich dabei um einen 1-dimensionales Feld von Zellen, die den Zustand AN (1) oder AUS (0) annehmen können. Die Nachbarschaft einer Zelle ist dabei die Zelle selbst, sowie die links und die rechts davon.

Außerdem werden periodische Randbedingungen angenommen, das heißt die Zelle „links“ von der ersten Zelle ist die Zelle ganz rechts und umgekehrt. Die Regel, die die Automaten befolgen, kann man als Funktion f: {0,1}³ → {0,1} verstehen. f(x, y, z) würde dabei angeben, welchen Zustand die Zelle annehmen würde, wenn ihre Nachbarn zuvor die Zustände x, y und z hatten. Das „updaten“ der einzelnen Zellen erfolgt dabei synchron, das heißt um den nächsten Zeitschritt t+1 zu erhalten, wird für jede Zelle die Übergangsfunktion f mit dem Zustand der Nachbarn zum Zeitpunkt t berechnet.

Manchmal werden ECA als Bild betrachtet, wobei die x-Achse den Raum darstellt und die y-Achse die Zeit; demnach entsprechen die verschiedenen Bildzeilen unterschiedlichen Zeitpunkten:

Fig. 1: ECA Regel 102 mit 80 Zellen über 160 Zeiteinheiten simuliert

Hierbei ist auch leicht die periodische Randbedingung erkennbar: was links den Rahmen des Bildes verlässt, kommt auf der rechten Seite wieder rein. Auch auffallend ist die Komplexität, die sich nach gewisser Zeit entwickelt: anfangs ist nur eine einzige Zelle 1, aber nach kurzer Zeit breitet sich die Struktur nach links aus und formiert dabei verschieden große Dreieckstrukturen.

Regel-Nummern

In Fig. 1 ist der ECA mit der Regel 102 abgebildet – aber wie genau wird die Regel auf die Übergangsfunktion f abgebildet? Bei den ECA ist die Regel eine Ganzzahl zwischen 0 und 255. Interpretiert man sie als Binärzahl, so steht jede Stelle für eine mögliche Nachbarschaft und den Folgezustand, den die Zelle dann annimmt.

Fig. 2: Die Regelzahl als 8-bit Binärzahl gibt die einzelnen Übergangsfunktionswerte an

Um arithmetisch also für eine gegebene Nachbarschaft x, y, z den Funktionswert zu errechnen, kann man sich der bit-shift-Operation bedienen:

f(x, y, z) = rule_number >> (x * 2² + y * 2¹ + z * 2⁰)

Diploide ECA

Während die bis dahin betrachteten ECA streng deterministisch waren (also keine Wahlmöglichkeiten bezüglich des Übergangs offen ließen), sind stochastische ECA vom Zufall abhängig: die Funktionswerte der Übergangsfunktion sind keine konkreten 1 oder 0-Werte mehr, sondern Wahrscheinlichkeiten zwischen 0 und 1. Eine Konsequenz ist, dass eine einfache Ganzzahl nicht mehr ausreicht, um diese ECA zu beschreiben, denn es gibt so viel mehr Möglichkeiten.

Dieser Post handelt von einer bestimmten Art von stochastischen ECA: die sogenannten diploiden Zellularautomaten wurden von Nazim Fatès im Paper Diploid Cellular Automata: First Experiments on the Random Mixtures of Two Elementary Rules genauer beschrieben. Der Titel verrät schon viel über die Funktionsweise der diploiden ECA: sie werden aus zwei „normalen“ ECA zusammengemixt, das heißt bei jedem Übergang wird zufällig zwischen zwei deterministischen ECA-Regeln ausgewählt und diese dann angewandt.

Man schreibt dann (f₁, f₂)[λ], wobei f₁ die Regel des ersten ECA und f₂ die Regel des zweiten ECA ist. Das λ bezeichnet das Mischverhältnis: es ist eine reelle Zahl zwischen 0 und 1, die die Wahrscheinlichkeit angibt, dass f₁ ausgewählt wird.

Es folgt eine interaktive Anwendung zur Visualisierung von diploiden ECA.








Mehr über das Verhalten von diploiden Automaten sowie eine detaillierte Erklärung zu den Äquivalenzklassen von elementaren Zellularautomaten kann man in meiner Ausarbeitung zu dem Thema nachlesen, die im Rahmen eines Proseminars im Sommersemester 2020 entstanden ist.

Kommentare

Um einen Kommentar hinzuzufügen, schreibe eine E-Mail mittels dieses Links.