Regel 30

Regel 30 ({{Modul:Vorlage:lang}} Modul:Vorlage:lang:103: attempt to index field 'wikibase' (a nil value)) ist ein eindimensionaler zellulärer Automat, der 1983 von Stephen Wolfram entdeckt wurde.<ref>Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2</ref> Die Regel legt fest, wie sich der Zustand einer bestimmten Zelle in einem eindimensionalen Gitter verändert (schwarz oder weiß). Werden viele Ausführungen der Regel untereinander abgetragen, entsteht ein für die Regel typisches zweidimensionales Muster (siehe Abbildung unten). Nach Wolframs Klassifikationsschema gehört dieser zelluläre Automat der „Klasse 3“ an, was bedeutet, dass er nichtperiodisches, chaotisches Verhalten zeigt.

Beschreibung[Bearbeiten]

Definition[Bearbeiten]

Die vorrangig von Stephen Wolfram untersuchten elementaren zellulären Automaten bestehen aus einem unendlich langen, eindimensionalen Gitter aus Zellen. Diese Zellen können den Zustand 0 (weiß) oder 1 (schwarz) annehmen. Zu Beginn wird die Konfiguration der Zellen festgelegt, z. B. eine einzelne schwarze Zelle. In jedem folgenden Zeitschritt wird auf die einzelnen Zellen eine Regel angewandt, die bestimmt, ob die Zelle im nächsten Schritt schwarz oder weiß ist. Dabei hängt der jeweils nächste Zustand von der Zelle selbst und von ihrer linken und rechten Nachbarzelle ab. Eine Regel muss deshalb <math>2^3 = 8</math> mögliche Zellkombinationen definieren, z. B. 010 (die Zelle ist schwarz, linker und rechter Nachbar sind weiß):

Aktueller Zustand von linkem Nachbar, Zelle und rechtem Nachbar	111	110	101	100	011	010	001	000
Neuer Zustand der betrachteten Zelle	0	0	0	1	1	1	1	0

Jeder der acht Möglichkeiten (000 bis 111) kann ein beliebiger Zustand 0 oder 1 zugewiesen werden. Insgesamt gibt es daher <math>2^8 = 256</math> elementare zelluläre Automaten. Ihre Benennung erfolgt nach dem von Wolfram aufgestellten Schema, indem man die acht nebeneinander geschriebenen Zustände als eine Binärzahl liest, z. B. 00011110, die entsprechende Dezimalzahl ergibt den Namen des elementaren Automaten (in diesem Fall 30).

Ihr Spiegelbild, Komplement und komplementäres Spiegelbild sind die Regeln 86 (01010110), 135 (10000111) und 149 (10010101).

Das folgende Diagramm zeigt die Hintereinanderausführung der Regel, wobei zu Beginn nur eine einzige Zelle schwarz und alle anderen weiß gefärbt sind. Die vertikale Achse beschreibt die Zeit und jede horizontale Linie zeigt den Zustand der Zellen zu einem bestimmten Zeitschritt.

Hintereinanderausführung der Regel 30, die Zeitschritte verlaufen vertikal.

Eigenschaften des Musters[Bearbeiten]

Datei:CA rule30s.png

Nach einer Berechnung von sehr vielen Schritten ergibt sich das typische Muster.

Vor allem zwei Strukturen sind zu erkennen: Das häufige Auftreten weißer Dreiecke und das regelmäßige gestreifte Muster auf der linken Seite. Die Anzahl der schwarzen Zellen zu einem bestimmten Zeitpunkt <math>n</math> beschreibt die Folge

<math>1,3,3,6,4,9,5,12,7,12,11,14,12,19,13,22,15,19</math> (Sequenz Folge A070952 in OEIS)

und ist ungefähr gleich <math>n</math>.

Chaos[Bearbeiten]

Die Regel 30 scheint nicht nur aus optischen Gründen chaotisch, sondern sie erfüllt auch die mathematischen Bedingungen an Chaos:

Sie hängt hochsensibel von den Anfangswerten ab. Das heißt, dass zwei geringfügig verschiedene Anfangskonfigurationen sich sehr schnell auseinanderentwickeln (divergieren).
Alle periodischen Konfigurationen sind zusammen eine dichte Teilmenge der Menge aller Konfigurationen.
Sie ist topologisch transitiv auf der Menge aller Konfigurationen (sie wirbelt die Konfigurationen durcheinander).

Weblinks[Bearbeiten]

Commons: Regel 30 – Sammlung von Bildern, Videos und Audiodateien

Eric W. Weisstein: Rule 30. In: MathWorld (englisch).
Regel 30 in Wolfram's Atlas of Cellular Automata (englisch)

Einzelnachweise[Bearbeiten]