沃爾夫勒姆規則110

Wolfram的規則110是Stephen Wolfram「基本」規則分類中的一個卓越的一維細胞自動機。這個線性網格中的每個單元格可以處於兩種狀態之一：0（關）或1（開）。每一步，下一行單元格通過查看當前行的三元組來確定——每個單元格加上它的兩個鄰居。哪些三元組在下一代產生1的模式由二進制數110編碼。

儘管定義極簡——只有幾個位元描述哪些局部排列變為「開」——規則110展示了令人難以置信的豐富和複雜的行為。在某些初始條件下，它已被證明是圖靈完備的，與理論上可以執行通用計算的系統相當。

運作原理 →

規則

在基本細胞自動機術語中，十進制規則號110對應於從「111」三元組到「000」讀取時的位元模式01101110。這意味著某些三元組（如110、101、011、001）在下一代產生活細胞，而其他則產生死細胞。

儘管命名約定簡單，出現的行為可能令人驚訝地複雜。您會看到由這些簡單三元組規則驅動的混沌區域、重複模式和各種相互作用。

湧現與複雜性

規則110最有趣的方面之一是單行位元如何演化成看起來像移動粒子、碰撞或波前的結構。初始行的微小變化可以極大地改變展開的圖案，突顯了系統對初始條件的敏感性。這種湧現的複雜性純粹來自局部相互作用——不需要中央協調。

在某些配置中，您會看到穩定區域、「Glider」以及重複或混沌的擴展，這強調了系統的深度。研究人員廣泛研究了這個自動機，以理解簡單的確定性系統如何可能表現出看似隨機或至少計算上不可約的模式。

圖靈完備性

規則110可以配置為計算通用圖靈機能計算的任何東西，使其圖靈完備。這意味著如果您以正確的方式設置初始行，理論上可以在這個小自動機內模擬邏輯運算、記憶體和任何基本計算元素。這是一個令人印象深刻的演示，表明即使從最簡單的規則集中也能產生複雜性——隨著時間的推移，重複的局部相互作用產生強大的行為。

演算法概述

下面是計算每個新行的簡單方法。我們可選地包裝邊緣，使一側的單元格可以看到另一側的鄰居。如果禁用此功能，網格外的邊緣被視為「死亡」：

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

以下是我們在每次更新時如何應用它（雖然我們的最終實現使用位元移位方法，但此表是哪些三元組產生活細胞的替代表達）：

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