ウルフラム・コード

ウルフラム・コード (英: Wolfram code) は、広く使用されている1次元のセル・オートマトン規則の番号付けルールである。この番号付けは、1983年のスティーブン・ウルフラムの論文で導入され、著書A New Kind of Scienceで一般化された。

定義

ウルフラム・コードは、オートマトンの各セルの新しい状態をその近傍の状態の関数として指定するテーブルが、S-進数のk-桁の数字として解釈できるという観察に基づいている。ここで、

• S はオートマトンの各セルが持つことのできる状態の数、
• k = S^2n + 1 は近傍の状態の総数 、
• nは近傍の半径

とする。従って、特定のルールのウルフラム・コードは、0 から S^{S2n + 1} − 1 の範囲であり、S-aryから10進数表記に変換される。その計算は以下の通りである。

1. セルの近傍 2n + 1 セル分の状態は、全部で S^2n + 1 通りある。これをすべてリストする。
2. 各状態 S 進数との数値として解釈し、数値の降順に並べ替える。
3. 各状態について、繊維ルールに基づいて、次のイテレーションにおけるセルの状態を計算し、リストする。
4. 得られた状態のリストを再び S 進数の数値として解釈し、この数を10進数に変換する。この結果の10進数がウルフラム・コードである。

ウルフラム・コードは、近傍のサイズ・形状も、状態の数も指定していない。これらは、文脈から既知であると仮定されている。そのような文脈なしに使われて場合は、コードは初等セル・オートマトンを指すものと想定されることが多い。すなわち、2状態1次元3近傍セル・オートマトンである。ウルフラムは彼の著書で広範囲に調査している。このクラスの注目すべきルール番号には、ルール30、ルール110、ルール184がある。ルール90も2を法とするパスカルの三角形を形成するため興味深い。「ルール37R」のように末尾に「R」が付いたこのタイプのコードは、同じ近傍構造を持つ二次セル・オートマトンを示す。

厳密には、有効範囲内のすべてのウルフラム・コードは異なる規則を定義しているが、これらの規則のいくつかは同型であり、通常は同値なものと見做される。たとえば、上記のルール110は、124、137、193と同型であり、これらは元のルールから、左右反転と、状態の再番号付けによって取得できる。慣例では、そのような各同型クラスは、コード番号が最も小さいルールによって表される。ウルフラム表記、特に10進表記の欠点は、同型が他の表記法に比べて分かりにくくなることである。それにもかかわらず、ウルフラム・コードは、1次元セル・オートマトンを参照するデファクトスタンダードになっている。

例

ここでは1次元2状態3近傍セルオートマトンの例を示す。

計算手順のステップ1	現在の状態	111	110	101	100	011	010	001	000
ステップ2	二進数として解釈 (ソート順)	7	6	5	4	3	2	1	0
ステップ3	中央のセルの次の状態	0	0	0	1	1	1	1	0

この表を二段目の「二進数として解釈 (ソート順)」に記載の数字が降順になるように各列を並び替える（この表ではすでに降順に並んでいるので、そのままでよい）。並び替えた後の表で、三段目の「中央のセルの次の状態」のデータを並べた0、0、0、1、1、1、1、0を2進数 と解釈し、10進数に変換すると、30である。従って、この規則はルール30と呼ばれる。

一般化セル・オートマトン

一般化して、D-次元空間で、近傍サイズが nであり、各セルの状態数が S であるようなセル・オートマトンを考える。この時、可能なルールの総数は、

R=S^S(2n+1)D

で与えられる。

もっとも一般的な例は S = 2、n = 1、D = 1の場合で、ルールの総数は R = 256 となる。可能なルールの総数は、系の次元に大きく依存する。例えば、空間の次元 (D) を1から2に増加すると、ルールの総数は、256から2⁵¹²に増加する (これはおよそ1.341×10¹⁵⁴である) 。