セルオートマトンの興味深い例。

habr（ http://habrahabr.ru/post/168291/、http://habrahabr.ru/post/227003/ ）、特にゲーム「Life」（ http://habrahabr.ru/ ）には、セルオートマトンに関する多くの記事があります。 post / 67790 /、http：//habrahabr.ru/post/154509/、http：//habrahabr.ru/post/237629/ ）。私の意見では、予想外で面白い例を与えるために、他のセルオートマトンについて何か新しいことを伝えたいです。 元の構成を徐々にコピーしている構造を見ます。そして、円を描く構造。

注意してください、大きなGIF

定義-重要なことですが、誰にとっても興味深いものではありません

Kudryavtsevの本「オートマトンの理論の紹介」によると、セルオートマトン（または均質な構造）は次のセットです。

どこで $inline_formula$ 整数k次元ベクトルのセット-構造セル。使用します $inline_formula$ ;

$inline_formula$ -多くの条件。

$inline_formula$ からなるペアごとに異なる非ゼロベクトルの順序付きセットです $inline_formula$ 力 $inline_formula$ 、便宜上 $inline_formula$ 。これはセルの近傍です。

$inline_formula$ h引数の値論理の関数nです（ $inline_formula$ ）、 $inline_formula$ -状態変化のルール。

一般的に言えば、 $inline_formula$ 他の航空会社を利用することもできますが、彼らはめったにそれを行いません。トーラス上でセルオートマトンを作成してみませんか？

これは定義にも適用されますが、次の場合に役立ちます。

$inline_formula$ -構造の状態。

$inline_formula$ -セル $inline_formula$ -彼女の状態。「セルの座標によると、その状態」のようなものです。

$inline_formula$ -新しいセル状態

$inline_formula$ -構造の新しい状態。各セルには独自の新しい状態があります。（適用される $inline_formula$ すべてのセルに）

構造の新しい状態は「アプリケーションの順序」に依存しないことに注意してください $inline_formula$ 、一見すると思われるかもしれませんが、実際には、状態を変更せずに、新しいフィールドを作成し、新しい状態で埋めます。

構成は、有限数の非ゼロセルを持つ構造体の状態です。

構造をコピー

いくつかの方向性があります $inline_formula$ -周辺。したい $inline_formula$ -XOR'ila付近のすべての値（結果が計算されるセルの値を含む）。なぜそのようにしたのですか？フィールド上にセルが1つしかない場合は、1回の移動で近隣全体に「コピー」される（反転される）ことは明らかです。

明らかに、操作は線形（XORの意味）です。つまり、各セルの新しい構成を個別に減算し、結果の要素を要素ごとにプロキシし、新しい構成を正直に読み取らないようにします。言い換えれば（以下で $inline_formula$ XORが理解）：if $inline_formula$ それから $inline_formula$ 。まあ、それに応じて $inline_formula$ 。

示す $inline_formula$ -セル内に1ユニットの構成 $inline_formula$ 要素。

証明

さて、それらを個別に検討してください。次の構成が持つことは簡単にわかります $inline_formula$ セル内 $inline_formula$ （1を含む）はそのまま残ります。つまり：

構成がどのようにさらに進むのかを見てみましょう（そして、それはクールに振る舞います！）：

すべてのメンバーが $inline_formula$ 合計で偶数回入力されるため、減少します（そして、特性フィールド2を使用します）。

さて、コピーの証拠ベースは準備ができています。移行を試みましょう。すべて同じ、2つではなく- $inline_formula$ 。

アプリケーションの場合 $inline_formula$ $inline_formula$ 時間の形式は次のとおりです。

それから

欲しいもの。

今、私たちは持っています $inline_formula$

クールな、クールな、私たちの構造は実際に近隣を定義するベクトルに沿ってコピーされます。

太陽をコピーしましょう：

正方形の例では、さらに進んでいます：

Xor

円周

信じられないほどの素晴らしい例：個々のセルの有限のメモリ（つまり、座標を覚えることさえできない！）を持つ離散構造で、連続オブジェクト（円）を任意にうまく補間します。

このシステムは正式な説明から明確にならないため、このシステムを正式に説明することはしません。セルには12個の状態があり、周辺には多くの要素があります。

始めましょう。ランニングシグナルが何であるかはほとんど明らかです。

仕組み

固定状態と1つの「信号」を持つ2つのセルがあります-最初の2つの間の間隔のセルです。ドライブには、「左に移動」と「右に移動」の2つの状態があり、これらの状態では、予想外に特定の方向に進化します。固定セルと接触すると、反対方向に回転します。

そして、彼が彼を保持している細胞を「押す」ことができることは明らかです。

仕組み

信号と接触している各固定セルは、信号と同様に動作します：側にシフトします。

それだけで十分です。ロードセルをプッシュする水平信号を実行し、プッシュするたびに2つの垂直ラッチと1つの垂直信号を作成します。水平方向の信号が垂直方向の信号と競合しないように信号を配置できることは明らかです。信号が重なる場合は、次のステップで信号を発射する方向を「記憶」する新しい状態を作成する必要があります。

固定点が丸くなる傾向があるのはなぜですか？

注：

$inline_formula$ 、 $inline_formula$ -水平信号を固定するポイントからの「開始までの」距離。

$inline_formula$ 、 $inline_formula$ -インデックスを使用して、列の垂直信号を固定するポイントまでの水平軸からの距離 $inline_formula$ ;

その後、開始時間 $inline_formula$ 垂直信号： $inline_formula$ （それぞれ $inline_formula$ 中心から移動する必要がある量から $inline_formula$ 右、戻る、左、戻る）、漸近的に $inline_formula$ 。同様に、垂直信号の開始からその高さまでの時間 $inline_formula$ ： $inline_formula$ 。定義する $inline_formula$ 円の半径 $inline_formula$ つまり、私たちは持っています $inline_formula$ 。すでに理解したように、上のポイントの形成の時間 $inline_formula$ 距離の列 $inline_formula$ ： $inline_formula$ 。この点は半径の円上にあります $inline_formula$ （ピタゴラスの定理）、すなわち $inline_formula$ でも $inline_formula$ つまり、私たちはそれを得た $inline_formula$ 。そして、これは、すべてのそのような（垂直固定）ポイントが、水平固定とほぼ同じ中心からの距離に配置されることを意味します。したがって、それらは円に近い図形を形成します。

状況を明確にする美しい写真：

太陽のプロトタイプを手に入れたArsenに感謝します！

セルオートマトンの興味深い例

構造をコピー

円周

More articles: