ウルフラムのルール110

Wolframのルール110は、Stephen Wolframの「初等」ルール分類に含まれる注目すべき一次元セルオートマトンです。この線形グリッドの各セルは、0（オフ）または1（オン）の2つの状態のいずれかを取ります。各ステップで、次の行のセルは現在の行の三つ組（各セルとその2つの近傍セル）を見て決定されます。どの三つ組が次の世代で1を生成するかのパターンは、二進数110によってエンコードされています。

その最小限の定義（どの局所配置が「オン」になるかを記述するわずかなビット）にもかかわらず、ルール110は驚くほど豊かで複雑な挙動を示します。特定の初期条件下ではチューリング完全であることが証明されており、理論上は普遍的な計算を実行できるシステムと同等です。

仕組み →

ルール

初等セルオートマトンの用語では、10進数のルール番号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;
}