どうにかして彼を知り、同時にコイルから降りないために、悲惨な脳を持つ人間は、何が起こっているかを思慮深く見て、私たちが見たものを分析し、モデルを構築する必要があります-抽象化。そして、実際に何が起こっているのかを理解していると信じるのは簡単です。
そして、あなたは驚くべきものを知っていますか? このアプローチはうまく機能します。 まあ、ほとんどいつも。 少なくとも、これ以上良いものは思いつきません。
しかし、実際には私はそれについて話していません。 これらの同じモデルのカテゴリーの、審美的にも数学的にも非常に興味深いカテゴリーについてお話したいと思います。
はい、セルオートマトン、つまり、そのサブセットである最も単純なセルラーオートマトン(エレメンタリーセルラーオートマトン)について話しています。 この記事では、それが何であるか、何であるか、どのような特性を持っているかを説明し、私の意見では、このような記事ではしばしば不当に無視される主要な、完全に正しい質問に答えます。 このように聞こえます: そして、なぜこれがすべてなのでしょうか?
今後、最も単純なセルオートマトンは、暗号化、物理プロセスのモデリング、人間の行動、生物学、およびその他の重要で興味深いもの全体で使用されます。 そして一般的に: まず、それは美しいです。
記事を読んだ後、あなた自身がそれらを試してみたいと思うことを心から願っています。この場合、JSとスティックから組み立てられたジェネレータを持っています。
退屈な理論
セルオートマトンとは何ですか?
離散モデル。任意の次元のグリッドであり、各セルはいつでも状態の有限セットの1つを取ることができ、ある状態から別の状態へのセルの遷移に対してルールが定義されます。
例: Conway's Life 、 Von Neumann Automation 、 Wireworld 、 Schelling Segregation Model
例: Conway's Life 、 Von Neumann Automation 、 Wireworld 、 Schelling Segregation Model
彼らはどんな人ですか?
グリルの寸法に応じて:
一次元、二次元、三次元など
たとえば、この記事で強調表示されているルール110などは1次元であり、Lifeは2次元です。
可能な条件の数に応じて:
バイナリ、ターナリなど
さまざまなセルオートマトンでは、さまざまな方法、つまり状態が次の瞬間に依存する多くのセルで、セルの近傍を決定できます。 これは、たとえば、さまざまなランクのVon Neumannの 近傍またはMooreの近傍です 。
SCは同期および非同期です。 同期では、システムのすべてのセルが同時に、非同期で更新されます-それぞれが独立して更新します。
最も重要な分類の1つは、 動作のタイプです 。 これについては、以下で個別に説明します。
一次元、二次元、三次元など
たとえば、この記事で強調表示されているルール110などは1次元であり、Lifeは2次元です。
可能な条件の数に応じて:
バイナリ、ターナリなど
さまざまなセルオートマトンでは、さまざまな方法、つまり状態が次の瞬間に依存する多くのセルで、セルの近傍を決定できます。 これは、たとえば、さまざまなランクのVon Neumannの 近傍またはMooreの近傍です 。
SCは同期および非同期です。 同期では、システムのすべてのセルが同時に、非同期で更新されます-それぞれが独立して更新します。
最も重要な分類の1つは、 動作のタイプです 。 これについては、以下で個別に説明します。
そして、最も単純なセルオートマトンは何ですか?
1次元のバイナリ(2つの可能な状態)セルラーオートマトン。各瞬間のセルの状態は、自身の状態と前の瞬間の隣接セルの状態のみに依存します。
単純なセルラーオートマトンは256個しかなく、その一部の動作は他のセルオートマトンと重複しています。 しかし、それにもかかわらず、狭いサークルで広く知られているスティーブン・ウルフラムは 、彼の前に何年もの人生をそれらの研究に捧げ、数十人の数学者もこれに対処し、今日まで、科学者はこのトピックに関する論文と科学作品を書いています。
まず、用語を定義しましょう。 このようなオートマトンのバリエーションは256個しかないため、同じWolfram(よく参照します)はそれほど気にしなくて、0から255の数字を呼び出すことを提案しました。この命名は、その簡潔さと便利さから、よく定着し、それ以来呼び出されていますあなたは信じられない、「 タングステンコード 」。
私はあなたを理解しています、私はリンクをたどるのが面倒なので、これらのコードを理解する方法について簡単に話します。 そして、もしあなたが私なしでこれを完全によく知っているなら、ネタバレを展開することはできませんが、ただ読んでください。
タングステンコードの意味
すぐに例を見てみましょう。
110などのルール番号を使用します。
1.110 10 = 01101110 2 。
2.テーブルに数値のバイナリ表現の数値を入力します。
左側の隣人、セル自体、および右側の隣人(テーブルの最初の行)の状態に応じて、次のステップで、セルは2番目の行に示された状態のいずれかを受け入れます。
これはさらに次のように視覚化できます。
110などのルール番号を使用します。
1.110 10 = 01101110 2 。
2.テーブルに数値のバイナリ表現の数値を入力します。
111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
左側の隣人、セル自体、および右側の隣人(テーブルの最初の行)の状態に応じて、次のステップで、セルは2番目の行に示された状態のいずれかを受け入れます。
これはさらに次のように視覚化できます。
Wolframはまた、セルオートマトンを行動の種類に応じて4つのクラスに分けることを提案しました:
グレード1:すべてのセルがすぐに同じ状態になり、安定します。
たとえば、ルール40:
グレード2:すべてのセルの状態がすぐに安定するか、周期的な振動が発生します。
たとえば、ルール3および33:
グレード3:オートマトンはカオス的な非周期構造を生成します。 初期状態の小さな変化は、結果の大きな変化を伴います。
たとえば、ルール22:
グレード4:マシンは複雑な相互作用構造を生成しますが、これは長期間存続できますが、安定性は達成されません。
たとえば、ルール193:
人生のPKA
ルール30
時々、完全な予想外の場所で基本的なセルオートマトンが見つかります。
たとえば、なんてかわいいのか見てください。
ただお世辞をしないでください。 彼はあなたを愛していません。 これは繊維コーン 、人間にとってコーンの家族からの最も危険な軟体動物です。 その毒に対する解毒剤はまだありません。
そのシェル上の描画は、ルール30によって生成されたパターンにすぎません。 少なくともそれはノッティンガム大学で考えていることです。
これは、「ルール30」の開発が1つのポイントからどのように見えるかです。
最近まで、同じルール30がMathematicaで疑似乱数を生成するために使用されていました。 これは、その重要な特性により可能になりました。それによって生成された結果はカオスです。つまり、初期条件のわずかな変更は、生成された結果に大きな影響を与えます。
ただし、ルールが繰り返しパターンを生成する初期条件は膨大です。 たとえば、初期状態で14番目のセルごとに「生きている」場合、結果はそのようなスカンジナビアのセーターになります。
ルール110
最も興味深いルールの1つ。 タングステンはそれをクラス4に分類しますが、初期条件によっては、クラス1、2、3、または4の代表として動作する場合があります。
比較のために、1つのポイントからの進化:
三角形の左の境界には周期構造があり、右半分には安定した均質状態があり、三角形の中央と右側の部分には不安定な周期構造が散在するカオス構造があります。
そして、生細胞で50%満たされたランダムな初期状態からの進化があります。
ここでは、周期的な(興味深いことに、異なる周期で)カオスも見ることができます。
2000年にマシュークックは 、このセルオートマトンがチューリング完全であること、つまり、あらゆる計算可能な機能を実現できることに基づいていることを証明しました。
フラクタル
1つのポイントから展開してフラクタル画像を生成するセルオートマトン(ルール18、22、126、161、182、218など)がいくつかあります。 たとえば、規則22のパターンは、2を法とするパスカル三角形(「Sierpinski Napkins」の一種の離散アナログ)です。 シェルピンスキーナプキンとパスカルの三角形の間の接続は、3年前にすでにHabréで適切にカバーされていました。
そして、この幸福はすべて次のようになります。
ルール161は、同じフラクタルの反転バージョンを作成します。
ちなみに、オートマトンの実装に関する重要なポイントに言及するのを忘れていました。
「エッジ効果」、つまり境界セルの境界線の効果を回避するには、オートマトンを閉じてリングにする必要があります。 左端のセルを右端の右隣にし、逆も同様です。
それ以外の場合、完全に予測された完全に満たされた長方形(完全に生細胞で構成される初期状態での規則161の進化)の代わりに、予期しない何かが見られます:
ルール184
ルール184にはいくつかの興味深い機能があります。そのため、数学モデリングで広く使用されています。
- 各ステップの後、「生きている」セルの数は変わりません。
- ルールは、初期状態に応じて、クラス2または4のルールとして動作できます。
- 初期状態の「生きている」セルが少ないほど、マシンの安定化が速くなります
その助けにより、 トラフィックフローはかなり効果的にモデル化されます。
個々の車は前方に移動し、 交通の波は後方に移動します。
(ウィキペディアの写真)
また、表面へのエアロゾルの堆積のモデリングおよび粒子消滅のモデリングにも適用できます。 そして、それに基づいて、私は多数の要素を構築することができます(私は主張することはできません、私は記事から何も理解していなかったので)。
おわりに
数学は、何と言っても、科学の女王であり(科学そのものとはほとんど言えませんが)、その中で働くことは無限ではありません。 多くの未解決の物理的問題があり 、それらの多くを解決するための数学的な装置がまだ発明されていないという理由だけで解決されていない。
そして、それは起こります、そしてその逆-誰も数学的な装置を必要としないようです、そして、それは突然、それが適切であることが判明する問題が生じます(例えば、規則184と交通の流れで)。
そして、最終的には美しいです。
関連リンク:
Stephen Wolframの最も単純なセルオートマトンのアトラス 。
タングステンブックニューサイエンスの種類 ;
謙虚でない使用人( source )のオーサーシップ用の最も単純なセルオートマトンのジェネレーター 。
Nico Disseldorpという名前の友人からの別の素晴らしいジェネレーター 。