Einfache Regeln, komplexes Verhalten
Elementare zelluläre Automaten gehören zu den einfachstmöglichen Rechensystemen: eine Reihe von Zellen, jede entweder an oder aus, die sich gleichzeitig nach einer lokalen Regel aktualisieren, die nur drei Zellen betrachtet (linker Nachbar, Zelle selbst, rechter Nachbar). Es gibt genau 256 mögliche Regeln, nummeriert von 0 bis 255 nach Stephen Wolframs Namenskonvention. Trotz dieser extremen Einfachheit erzeugen einige dieser Regeln Muster von außergewöhnlicher Komplexität.
Die Wolfram-Klassifikation
Wolfram ordnete die 256 Regeln in vier Verhaltensklassen ein. Klasse-1-Regeln (z.B. Regel 0, Regel 255) kollabieren schnell zu einem einheitlichen Zustand. Klasse-2-Regeln (z.B. Regel 4, Regel 108) erzeugen einfache periodische Muster — Streifen, Dreiecke, sich wiederholende Blöcke. Klasse-3-Regeln (z.B. Regel 30, Regel 90) generieren chaotische, scheinbar zufällige Muster. Klasse-4-Regeln (z.B. Regel 110) befinden sich an der Grenze — sie erzeugen komplexe, langlebige Strukturen, die auf filigrane Weise interagieren.
Wichtige Regeln zum Erkunden
Regel 30 — Das Paradebeispiel für Chaos in zellulären Automaten. Aus einer einzelnen Zelle erzeugt sie ein Muster, das auf der linken Seite zufällig erscheint, rechts aber eine regelmäßige Struktur aufweist. Wolfram nutzte sie als Zufallszahlengenerator.
Regel 90 — Erzeugt das Sierpinski-Dreieck, ein berühmtes Fraktal. Das liegt daran, dass Regel 90 dem XOR der beiden Nachbarn entspricht, und die Binärzeilen des Pascalschen Dreiecks modulo 2 dasselbe Muster erzeugen.
Regel 110 — Nachweislich Turing-vollständig, wie Matthew Cook 2004 bewies. Das bedeutet, dass dieser einfache eindimensionale Automat prinzipiell jede Berechnung durchführen kann — ein tiefgreifendes Ergebnis, das die einfachsten Systeme mit den leistungsfähigsten verbindet.
Emergenz und Berechnung
Zelluläre Automaten demonstrieren ein fundamentales Prinzip: Komplexes globales Verhalten kann aus einfachen lokalen Regeln ohne zentrale Steuerung entstehen. Dieses Prinzip liegt Phänomenen von Kristallwachstum über Staus bis zur Entwicklung biologischer Organismen zugrunde. Die Tatsache, dass Regel 110 berechnungsuniversell ist, legt nahe, dass die Fähigkeit zur Komplexität selbst in den einfachsten Systemen angelegt ist.