ウルフラム・コード

ウルフラム・コード (英: 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 次元 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¹⁵⁴ である) 。