ルール30

ルール30は、スティーブン・ウルフラムによって1983年に導入された、1次元セル・オートマトンのルールの1つである。ウルフラムの分類では、ルール30はカオス状態を表すクラス3に分類される。

ルール30は、単純なルールである一方、複雑で一見無作為なパターンを生成する。そのため、スティーブン・ウルフラムは、ルール30等のセル・オートマトンは、自然界で見られる複雑な構造を生み出すルールがいかにシンプルであるかを理解するための鍵となると考えた。例えば、イモガイの貝殻にルール30が生成する模様と似た模様が現れる。ルール30は Mathematica の乱数生成にも使用されており、暗号化で用いるストリーム暗号としても提案されている。

ルール30（2進法で00011110）はそのルールを記述する最小のウルフラム・コードであるため、そう名付けられている（後述）。ルール30の内部状態を左右逆にしたもの（鏡像）がルール86（01010110）、状態のビットを反転したものがルール135（10000111）、内部状態を左右逆にし、状態のビットも反転させたものがルール149（10010101）であるが、本質的にはルール30と同じである。

ルールセット

ウルフラムの基本セル・オートマトンでは、各セルの初期配列とルールによって、2状態を持つ無限の1次元配列が考えられる。セル・オートマトンは離散的な時間で考えられ、全てのセルはその現在の状態と左右の状態のみに基づいて同時に状態を変化させる。ルール30の場合、その変化させるルールは次の表で示される。この00011110を十進法に変換すると30であるため、ルール30と呼ばれる。

構造と性質

次のパターンは状態"0"中に状態"1"（黒色）がたった1つだけ存在する初期状態から現れる。

ここでも、縦軸が時間を表す。この構造では、白い逆三角形が頻繁に出現し、左側に縞模様が現れるなどの幾つかの模様が現れる。構造全体をうまく説明するパターンはない。n世代目に存在する状態"1"（黒色）のセルの数は、

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... オンライン整数列大辞典の数列 A070952

となり、およそnである。黒マスが生じうる範囲は2n 1であるため、およそ1/2の確率で0と1の状態が生じている。

カオス

スティーブン・ウルフラムは、セル・オートマトンの分類を視覚的な情報に基づいて行い、ルール30は「カオス」に相当するクラス3とした。しかし、ロバート・L. デバニーとクヌードソンによって提案された、より厳密なカオスの定義を満たすことが後に示された。特に、デバニーの基準によればルール30は初期条件の微小な変化に対して大きな変化が生じる初期値敏感性を示し、その周期的な構成はカントールトポロジーによれば全ての空間で密であり、混合的（任意の2つの有限パターンのセルに対して、最終的に他のパターンを含む構成に繋がる1つのパターンを含む構成が存在する）である。クヌードソンの基準によれば、ルール30は敏感な依存性（sensitive dependence）を示し、密な軌道（dense orbit）（任意の有限のセルパターンを形成する初期配置）が存在する。これら2つのルールのカオス的な振る舞いの特徴付けは、ルール30の permutative である（もし2つの配列CとDが、位置iのセルの状態のみ異なるば場合、1ステップ後のi 1の状態が異なる）という単純な特性によって検証された。

応用

乱数生成

上記の画像でも明らかなように、ルール30は入力が無作為ではなくても見かけ上の乱数を生成する。スティーブン・ウルフラムはその中心の列を擬似乱数生成器として使用することを提案した。多くのランダム性の標準的なテストに合格し、 Wolfram はこのルールを Mathematica で乱数を生成するために使っている。ルール30は多くの入力パターンに対してランダムなパターンを生成するが、反復パターンを生成する入力パターンもまた無限に存在する。自明な例では、全ての入力が"0"である場合である。それほど自明ではない例には、"00000001000111"を繰り返す入力がある。詳しくは Repeating Rule 30 patterns を参照。

モシェ・シッパーとマルコ・トマッシーニは、ルール30の乱数生成器は、他のセル・オートマトンを用いた乱数生成器と比較して、カイ二乗検定の結果があまり良くないことを示した。また、「ルール30のセル・オートマトンによって得られた比較的悪い結果は、Wolframが考える逐次的な処理ではなく、N個の乱数列を並列で生成したものによるものかもしれない」と懸念を表明した。

装飾

北ケンブリッジ駅は、ルール30（もしくはそのビットを反転したルール135）の遷移を示すパネルで装飾されている。このデザインはケンブリッジの数学者ジョン・ホートン・コンウェイが研究したライフゲームに触発された建築家によって行われたが、ライフゲームのルールには基づいていない。

参考文献

Wolfram, Stephen, 1985, Cryptography with Cellular Automata, CRYPTO'85.

外部リンク

Weisstein, Eric W. "Rule 30". mathworld.wolfram.com (英語).
Rule 30 in Wolfram's atlas of cellular automata
Rule 30: Wolfram's Pseudo-random Bit Generator. Recipe 32 at David Griffeath's Primordial Soup Kitchen.
Repeating Rule 30 patterns. A list of patterns that, when repeated to fill the cells of a Rule 30 automaton, repeat themselves after finitely many time steps. Frans Faase, 2003. Archived from the Original on 2013-08-08
Paving Mosaic Fractal. Basic introduction to the pattern of Rule 30 from the perspective of a LOGO software expert Olivier Schmidt-Chevalier.
TED Talk from February 2010. Stephen Wolfram speaks about computing a theory of everything where he talks about rule 30 among other things.

30 ニコニコニュースオリジナル