🔲 Wolfram 1D-Zellularautomaten

Ein System ist Turing-vollständig, wenn es jede Berechnung simulieren kann, die ein Universalrechner ausführen kann, sofern genügend Zeit und Speicher vorhanden sind. Matthew Cook bewies 2004 (mit Wolframs Erlaubnis zur Veröffentlichung), dass Regel 110 Turing-vollständig ist, indem er zeigte, dass sie eine spezielle Art universeller Maschine namens zyklisches Tag-System simulieren kann. Das bedeutet, dass Regel 110 — eine eindimensionale Reihe binärer Zellen, aktualisiert durch eine Tabelle von nur 8 Bits — im Prinzip in der Lage ist, jeden Algorithmus auszuführen, was sie zu einem der einfachsten bekannten universellen Rechensubstrate macht.

Regel 184 entspricht direkt dem asymmetrischen einfachen Ausschlussprozess (ASEP), einem Standardmodell des Verkehrsflusses. Jede lebende Zelle steht für ein Fahrzeug, und die Regel bewegt Fahrzeuge um eine Position vorwärts, wenn die Zelle davor leer ist, andernfalls bleiben sie stehen. Dies reproduziert auf natürliche Weise reale Verkehrsphänomene: Bei niedriger Dichte fließen Fahrzeuge mit maximaler Geschwindigkeit frei; oberhalb einer kritischen Dichte breitet sich ein Stau als Welle rückwärts aus, während einzelne Fahrzeuge gelegentlich vorwärtsfahren. Regel 184 wird in Physik und Verkehrswissenschaft als das einfachste diskrete Verkehrsmodell verwendet, das dieses Stauwellenverhalten erfasst.

Regel 30 ist nicht zufällig — sie ist vollständig deterministisch —, aber das Muster, das sie aus einer einzelnen lebenden Zelle erzeugt, ist nachweislich chaotisch und besteht Standard-Zufallstests. Wolfram nutzte die mittlere Spalte von Regel 30 über viele Jahre als Pseudozufallszahlengenerator in Mathematica, und sie wurde als Quelle kryptografischer Zufälligkeit untersucht. Das Muster ist so empfindlich gegenüber Anfangsbedingungen und visuell so unvorhersehbar, dass die Vorhersage zukünftiger Zustände ohne schrittweise Ausführung der Regel als rechnerisch irreduzibel erscheint: Es gibt keine bekannte Abkürzung, die schneller ist, als sie tatsächlich zu simulieren.

Eindimensionale Zellularautomaten wurden erstmals in den frühen 1980er-Jahren von Stephen Wolfram untersucht, der eine systematische computergestützte Untersuchung aller 256 elementaren Regeln durchführte und seine Ergebnisse ab 1983 in einer Reihe von Arbeiten veröffentlichte. Wolfram klassifizierte die Regeln in vier Verhaltensklassen — Fixpunkte, periodische Muster, chaotische Muster und komplexes (Klasse-IV-) Verhalten —, eine Taxonomie, die in der Komplexitätswissenschaft bis heute einflussreich ist. Sein späteres Buch "A New Kind of Science" (2002) erweiterte diese Ideen zu einer großen Theorie, die vorschlägt, dass einfache Regeln die Grundlage aller natürlichen Komplexität sind.

Conways Game of Life ist der berühmteste zweidimensionale Zellularautomat, der eine 3x3-Nachbarschaft statt eines 1x3-Streifens nutzt; er erreicht ebenfalls Turing-Vollständigkeit und erzeugt Gleiter, Oszillatoren und Raumschiffe. Die Sierpinski-Dreieck-Simulation auf dieser Website teilt ihre fraktale Struktur mit Regel 90. Reaktions-Diffusions-Systeme wie das Gray-Scott-Modell erweitern die Idee lokaler musterbildender Regeln auf kontinuierliche Chemie. Zellularautomaten mit größerer Nachbarschaft und totalistische Automaten — bei denen nur die Anzahl lebender Nachbarn zählt — umfassen die Familie mit Brian's Brain und Wireworld, die digitale Logikschaltungen nachbilden können.

Zellularautomaten sind die Grundlage mehrerer praktischer Technologien. Regel 30 und verwandte Automaten wurden als Pseudozufallszahlengeneratoren in Computeralgebrasystemen verwendet. CA-basierte Modelle treiben Strömungssimulationen über Lattice-Boltzmann-Methoden an, die die Navier-Stokes-Gleichungen auf einem Gitter lokaler Kollisionsregeln annähern und in der Aerodynamik- und Mikrofluidikforschung eingesetzt werden. In der Hardware treten CA-Schieberegister in Stromchiffren und fehlerkorrigierenden Codes auf. Forscher haben CA auch genutzt, um sich selbst replizierende robotische Systeme und programmierbare Materie zu entwerfen, inspiriert von von Neumanns theoretischem sich selbst reproduzierendem Automaten aus den 1950er-Jahren.

Aktuelle Forschung untersucht reversible Zellularautomaten, bei denen jede Konfiguration einen eindeutigen Vorgänger hat — relevant für Quantencomputing und thermodynamisch effiziente Berechnung. Es gibt aktive Arbeit an kontinuierlichen Zellularautomaten (SmoothLife und Lenia), die diskrete Regeln auf reellwertige Zustände verallgemeinern und lebensähnliche Organismen erzeugen, die sich bewegen und vermehren. Forscher untersuchen auch CA als Modelle der Raumzeit auf der Planck-Skala und fragen, ob das Universum selbst ein Zellularautomat sein könnte. Im maschinellen Lernen sind faltende neuronale Netze strukturell analog zu CA, und neuronale Zellularautomaten wurden trainiert, um Zielbilder wachsen zu lassen und sich selbst zu reparieren, was ein neues Gebiet eröffnet, das Deep Learning mit dem CA-Paradigma verbindet.