Loading AI tools
ウィキペディアから
ルール30は、スティーブン・ウルフラムによって1983年に導入された、1次元セル・オートマトンのルールの1つである[2] 。ウルフラムの分類では、ルール30はカオス状態を表すクラス3に分類される。
ルール30は、単純なルールである一方、複雑で一見無作為なパターンを生成する。そのため、スティーブン・ウルフラムは、ルール30等のセル・オートマトンは、自然界で見られる複雑な構造を生み出すルールがいかにシンプルであるかを理解するための鍵となると考えた。例えば、イモガイの貝殻にルール30が生成する模様と似た模様が現れる。ルール30は Mathematica の乱数生成にも使用されており[3] 、暗号化で用いるストリーム暗号としても提案されている[4]。
ルール30（2進法で00011110）はそのルールを記述する最小のウルフラム・コードであるため、そう名付けられている（後述）。ルール30の内部状態を左右逆にしたもの（鏡像）がルール86（01010110）、状態のビットを反転したものがルール135（10000111）、内部状態を左右逆にし、状態のビットも反転させたものがルール149（10010101）であるが、本質的にはルール30と同じである。
ウルフラムの基本セル・オートマトンでは、各セルの初期配列とルールによって、2状態を持つ無限の1次元配列が考えられる。セル・オートマトンは離散的な時間で考えられ、全てのセルはその現在の状態と左右の状態のみに基づいて同時に状態を変化させる。ルール30の場合、その変化させるルールは次の表で示される。この00011110を十進法に変換すると30であるため、ルール30と呼ばれる。
| 現在の状態 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| 中央のセルの次の状態 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
次のパターンは状態"0"中に状態"1"（黒色）がたった1つだけ存在する初期状態から現れる。
ここでも、縦軸が時間を表す。この構造では、白い逆三角形が頻繁に出現し、左側に縞模様が現れるなどの幾つかの模様が現れる。構造全体をうまく説明するパターンはない。n世代目に存在する状態"1"（黒色）のセルの数は、
となり、およそ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の状態が異なる）という単純な特性によって検証された。[5]
上記の画像でも明らかなように、ルール30は入力が無作為ではなくても見かけ上の乱数を生成する。スティーブン・ウルフラムはその中心の列を擬似乱数生成器として使用することを提案した。多くのランダム性の標準的なテストに合格し、 Wolfram はこのルールを Mathematica で乱数を生成するために使っている。ルール30は多くの入力パターンに対してランダムなパターンを生成するが、反復パターンを生成する入力パターンもまた無限に存在する。自明な例では、全ての入力が"0"である場合である。それほど自明ではない例には、"00000001000111"を繰り返す入力がある。詳しくは Repeating Rule 30 patterns を参照。
モシェ・シッパーとマルコ・トマッシーニは、ルール30の乱数生成器は、他のセル・オートマトンを用いた乱数生成器と比較して、カイ二乗検定の結果があまり良くないことを示した[6]。また、「ルール30のセル・オートマトンによって得られた比較的悪い結果は、Wolframが考える逐次的な処理ではなく、N個の乱数列を並列で生成したものによるものかもしれない」と懸念を表明した[7]。
北ケンブリッジ駅は、ルール30（もしくはそのビットを反転したルール135）の遷移を示すパネルで装飾されている。このデザインはケンブリッジの数学者ジョン・ホートン・コンウェイが研究したライフゲームに触発された建築家によって行われたが、ライフゲームのルールには基づいていない[8][9]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
