Reguła 110 Wolframa

Reguła 110 Wolframa to niezwykły jednowymiarowy automat komórkowy z klasyfikacji „elementarnych" reguł Stephena Wolframa. Każda komórka w tej liniowej siatce może znajdować się w jednym z dwóch stanów: 0 (wyłączona) lub 1 (włączona). W każdym kroku następny wiersz komórek jest określany poprzez analizę trójek w bieżącym wierszu — każda komórka plus jej dwaj sąsiedzi. Wzorzec określający, które trójki produkują 1 w następnej generacji, jest zakodowany przez liczbę binarną 110.

Pomimo minimalnej definicji — zaledwie kilka bitów opisujących, które lokalne układy stają się „włączone" — Reguła 110 demonstruje niezwykle bogate i złożone zachowanie. Udowodniono nawet, że jest Turing-zupełna przy określonych warunkach początkowych, co stawia ją na równi z systemami zdolnymi teoretycznie do wykonywania uniwersalnych obliczeń.

Jak to działa →

Reguła

W terminologii elementarnych automatów komórkowych dziesiętny numer reguły 110 odpowiada wzorcowi bitowemu 01101110, gdy czytamy od trójki '111' w dół do '000'. Oznacza to, że pewne trójki (jak 110, 101, 011, 001) dają żywą komórkę w następnej generacji, podczas gdy inne dają martwą komórkę.

Pomimo prostej konwencji nazewnictwa, zachowania które się wyłaniają, mogą być zaskakująco złożone. Zobaczysz chaotyczne regiony, powtarzające się wzorce i wszelkiego rodzaju interakcje napędzane przez te proste reguły trójkowe.

Emergencja i złożoność

Jednym z najbardziej intrygujących aspektów Reguły 110 jest to, jak pojedynczy wiersz bitów może ewoluować w struktury przypominające poruszające się cząstki, kolizje lub fronty falowe. Drobne zmiany w początkowym wierszu mogą drastycznie zmienić rozwijający się wzór, podkreślając wrażliwość systemu na warunki początkowe. Ta emergentna złożoność powstaje wyłącznie z lokalnych interakcji - nie jest wymagana żadna centralna koordynacja.

W niektórych konfiguracjach można zaobserwować stabilne regiony, glajdery oraz powtarzające się lub chaotyczne rozszerzenia, które podkreślają głębię systemu. Badacze intensywnie studiowali ten automat, aby zrozumieć, jak proste systemy deterministyczne mogą wykazywać wzorce, które wydają się losowe lub są przynajmniej obliczeniowo nieredukowalne.

Zupełność Turinga

Reguła 110 może być skonfigurowana do obliczania wszystkiego, co potrafi uniwersalna maszyna Turinga, co czyni ją zupełną w sensie Turinga. Oznacza to, że jeśli ustawisz początkowy wiersz we właściwy sposób, możesz teoretycznie emulować operacje logiczne, pamięć i każdy podstawowy element obliczeniowy w tym małym automacie.

Przegląd algorytmu

Poniżej przedstawiono proste podejście do obliczania każdego nowego wiersza. Opcjonalnie zawijamy krawędzie, aby komórki po jednej stronie mogły widzieć sąsiadów po przeciwnej stronie. Jeśli ta opcja jest wyłączona, krawędzie są traktowane jako „martwe" poza siatką:

// 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
};

A oto jak stosujemy to podczas każdej aktualizacji (chociaż nasza ostateczna implementacja używa podejścia z przesunięciem bitowym, ta tabela jest alternatywnym wyrażeniem tego, które trójki dają żywą komórkę):

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;
}