Wolframs Regel 110

Wolframs Regel 110 ist ein bemerkenswerter eindimensionaler zellulaerer Automat aus Stephen Wolframs Klassifikation der 'elementaren' Regeln. Jede Zelle in diesem linearen Gitter kann einen von zwei Zustaenden haben: 0 (aus) oder 1 (ein). Mit jedem Schritt wird die naechste Zellenreihe durch Betrachtung von Dreiertupeln in der aktuellen Reihe bestimmt - jede Zelle plus ihre zwei Nachbarn. Das Muster, welche Tripel in der naechsten Generation eine 1 erzeugen, ist durch die Binaerzahl 110 kodiert.

Trotz ihrer minimalen Definition - nur ein paar Bits, die beschreiben, welche lokalen Anordnungen 'ein' werden - zeigt Regel 110 unglaublich reichhaltiges und komplexes Verhalten. Unter bestimmten Anfangsbedingungen wurde bewiesen, dass sie Turing-vollstaendig ist, gleichwertig mit Systemen, die theoretisch universelle Berechnungen durchfuehren koennen.

Wie es funktioniert →

Die Regel

In der Terminologie elementarer zellulaerer Automaten entspricht die dezimale Regelnummer 110 dem Bitmuster 01101110, wenn man von der '111'-Tripel bis zur '000' liest. Das bedeutet, dass bestimmte Tripel (wie 110, 101, 011, 001) in der naechsten Generation eine lebende Zelle erzeugen, waehrend andere tote Zellen ergeben.

Trotz der einfachen Namenskonvention koennen die entstehenden Verhaltensweisen ueberraschend komplex sein. Sie werden chaotische Regionen, sich wiederholende Muster und alle moeglichen Interaktionen sehen, die durch diese einfachen Tripel-Regeln angetrieben werden.

Emergenz & Komplexität

Einer der faszinierendsten Aspekte von Regel 110 ist, wie eine einzelne Reihe von Bits sich zu Strukturen entwickeln kann, die wie bewegende Partikel, Kollisionen oder Wellenfronten aussehen. Winzige Aenderungen in der Anfangsreihe koennen das sich entfaltende Muster drastisch veraendern und die Empfindlichkeit des Systems gegenueber Anfangsbedingungen hervorheben. Diese emergente Komplexitaet entsteht rein aus lokalen Interaktionen - keine zentrale Koordination ist erforderlich.

In bestimmten Konfigurationen werden Sie stabile Regionen, 'Glider' und sich wiederholende oder chaotische Expansionen beobachten, die die Tiefe des Systems unterstreichen. Forscher haben diesen Automaten ausgiebig untersucht, um zu verstehen, wie einfache deterministische Systeme Muster zeigen koennen, die zufaellig erscheinen oder zumindest rechnerisch irreduzibel sind.

Turing-Vollständigkeit

Regel 110 kann so konfiguriert werden, dass sie alles berechnet, was eine universelle Turing-Maschine kann, und ist somit Turing-vollstaendig. Das bedeutet, wenn Sie die Anfangsreihe richtig einrichten, koennen Sie theoretisch logische Operationen, Speicher und jedes grundlegende Rechenelement innerhalb dieses kleinen Automaten emulieren. Es ist eine eindrucksvolle Demonstration dafuer, dass Komplexitaet selbst aus dem einfachsten Regelwerk entstehen kann - es sind die wiederholten lokalen Interaktionen ueber die Zeit, die maechtiges Verhalten hervorbringen.

Algorithmische Übersicht

Nachfolgend ein einfacher Ansatz zur Berechnung jeder neuen Reihe. Wir koennen optional die Raender umschlagen, sodass Zellen auf einer Seite Nachbarn auf der gegenueberliegenden Seite sehen koennen. Wenn dies deaktiviert ist, gelten Raender ausserhalb des Gitters als 'tot':

// Rule 110 transition table - maps each 3-bit pattern to its next state
const transitions = {
  // pattern => next state
  '111': 0,
  '110': 1,
  '101': 1,
  '100': 0,
  '011': 1,
  '010': 1,
  '001': 1,
  '000': 0
};

Und so wenden wir es bei jedem Update an (obwohl unsere finale Implementierung den Bitshift-Ansatz verwendet, ist diese Tabelle eine alternative Darstellung dafuer, welche Tripel eine lebende Zelle erzeugen):

function computeNextRow(currentRow, wrapEdges) {
  const length = currentRow.length;
  const newRow = new Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    const leftIndex  = wrapEdges ? (i - 1 + length) % length : i - 1;
    const rightIndex = wrapEdges ? (i + 1) % length : i + 1;

    const left   = (leftIndex < 0 || leftIndex >= length) ? 0 : currentRow[leftIndex];
    const center = currentRow[i];
    const right  = (rightIndex < 0 || rightIndex >= length) ? 0 : currentRow[rightIndex];

    const pattern = (left << 2) | (center << 1) | right;
    newRow[i] = (110 >> pattern) & 1;
  }
  return newRow;
}