Über zelluläre Automaten | Spiel des Lebens, Regel 30, Regel 110 & mehr

Die vier Grundbestandteile

Jeder zelluläre Automat besteht aus denselben vier Teilen. Das Raster ist der Raum, in dem die Zellen leben. Es kann eine eindimensionale Linie sein, eine zweidimensionale Ebene wie ein Schachbrett oder sogar ein dreidimensionaler Raum. Die Zustände sind das, was eine Zelle sein kann. Im einfachsten Fall ist eine Zelle binär: Schwarz oder Weiß, 1 oder 0. Die Nachbarschaft ist die Menge der Zellen, die eine Zelle direkt beeinflussen. Auf einem quadratischen Raster ist das meist die Moore-Nachbarschaft, alle acht umliegenden Zellen, oder die Von-Neumann-Nachbarschaft, nur Norden, Osten, Süden und Westen. Die Regeln sind das Gehirn des Automaten: die Logik, die jeder Zelle ihren neuen Zustand gibt. Zum Beispiel: Wenn ich lebe, aber weniger als zwei lebende Nachbarn habe, sterbe ich an Einsamkeit. Jede Zelle wendet im selben Moment dieselben Regeln an.

1. Conways Spiel des Lebens

Regeln: B3/S23. Eine lebende Zelle überlebt mit 2 oder 3 lebenden Nachbarn. Eine tote Zelle wird mit genau 3 lebendig. Jede andere Zelle ist in der nächsten Generation tot. John Conway entwarf es 1970, und Martin Gardners Kolumne in Scientific American machte es berühmt. Es erzeugt Gleiter, Oszillatoren und Raumschiffe. Bill Gosper fand im selben Jahr die erste Gleiterkanone: ein Muster, das alle 30 Generationen einen neuen Gleiter abfeuert, für immer. Das Spiel des Lebens kann Berechnungen ausführen, denn Gleiter können Signale tragen und wie Logikgatter zusammenstoßen. Vor allem zeigt es, wie komplexes Verhalten aus einfachen Regeln wächst.

Gosper-Gleiterkanone im Spiel des Lebens, die einen diagonalen Strom von Gleitern abfeuert — Gosper-Gleiterkanone nach 330 Generationen. Erstellt in PictorX.

2. Regel 30

Typ: ein eindimensionaler elementarer zellulärer Automat. Der nächste Zustand jeder Zelle hängt von ihr selbst und ihren beiden Nachbarn ab, und jede Generation wird als neue Zeile unter der letzten gezeichnet. Stephen Wolfram stellte Regel 30 im Jahr 1983 vor. Beginnt man mit einer einzigen schwarzen Zelle, wächst daraus ein chaotisches Dreieck. Trotz ihrer deterministischen Regel wirkt sie zufällig, so zufällig, dass ihre mittlere Spalte als Pseudozufallszahlengenerator genutzt wurde. Dieselbe Art von Dreiecken zeigt sich im Pigment der Schale der Meeresschnecke Conus textile.

Dreieck der Regel 30, aus einer einzigen schwarzen Zelle gewachsen, rechts chaotisch und links gestreift — Regel 30 aus einer schwarzen Zelle, 224 Generationen. Erstellt in PictorX.

3. Regel 110

Typ: ein eindimensionaler elementarer zellulärer Automat wie Regel 30, mit einer anderen Tabelle aus acht Antworten. Regel 110 ist nachweislich berechnungsuniversell: Matthew Cook zeigte, dass sie mit einer passenden ersten Zeile jede Berechnung nachbilden kann, die ein Universalcomputer ausführen kann. Sie trägt bewegliche Strukturen, die über einen sich wiederholenden Hintergrund wandern und miteinander wechselwirken, wenn sie sich treffen. Diese Zusammenstöße nutzt der Beweis als seine Logik. Regel 110 zeigt, wie sehr einfache Regeln beliebige Berechnungen nachbilden können.

Regel 110, aus einer Zelle rechts gewachsen, breitet sich in verschachtelten Dreiecken nach links aus — Regel 110 aus einer schwarzen Zelle am rechten Rand. Erstellt in PictorX.

4. Brian's Brain

Zustände: aus, an (feuernd) und refraktär. Regeln: Eine ausgeschaltete Zelle schaltet sich ein, wenn genau 2 Nachbarn an sind. Eine eingeschaltete Zelle wird refraktär. Eine refraktäre Zelle schaltet sich aus. Brian Silverman hat diesen Automaten entworfen. Weil eine Zelle nach dem Feuern eine Generation lang ruhen muss, bewegt sich jeder Impuls immer weiter von dort weg, wo er schon war. Das Ergebnis ist ein Gewimmel selbstfahrender Muster, das Wellen in erregbaren Medien wie Nervengewebe oder Herzmuskel ähnelt und oft lebendig und organisch wirkt.

Brian's Brain breitet sich von einem zufälligen Fleck aus, feuernde Zellen in Gelb und verblassende Spuren in Violett — Brian's Brain 70 Generationen nach einem zufälligen Fleck, mit verblassenden Spuren. Erstellt in PictorX.

5. Wireworld

Zustände: leer, Elektronenkopf, Elektronenschwanz und Leiter. Regeln: Ein Kopf wird zum Schwanz, ein Schwanz wird zum Leiter, und ein Leiter wird zum Kopf, wenn genau 1 oder 2 seiner Nachbarn Köpfe sind. Leere Zellen bleiben leer. Brian Silverman entwarf 1987 auch Wireworld. Leiterzellen sind Drähte, und ein Kopf mit einem Schwanz dahinter ist ein Elektron, das an ihnen entlangläuft. Wireworld kann elektronische Schaltungen simulieren: Eine Drahtschleife mit einem Elektron ist ein Taktgeber, eine kleine Kerbe ist eine Diode, und wenige Zellen ergeben ein Logikgatter. Darin wurden vollständige Computer gebaut, etwa der Wireworld-Computer von David Moore und Mark Owen, der Primzahlen berechnet.

Wireworld-Schaltung mit zwei Taktschleifen, zwei Dioden und einem XOR-Gatter, Elektronen in Blau und Rot auf gelbem Draht — Zwei Taktgeber, zwei Dioden und ein XOR-Gatter in Wireworld. Erstellt in PictorX.

Wolframs 256 Regeln und vier Klassen

Eine eindimensionale Zelle mit zwei Nachbarn sieht eines von acht Mustern, von 111 bis 000. Eine Regel legt für jedes davon den neuen Zustand fest, besteht also aus acht Bits, und es gibt 2⁸ = 256 elementare Regeln. Liest man die acht Antworten als Binärzahl, erhält man den Namen der Regel: Regel 30 ist 00011110, und Regel 110 ist 01101110. Stephen Wolfram ordnete die Regeln nach ihrem Verhalten, von Ordnung bis Chaos. 1. Klasse 1 endet in einem einheitlichen Zustand. 2. Klasse 2 endet in stabilen oder sich wiederholenden Strukturen. 3. Klasse 3 bleibt chaotisch und wirkt zufällig, wie Regel 30. 4. Klasse 4 baut Strukturen, die sich bewegen und miteinander wechselwirken, an der Grenze zwischen Ordnung und Chaos, wie Regel 110.

Rangliste nach Schwierigkeit

Spiel des Lebens ★☆☆☆☆ · Regel 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regel 110 ★★★★★. Die ersten beiden erklären sich beim Zusehen von selbst. Regel 110 versteckt ihre beweglichen Strukturen in einem sich wiederholenden Hintergrund.

Optisch am schönsten

1. Brian's Brain · 2. Conways Spiel des Lebens · 3. Regel 30 · 4. Regel 110 · 5. Wireworld.

Mathematisch am wichtigsten

1. Regel 110, wegen der Universalität · 2. Spiel des Lebens, wegen Universalität und Emergenz · 3. Regel 30, wegen Chaos und Zufälligkeit · 4. Wireworld, wegen digitaler Logik · 5. Brian's Brain, wegen erregbarer Systeme.

In Natur, Physik und Kryptografie

Zelluläre Automaten werden genutzt, um komplexe Systeme in Natur, Physik und Kryptografie zu simulieren. Die Idee geht auf Stanisław Ulam und John von Neumann in den 1940er-Jahren zurück, die mit einem Raster aus Zellen eine Maschine entwarfen, die sich selbst kopieren kann. In der realen Welt sieht man zelluläre Automaten im Pigment mancher Schalen, etwa bei Conus textile, deren Dreiecke wie Regel 30 aussehen, und in den Schuppen der Perleidechse, die nach einer Regel nahe an einem zellulären Automaten zwischen Grün und Schwarz wechseln. Physiker nutzen sie, um Gasströmungen, Sandhaufen und Waldbrände zu modellieren. Die scheinbare Zufälligkeit von Regel 30 machte sie zu einem Kandidaten für Zufallszahlengeneratoren und Stromchiffren.

Entdecken Sie sie in PictorX

Öffnen Sie Zelluläre Automaten, um alle fünf laufen zu lassen. Sehen Sie der Gleiterkanone zu, einer Flotte von Raumschiffen oder dem R-Pentomino, das 1.103 Generationen braucht, bis es zur Ruhe kommt. Geben Sie eine beliebige Regel im Stil des Spiels des Lebens wie B36/S23 ein oder eine beliebige elementare Regelnummer von 0 bis 255. Zeichnen und radieren Sie Zellen, schicken Sie Elektronen durch die Wireworld-Schaltungen, verbinden Sie die Ränder und wechseln Sie in den bunten Modus. Speichern Sie ein PNG oder öffnen Sie die Leinwand im PictorX-Editor.

Häufig gestellte Fragen

Was ist ein zellulärer Automat?

Ein Raster aus Zellen, in dem jede Zelle einen Zustand hat. Bei jedem Takt werden alle Zellen gemeinsam nach einer festen Regel aktualisiert, die nur eine Zelle und ihre Nachbarn betrachtet. Trotz der einfachen Regeln können die Muster komplex und unvorhersehbar sein.

Wer hat zelluläre Automaten erfunden?

Stanisław Ulam und John von Neumann, in den 1940er-Jahren in Los Alamos. John Conways Spiel des Lebens (1970) machte die Idee populär, und Stephen Wolfram untersuchte in den 1980er-Jahren die 256 elementaren Regeln.

Welche zellulären Automaten sind Turing-vollständig?

Von den fünf hier sind Regel 110 und das Spiel des Lebens nachweislich universell, und Wireworld kann einen vollständigen Computer aufnehmen. Universell heißt, dass sie mit dem richtigen Startmuster jede Berechnung ausführen können, die ein Universalcomputer ausführen kann.

Was sind Wolframs vier Klassen?

Klasse 1 erstarrt in einem einheitlichen Zustand, Klasse 2 kommt in stabilen oder sich wiederholenden Strukturen zur Ruhe, Klasse 3 bleibt chaotisch wie Regel 30, und Klasse 4 baut bewegliche, wechselwirkende Strukturen wie Regel 110.

Warum wirkt Regel 30 zufällig?

Jeder Schritt steht fest, aber jede Zelle mischt ihren linken Nachbarn so mit den anderen beiden, dass sich kleine Unterschiede schnell ausbreiten. In ihrer mittleren Spalte wurde kein einfaches Muster gefunden, deshalb wurde sie zur Erzeugung von Zufallszahlen genutzt.