Zellularautomat

ZellularautomatIn den Vierziger- und Fünfzigerjahren des 20. Jahrhunderts wurden durch John von Neumann und Alan Turing die Anfänge der Automatentheorie geschaffen. Von Interesse sind dabei vor allem die Zellularautomaten, in denen einzelne Zellen wegen gewisser Regeln und dem Zustand ihrer Nachbarn „leben“ bzw. „sterben“.
Ein berühmtes Beispiel dafür ist Conways „Game of Life“.

In diesem Unterprogramm simuliert das Programm acht verschiedene eindimensionale, lineare, binäre Automaten.

Diese bestehen aus einer Reihe von Zellen, die jeweils den Zustand 0 oder 1 annehmen können. Von einer Anfangskonfiguration ausgehend, sterben bzw. leben die Zellen je gewähltem Automaten in Abhängigkeit von drei, fünf, sieben oder neun Nachbarn, mit Zufallsbelegung oder nicht.

RegelsystemZur Erläuterung sei der Zellularautomat mit drei Nachbarn gewählt. Die jeweils drei nebeneinander liegenden Zellen beeinflussen die mittlere der drei Zellen für die nächste Generation, in der Darstellung also eine Zeile tiefer.

In der Darstellung würden die Belegungen der Zellen A, B und C damit über die Zelle B entscheiden. Eine Regel (Übergang von der Eltern- zur Kindgeneration) könnte zum Beispiel besagen, dass B‚ nur dann den Zustand 1 hat, wenn alle drei Elternzellen gesetzt sind.

Für drei Nachbarn gibt es insgesamt 23 mögliche Übergänge und damit 28 = 256 verschiedene Bildungsregeln.
Interessiert man sich nur für Regeln, die weder links noch rechts bevorzugen, verbleiben noch 32. Kodiert man die acht wichtigen Übergänge

111 → a 110 → b 101 → c 100 → d
011 → e 010 → f 001 → g 000 → h

und kodiert man diese acht Variablen nach Wolfram mit einer Codezahl C = 128a + 64b + 32c + 16d + 8e + 4f + 2g + h, so ergeben sich Codierungen C im Bereich von 0 bis 255. Für die Darstellung des Wolfram-Dreiecks ist C = 150, für das Sierpinski-Dreieck C = 90.

Geben Sie unter Zellen 3 ein, können Sie damit eine Codierung im genannten Bereich eingeben und nach Betätigung des Schalters Darstellung deren Wirkung nachvollziehen. Ausgangspunkt ist jeweils eine lebende Zelle in der Mitte der Darstellung. Möchten Sie, dass mit einer Zufallsbelegung der ersten Generation begonnen wird, so setzen Sie die Markierung im Feld keine Einzelzelle verwenden. Wählen Sie das Feld Zufallszelle, wird je Generation (Zeile) eine weitere Zelle zufällig auf den Status „lebend“ gesetzt.

Außer drei Zellen können Sie auch fünf, sieben oder neun eingeben. Andere Eingaben werden automatisch korrigiert.

Zellularautomaten mit fünf Nachbarn sind für Codierungen <= 64 interessant; mit sieben und mehr Nachbarn <=255. Interessante Beispiele erhalten Sie für Zellularautomaten mit fünf wirkenden Nachbarn bei zufälliger Belegung der Startzeile:

  • Homogen: 0, 16, 32, 36, 48
  • Periodisch: 8, 24, 40, 56, 58
  • Fraktal: 6, 10, 12, 14, 18
  • Komplex quasiperiodisch: 20, 52

Außer den genannten Codierungen sind zum Beispiel folgende Zahlenwerte interessant:

  • Zellularautomat mit 3 Nachbarn: 30, 45, 50, 54, 57, 60, 73, 75, 105, 107, 110, 126, 129, 131, 135, 137, 150, 151, 153, 169, 182, 183, 193
  • Zellularautomat mit 3 Nachbarn (erste Zeile zufällig): 0, 9, 15, 18, 22, 26
  • Zellularautomat mit 5 Nachbarn (erste Zeile zufällig): 0, 2, 5, 9, 10, 12, 17, 18, 20-23, 25
  • Zellularautomat mit 7 Nachbarn (erste Zeile zufällig): 0, 2, 9, 17, 20, 25, 34, 36, 49
  • Zellularautomat mit 9 Nachbarn (erste Zeile zufällig): 0, 2, 9, 10, 17, 21, 25, 36, 43, 52, 53