Loading article…
ルール30は、 1983年にスティーブン・ウルフラムによって導入された基本的なセルオートマトンです。 [2]ウルフラムの分類体系を使用すると、ルール30はクラスIIIルールであり、非周期的でカオス的な動作を示します。
このルールは、単純で明確に定義されたルールから複雑で一見ランダムなパターンを生成するため、特に興味深いものです。このため、ウルフラムは、ルール 30、そしてセルオートマトン全般が、単純なルールが自然界で複雑な構造と動作を生み出す仕組みを理解する鍵であると考えています。たとえば、ルール 30 に似たパターンは、広く分布するイモガイの一種Conus textileの殻に現れます。ルール 30 は、 Mathematicaの乱数生成器としても使用されており、[3]暗号化に使用するストリーム暗号として提案されています。[4] [5]
ルール 30 は、ルール セットを記述する最小のWolfram コードが 30 であるため、このように名付けられました(以下に説明)。ルール 30 の鏡像、補集合、鏡像補集合の Wolfram コードは、それぞれ 86、135、149 です。
ルールセット
Wolfram のすべての基本セルオートマトンでは、2 つの状態のみを持つセルオートマトン セルの無限の 1 次元配列が考慮され、各セルは何らかの初期状態にあります。離散的な時間間隔で、各セルは現在の状態と 2 つの隣接セルの状態に基づいて自発的に状態を変更します。ルール 30 の場合、オートマトンが次の状態になるルール セットは次のようになります。
左、中央、右のセルが(p,q,r)と表記されている場合、中央のセルの次の状態に対応する式は、p xor (q or r)と表すことができます。 2 進数では00011110 2 = 30 となるため、これはルール 30 と呼ばれます。
次の図は、作成されたパターンを示しています。セルは、その近傍の以前の状態に基づいて色分けされています。暗い色は「1」を表し、明るい色は「0」を表します。時間は垂直軸に沿って増加します。
構造と特性
次のパターンは、状態 1 (黒で表示) の単一のセルが状態 0 (白で表示) のセルによって囲まれた初期状態から発生します。
ルール30セルオートマトン
ここで、縦軸は時間を表し、画像の水平断面は、パターンの進化の特定の時点での配列内のすべてのセルの状態を表します。この構造には、白い三角形の頻繁な出現や左側の明確な縞模様など、いくつかのモチーフがありますが、構造全体には識別可能なパターンはありません。生成時の黒いセルの数は、シーケンスによって与えられます。
- 1、3、3、6、4、9、5、12、7、12、11、14、12、19、13、22、15、19、...（OEISの配列A070952）
およそ である。[要出典]
カオス
ルール 30 は、 Devaneyと Knudsonが提案した厳密なカオスの定義を満たしています。特に、Devaney の基準によれば、ルール 30 は初期条件に敏感な依存性を示し(少数のセルだけが異なる 2 つの初期構成は急速に分岐します)、その周期構成は構成空間のカントール位相によればすべての構成の空間で密であり(任意の有限のセル パターンで周期構成が存在します)、混合しています(任意の有限のセル パターン 2 つについて、1 つのパターンを含む構成が存在し、最終的にはもう 1 つのパターンを含む構成につながります)。Knudson の基準によれば、敏感な依存性を示し、密な軌道があります (最終的に任意の有限のセル パターンを表示する初期構成)。ルールのカオス的動作のこれらの特徴は両方とも、ルール30のより単純で検証しやすい特性から来ています。それは、ルール30が左順列的であるということです。つまり、2つの構成CとDが位置iの1つのセルの状態において異なる場合、1つのステップの後、新しい構成はセルi + 1で異なることになります。[6]
アプリケーション
乱数生成
上の画像から明らかなように、ルール30はランダムな入力と見なせるものが何もないにもかかわらず、一見ランダムな結果を生み出します。Stephen Wolframは、中央の列を疑似乱数ジェネレーター（PRNG）として使用することを提案しました。これはランダム性に関する多くの標準的なテストに合格しており、Wolframは以前、このルールをMathematica製品でランダムな整数を作成するために使用していました。[7]
シッパー氏とトマシーニ氏は、乱数生成器としてルール 30 をすべてのルール列に適用した場合、他のセルオートマトンベースの生成器と比較してカイ二乗検定で動作が悪いことを示しました。 [8]また、著者らは、「ルール 30 CA によって得られた結果が比較的低いのは、Wolfram が考慮した単一の乱数列ではなく、並列に生成された N 個の乱数列を考慮したためである可能性がある」という懸念も表明しました。[9]
装飾
ケンブリッジ北駅は、ルール30（または白黒反転でルール135）の進化を示す建築パネルで飾られている。[10]建築家は、このデザインはケンブリッジの数学者ジョン・ホートン・コンウェイが研究した別のセルオートマトンであるコンウェイのライフゲームに触発されたと説明しているが、実際にはライフに基づいているわけではない。[11] [12]
プログラミング
セルの値が 1 つ以上のコンピュータ ワード内のビットで表現される場合、状態の更新はビット単位の演算によって迅速に実行できます。ここではC++で示します。
#include <stdint.h> #include <iostream>
int main () { uint64_t state = 1u << 31 ; for ( int i = 0 ; i < 32 ; ++ i ) { for ( int j = 64 ; j -- ;) { std :: cout << char ( state >> j & 1 ? 'O' : '.' ); } std :: cout << '\n' ; state = ( state >> 1 ) ^ ( state | state << 1 ); } }
このプログラムは次の出力を生成します。
...................................O.... …… ..........................OOO........................ ...................................OO..O................. ………… ...................................OO.OOOO................. …… ...................................OO..O.O................. ………… ...................................OO.OOOO.OOO....... …… ......................OO..O.O..O....... ………… ......................OO.OOOO..OOOOOO.... …… ......................OO....O...OOO....O.... …… ......................OO.OOOO.OO..O...OOO....... …… ......................OO..O.O.OOOO.OO..O.... …… ......................OO.OOOO..OO.O.O.OOOO.. …… ...................OO..O...OOO..OO..OO.O...O.... …… ...................OO.OOOO.OO..OOO.OOO..OO.OOO.... .. ...................OO..O..O.OOO.O..OOO..O..O....... …… .......おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお ......OO..O...OOO..OOOO.O....OOO....O.... …… ...................OO.OOOO.OO..OOO.OO..OO..O.OOO.... ... .....OO..O..O.OOO..O..OO.OOO.OOOO..OO..O........ .... .......OO.OOOO..OO.O..OOOOOO..O...O...OOO.OOOO.... ......OO..O...OOO..OOOO.....OOOO.OOO.OO...O...O.... .. .......OO.OOOO.OO..OOO...O...OO....O...OOOOOO.OOO..... .......OO..O..O.OOO..O.OOO.OO.O..OOO.OO.OO..O..O.... .. ……OO.OOOO..OO.O..OOO.O.O..OOOO.O..O.OO.OOOOOO....... ......OO..O...OOO..OOOO...OO.OOOOOO...O.OOOOOO.O..O.....O.... ......OO.OOOO.OO..OOO...O.OO..O....O.OO.O....OOOOOO...OOO.... ……OO..O..O.OOO..O.OO.O.OOOO..OO.O..OO...OO....O.OO..O.. ... ....OO.OOOO..OO.O..OOO.O..OO..OOOO..OOOO.O.OO.O..OO.O.OOOO.... ....OO..O...OOO..OOOO...OOOO.OO.OO..OOOO.OO.OOOO..OO..O... ...OO.OOOO.OO..OOO...O.OO.O..O.OOOO..O..OO.OOOO...OOO.OO.OOO.. ..OO..O..O.OOO..O.OO.OO.OOOOOO.O..OOOOOO..O...O.OO...O..O..O。 .OO.OOOO..OO.O..OOO.O..O.OOOO....OOOO..OOOO.OO.OOOOOOOOOO
参照
参考文献
- ^ Stephen Coombes (2009 年 2 月)。「 貝殻の幾何学と色素沈着」(PDF)。www.maths.nottingham.ac.uk 。ノッティンガム大学。2013年 4 月 10 日閲覧。
- ^ Wolfram, S. (1983). 「セルオートマトン統計力学」Rev. Mod. Phys . 55 (3): 601–644. Bibcode :1983RvMP...55..601W. doi :10.1103/RevModPhys.55.601.
- ^ 「乱数生成」。Wolfram Mathematica 8 ドキュメント。2011年12 月 31 日閲覧。
- ^ Wolfram, S. (1985). 「セルラーオートマトンによる暗号化」。Advances in Cryptology – CRYPTO '85 の議事録。Lecture Notes in Computer Science 218、Springer-Verlag。p. 429。doi :10.1007/3-540-39799-X_32。
- ^ Meier, Willi; Staffelbach, Othmar (1991). 「セルラーオートマトンによって生成された疑似ランダムシーケンスの分析」。Advances in Cryptology – Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91 。Lecture Notes in Computer Science 547、Springer - Verlag。p. 186。doi : 10.1007/3-540-46416-6_17。
- ^ カッタネオ、ジャンピエロ;フィネリ、ミケーレ。マルガラ、ルチアーノ (2000)。 「初等セルオートマトンダイナミクスによるトポロジカルカオスの解明」理論的なコンピューターサイエンス。244 (1-2): 219-241。土井：10.1016/S0304-3975(98)00345-4。MR1774395 。
- ^ Lex Fridman (2018-03-02)、MIT AGI: Computational Universe (Stephen Wolfram)、2021-12-19にオリジナルからアーカイブ、2018-03-07に取得
- ^ Sipper, Moshe; Tomassini, Marco (1996). 「セルラープログラミングによる並列乱数ジェネレーターの生成」International Journal of Modern Physics C . 7 (2): 181–190. Bibcode :1996IJMPC...7..181S. doi :10.1142/S012918319600017X.
- ^ Sipper, Moshe、 Tomassini , Marco (1996)の 6 ページ目。「セルラープログラミングによる並列乱数ジェネレーターの生成」。International Journal of Modern Physics C。7 (2): 181–190。Bibcode : 1996IJMPC ...7..181S。doi :10.1142/S012918319600017X。
- ^ ウルフラム、スティーブン（2017年6月1日）、「ああ、ルール30でカバーされている！」、スティーブン・ウルフラムのブログ
- ^ ローソン・パーフェクト、クリスチャン（2017年5月23日）「間違った理由で正しい答え：新しいケンブリッジノース駅のセルオートマトン」、The Aperiodical
- ^ コリーン・パーティル。「英国の鉄道駅が有名な数学者に捧げたトリビュートは、数学以外はすべて正しかった」。Quartz 。 2017年6月12日閲覧。
- Wolfram, Stephen、1985 年、「Cryptography with Cellular Automata」、CRYPTO'85。
外部リンク
ウィキメディア・コモンズには、規則 30に関連するメディアがあります。
- Weisstein、Eric W.「ルール 30」。MathWorld。
- 「ルール30賞の発表」。スティーブン・ウルフラム著作集。2019年10月1日。
- ウルフラムのセルオートマトンアトラスのルール30
- ルール 30: Wolfram の疑似ランダム ビット ジェネレーター。David Griffeath の Primordial Soup Kitchen のレシピ 32。
- ルール 30 パターンの繰り返し。ルール 30 オートマトン セルを埋めるために繰り返されるパターンのリスト。有限回数のステップの後に繰り返されます。Frans Faase、2003 年。2013 年 8 月 8 日にオリジナルからアーカイブされました。
- モザイク フラクタルの舗装。LOGO ソフトウェアの専門家 Olivier Schmidt-Chevalier の観点から見た、ルール 30 のパターンの基本的な紹介。
- 2010 年 2 月の TED トーク。Stephen Wolfram が万物の理論の計算について語り、その中でルール 30 などについて語っています。