セルラーマシンステッパー

この記事では、2次元セルラーオートマトンのルールを提案します。これは、一方ではジョンコンウェイの人生 （ コンウェイの人生のゲーム ）に非常に似ており、他方では大きな違いがあります。 まず、最大3つのセル状態の増加、自己組織化能力の向上、無制限のアクティブな進化、無制限の数の移動構成によって区別されます。



安定した構成の場合、新しいルールはLifeゲームのルールと一致するため、Lifeゲームのすべての安定した構成は新しいルールに存在します。 記載されているセルラオートマトンには、移動クラスの大きなクラスである宇宙船があります。 これらすべての構成は、ステッパーショベルと松葉杖の人の動きに似た同じ進歩的なメカニズムに沿って動きます。 私は同様の宇宙船をステッパーと呼び、ステッパーはそれ自体を支配しています。 そのため、将来的にそれを呼び出します。



ステッパーには非常に多くのオシレーターがあり、ゲームLifeの一部のオシレーターはステッパーで動作し、ルールの連続性を示しています。 そして最後に、有名なコンウェイグライダーも規則案に存在します。 この記事では、ランダムに満たされたグレーティングのダイナミクスを検討し、ステッパーの移動メカニズムを明らかにし、現在見つかっているオシレーターとステッパーについて説明します。 衝突と複雑な機能的動作の例も示します。





[00]ステッパーのストリームを生成する移動構成の例

ルール開発履歴

1988年、私は技術ビジョンの研究室で働きました。 ラスタモノクロ画像のスケルトン化のアルゴリズムを研究し、その実装のためのプログラムを作成しました。 スケルトン化アルゴリズム自体は私たちにとって決して有用ではなく放棄され、少し改良した後の記述プログラムは、グラフィカルエディタとグラフィカル出力を備えたかなりまともなセルオートマトンになりました。 彼女の最初のテストは、もちろん、ライフオブジョンコンウェイでした。 しばらくして、他のルールを試してみたかったのですが、1975年のジャーナル「Science and Life」で以前読んだ記事「 Evolution of the game Evolution 」を思い出しました[1]。 この記事では、ゲームLifeを開発しようとして、著者のI. Sidorovが新たに生まれた細胞の3番目の状態を追加しました。 新しいルールでは、セルは空、若い、古いの3つの状態になります。 若い細胞はどのような状況でも死ぬことはなく、次世代では古い細胞になります。





[01]細胞条件の指定



I.シドロフは、すべてのルールを次のように策定しました。

1. 一度の動きで若い細胞が過密や孤独で死ぬことはありません。 1つの移動の後、若いセルは古いセルに変わります。
2. 空の各セルでは、このセルに3つの隣接セルがあれば、新しい（若い）セルが生成されます（古いセルと若いセルの両方が隣接セルになる可能性があります）。
3. 古いセルは、4つ（またはそれ以上）の古いセルに接している場合、または少なくとも1つの若いセルがある3つ（またはそれ以上）のセルに接している場合、過密により死にます。
4. 古いセルは、孤立している場合や隣接セルが1つしかない場合（古いセルと若いセルの両方が隣接セルになる可能性があります）、孤独で死にます。

I.シドロフのセルラーオートマトンで彼が説明した2隻の船があります。 その後、2つのオシレーターを見つけることができました。 残念ながら、特定の臨界質量を超えると、人口はその構造を失い、急速に成長します。 これを観察するのは面白くなかったので、私は自分の生と死の法則を発展させることを約束しました。

さまざまなオプションを選択した後、次のルールが形成されました。

1. 一度の動きで若い細胞が過密や孤独で死ぬことはありません。 1つの移動の後、若いセルは古いセルに変わります（このルールは変更されません）。
2. 若いセルは、少なくとも3つの隣接セルがあり、その中に少なくとも2つの古いセルがある場合、空のセルで生まれます。
3. 古いセルは、2つまたは3つの隣接するセルがあり、そのうち1つだけが若い場合、次の世代に存在し続けます。

より明確に、ルールは表の形式で提示できます。 軸は若い隣人と古い隣人の数を示します。





[02] I.シドロフの規則の表形式





[03]ステッパールールの表形式表示



このルールは私にとって非常に興味深く思えたので、自分の記事を書いて同じジャーナルScience and Lifeに送った。 しばらくして、近い将来セルラーオートマトンに関する出版物が予定されていないという回答を受け取りました。 20年以上の間、私はゆっくりと、大きな中断で、このセルラーオートマトンに取り組みましたが、それをどこにも公開しようとしませんでした。 そして、任意のルールに従ってセルオートマトンを作成できる素晴らしいGollyプログラムの登場によってのみ、あなたのささやかな研究を共有する機会が現れました。 Gollyは無料で、 http：//sourceforge.net/projects/golly/からダウンロードできます。



この記事のすべての図にはインデックスが付いています。必要に応じて、 MilhinSA.Golly2.5.zipアーカイブをダウンロードできます。 このアーカイブには、すべての例のrleファイルが対応するインデックスの下にあります。 この場合、静的な写真に満足することはできませんが、実際のプロセスを確認してください。 Gollyは、最初に展開することなく、ルールと例でこのアーカイブを開くことができます。



2012年3月、私はConwayのGame of Life Englishフォーラムの Steppersセルラーマシンに投稿を投稿しました。 このメッセージは、フォーラムの参加者の関心を喚起し、一部はステッパーズ研究に参加し、調査結果を共有しました。

ダイナミクス

セルオートマトンの積分特性をチェックする最善の方法は、ノイズ信号、つまり、ランダムに満たされた母集団をその入力に送信することです。 次の図は、世代32、320、および3200のゲームLifeおよびSteppersのランダムに満たされたトロイダルグリッドの進化の結果を示しています。Steppersの人口密度は、ゲームLifeよりもゆっくりと減少し、ある段階で安定することがわかります。





[04]ゲームライフとステッパーのランダムな集団の進化



統計的に信頼できるデータを取得するために、次の計算実験を実施しました。 各ルールについて、密度が50％の256 x 256セルのランダムに満たされたトロイダルフィールドが形成されました。 セルラーマシンは、最大10,000世代まで機能しました。 世代ごとに、フィールド密度はパーセンテージとして計算され、状態を変更したセルのパーセンテージも計算されました。 最後のパラメーターは、セルオートマトンのアクティビティを特徴付けます。 各マシンについて、このプロセスを1000回繰り返し、出力を平均しました。



以下は、密度とアクティビティのグラフです。 これらのグラフから、開発の最初の段階で密度と、それに応じてゲームLifeのアクティビティが急速に低下し、3000〜4000世代で平均して密度の3％に低下することがわかります。 アクティビティは平均1％に低下します。 これらが残りの静止構成と単純な発振器であることは容易に理解できます。 セルラーマシンステッパーは、異なるシナリオで進化します。 約20世代にわたって、若い細胞と古い細胞のバランスが確立され、減衰した振動プロセスにつながります。 その後、密度が低下し始め、500-700世代で21％安定します。 アクティビティは14％安定します。 したがって、十分なサイズのランダムフィールドの進化は無限に続きます。





[05]密度と活動の変化のグラフ



密度と活動の変化のグラフはフィールド全体の平均値を示しますが、細胞の密度と活動は時間だけでなく空間でも変化します。 一様に満たされたランダムフィールドの進化中に、セルがアクティブ領域にグループ化され、テクスチャを形成していることがわかります。 アクティビティが増加した領域を強調するために、特別なセルラーオートマトンマッピングアルゴリズムが適用されました。 次のように機能します。 32世代にわたる各セルについて、出生数と死亡数が計算されます。 次に、黒赤黄白パレットのセルラーオートマトンの画像が表示されます。 次の図は、ゲームLifeのアクティブセルが非常に急速に孤立した領域に分割され、その後に消滅することを示しています。 ステッパーのセルオートマトンでは、アクティブな領域は形状とサイズを絶えず変化させ、結合および分解します。 十分な広さのエリアは空いたままで、病院、発振器、グライダー、ステッパーがあります。 このため、ランダムなフィールドの進化があっても、自己組織化の結果としてかなり興味深い状況が発生します。





[06]進化中の人口活動の変化



確かに、ステッパールールは非常に粘り強いだけでなく、非常に爆発的でもあります。 多くの場合、単純な構成の相互作用は、制御できない人口増加につながります。 ConwayのGame of Lifeフォーラムで、人口の無制限の増加を引き起こす最小サイズの構成が見つかりました。 次の図は、5セルパターンと1500世代の状態を示していますが、完全ではありません。 人口サイズは、20,000セルよりわずかに少ないです。





[07] 1500世代目の5セルパターン



線形7セルパターンはさらに集中的に開発されています。 ここでは、彼は500代目、8 124細胞の集団サイズで描かれています。 3000世代では、人口サイズは500,000セルを超えます。





[08] 500世代目の7セルパターン

ムーブメント、ステッパー

現在、Steppersセルラーオートマトンでは、2種類の移動構成が見つかります。 さらに、唯一のタイプは、ゲームライフではグライダーと呼ばれる最初のタイプを指します。 Steppersのグライダーは、ゲームLifeのグライダーとはわずかに異なることがわかります。 これらのルールの間に大きな違いがあるため、グライダーの存在は予想外でした。





[09]ゲームとゲームステッパーグライダーの比較。



ステッパーは別のタイプに属し、サイズは無制限なので、数は無制限です。 すべてのステッパーは同じ移動方法で結合されます。 そして、このメソッドは、その存在を出生ルールに負っています。 「空のセルに3つの隣接セルがあり、その中に少なくとも2つの古いセルがある場合、若いセルは空のセルで生まれます」というように聞こえます。 出生ルールがそのような効果を引き起こした理由を説明しようとします。



ゲームLifeには、光の速度などがあります。 これは、無限または閉じたセルの列が移動できる究極の速度であり、世代ごとに1つのセルに相当します。 ステッパーでは、若いセルの列は新しい列を生成できません;このため、彼は最初に年をとらなければなりません。 したがって、Steppersの無限数のセルの伝播速度は、ゲームLifeの半分であり、2世代に1つのセルです。





[10]ゲームライフアンドステッパーの無限の数のセルの進化



次に、有限な一連のセルの進化を考えてみましょう。 ライフゲームでは、極端なセルの反対側に新しいセルを作成することはできません。隣接するセルが2つしかないため、新しい世代はそれぞれ2行短くなり、しばらくすると消えます。 ステッパーCA内の多数のセルの進化中に同じ画像が観察されますが、その速度は2倍しかありません。





[11]ゲームライフとステッパーの有限数のセルの進化



しかし、ステッパーで、行の片側で、1つの隣人が極端なセルに追加されて、第1世代で消滅しないようにすると、状況は完全に変わります。 次のいずれかの方法でネイバーを追加できます。





[12]多数の細胞のステッパーへの変換



この場合、エージングの段階で、行の端に沿って1つのセルが生成され、その幅が復元されます。 2つの古いセルと1つの若いセルが既に新しいセルを生成しているため、一連のセルが移動し続け、幅を連続的に復元します。





[13]多数のセルの幅を復元する



この手法を使用すると、任意のサイズのステッパーを作成できます。 以下は100セルの列と優雅なステッパーで、数百世代後にそこから出てきました。 その期間は8です。





[14] 100セルステッパー



ステッパーは隣接または複合することができ、密接に相互作用することも、全体として移動することさえできます。 さまざまなステッパーの小さな例を次に示します。





[15]ステッパーの例



ステッパーのサイズは、幅だけでなく長さも無限に大きくすることができます。 ConwayのGame of Lifeフォーラムのメンバーとして、 Emerson J. Perkins（knightslife）は 、任意の順序で通常の要素を使用して、任意の長さのステッパーを構築できることを示しました。





[16]任意の長さのステッパーの設計



残念ながら、現時点では、グライダーとステッパーを除く他のタイプの移動構成は知られていません。 しかし、まだ存在することを願っています。 上記のステッパーは、背後に構成を残していません。つまり、宇宙船です。 移動中のその他のステッパーは、さまざまな静止した構成を離れ、グライダーとステッパーを放出することができ、多くの場合、単純に不断のカオスが続きます。

蒸気機関車と熊手

ゲームLifeの用語に従って、ゴミを残して移動する構成はフグと呼ばれます 。 次の図では、移動中に一連の静止構成を残す蒸気機関車の選択を見ることができます。 2つのブロックのチェーンを生成する蒸気機関車は、記録破りの短い期間p 6を持ちます。移動速度c / 2で、ブロックは3つのセルだけの期間で積み重ねられます。 近いことは単に不可能です。 最後の蒸気エンジンは連続したラインを形成します。 これにより、 wickstretcher拡張機能として分類できます。





[17]蒸気機関車



移動構成を生成する蒸気機関車はレーキと呼ばれます。 このような予期しない名前は、不正確な翻訳の結果です。 ミュラーの辞書によると、 レーキという言葉には、海軍の「縦方向の火」など、多くの意味があります。 これがレーキという言葉の作者が意味したものだと思います。 しかし、熊手が私たちを捕まえました。我慢する必要があります。 火の方向に応じて、レーキは正面、側面、および背面に分割されます。 ステッパーでは、熊手はグライダーとステッパーによって発射されます。 以下に、レーキシューターのさまざまなオプションがあります。





[18]前面と背面のグライダーを発射するレーキ





[19]サイドレーキ





[20]逆レーキ



すべての機関車にこのような狭い専門分野があるわけではありません。 次の図の蒸気エンジンは、固定構成とともにリバースステッパーを生産します。





[21]逆レーキと固定構成



また、この蒸気機関車は、1周期で2つのバージ、2つのボート、4つのサイドステッパー、4つのリバースステッパー（12セル幅の大きなステッパー1つを含む）を残します。





[22]リバース、サイドレーキ、固定構成



残念ながら、蒸気機関車は発見されておらず、発振器、定期的な構成が残っています。 実際、一対のビーコンを生成する蒸気エンジンがありますが、他のゴミの背景に対してそれらに気付くことは困難です。 したがって、これはルールの例外です。

乗数

ブリーダーは、二次的な人口増加をもたらす構成です。 二次成長の本質は、乗数が構成を生成し、その構成がいくつかの構成も生成することです。 Steppersには2種類のブリーダーがあります。これは、熊手での熊手射撃と静止した構成を残す蒸気機関車での熊手射撃です（この提案が文脈から外れないことを願っています）。



次の図では、MMS （moving-moving-stationary）などの乗数を見ることができます。 これは、移動するオブジェクトが静止オブジェクトを生成する移動オブジェクトを生成することを意味します。 p240の期間で、彼は一連の浴槽を形成する4つの蒸気機関車を生産しています。





[23] MMSタイプ乗数



次のブリーダーは、タイプMMM （moving-moving-moving）です。 p32の期間で、彼はレーキシューティングの簡単なステッパーをリリースします。 この乗数のサイズが小さいことに注意してください。5×9セルの長方形で囲まれたのは15セルだけです。 ゲームLifeでは、2次成長を伴う最小構成は「26セル2次成長」であり 、そのサイズは、名前が示すとおり26セルであり、サイズは16193×15089セルです。





[24] MMMタイプ乗数



エマーソンJ.パーキンスは非常に興味深いブリーダーを発見しました 。 彼の意見では、これは他の有名なセルオートマトンでは発生しません。 2つの同一の横方向レーキが相互作用すると、同じレーキが生成されます。 つまり、2つの構成がそれぞれ独自の構成を直接生み出します。





[25] 2つの同一の構成が独自の種類を生み出します。



エマーソンJ.パーキンスは、さらにいくつかの「合成」プロパゲーターを構築しました。 以下は、MMSおよびMMMタイプの乗数です。 それらの作成中に、グライダー合成の要素が使用されたため、その可能性を期待できます。





[26] MMSパーキンス乗数





[27] MMMパーキンス乗数

カウンター

逆方向に逆のレーキをリリースする構成があります。 これらの構成は、最初に発行されたリバースレーキからのステッパーのストリームが後続のすべてを破棄するため、乗数になることはありません。 それにもかかわらず、このようなパターンはある程度興味深いものです。 実際、新しくリリースされたリバースレーキと最初のリバースレーキのステッパーのストリームが衝突すると、予期しない効果が現れます。 発行された各逆レーキは、ストリーム内の最初のステッパーを破壊しますが、同時に以前に破壊されたすべてのステッパーを復元します。 しかし、それがバイナリカウンタの仕組みです。 ステッパーのチェーンをビットのシーケンスとみなし、同時に、欠落しているステッパーを「1」、現在を「0」とすると、発行された逆レーキがどのように計算されるかがわかります。





[28]カウンター



このパターンに基づいてカウンターを作成し、その動作を確認してみましょう。 16桁に制限します。つまり、ストリームに16のステッパーを残します。 任意の数、たとえば9780を使用します。そのバイナリ表現は0010011000110100です。カウンターの期間がp48であるとすると、指定された数のバックレーキが9780 * 48 = 469440世代でリリースされます。 次に、0世代と469440世代のカウンターの状態を比較します。 カウンターが機能していることを確認できます。 ステッパーのシーケンスには、設定した番号が含まれています。





[29]カウンターの動作例

散弾銃

ガン（ガン）は、グライダーまたは宇宙船を放出する静止構成と呼ばれます。 現在、ステッパーを撃つ3つのライフルが知られていますが、グライダーライフルはまだ見つかっていません。 これらの銃のうち最初のものは、幅が4セルの4つのステッパーを生産します。 その期間はp32です。 この図は、世代T = 0、6、12、18、24、32のシーケンスを示しています。





[30] 4セル幅の散弾銃の散弾銃



2番目のショットガンの周期はp14で、5つのセルの幅を持つ4つのステッパーを生成します。 図は、世代T = 0、3、6、9、12、14のシーケンスを示しています。





[31] 4方向に5セル幅のショットガンを発射するステッパー



そして最後に、予想通り、一方向に発射する銃。 その周期はp10で 、6セル幅のステッパーを生成します。





[32] 6セル幅のショットガン

発振器

発振器は、それ自体の前身である固定構成です。 彼らの開発では、数世代後に初期状態に戻ります。 現在、約200の発振器が知られています。 そのうちのいくつかは、ゲームライフからのダブルを持っています。 細胞の老化により、細胞の周期が上方に変化することがわかります。 しかし、まったくそうではありません。 大釜 、これは最後の行のオシレーターで、ゲームではLifeの周期はp8です。 ステッパーズでは、彼の期間はp5に短縮されました。





[33]ゲームのライフからオシレーターの周期を変更する



実験として、ゲームLifeのオシレーターの大規模なグループが、Steppersセルラーオートマトンに転送されました。 それらのいくつかは生き残りました、つまり、彼らは発振器のままでした。 以下に、それらの一部を示します。





[34]ゲームライフに存在する発振器



ステッパーでオシレーターを検索するために、かなり原始的なアルゴリズムで特別なプログラムが作成されました。 256 x 256セルのサイズのトロイダル格子の中心では、16 x 16の領域がランダムな状態のセルで満たされていました。 正方形の内容の12種類の対称性がランダムに選択されました。 次に、500世代について、中央地域のコンテンツを32の以前の状態と比較しました。 一定期間以上前に現在の状態がすでに満たされている場合、その内容はテキストファイルに表示されます。 推定されたパターンは繰り返し提示されませんでした。 次に、かなり膨大なテキストファイルから、手動で管理して非常に興味深いオシレーターを選択しました。 それらの例をいくつか示します。





[35]ステッパーにあるオシレーターの例



そして、現在知られているオシレーターのほぼ完全なコレクションです





[36]ステッパーオートメーションオシレーター

衝突

ステッパーには多くの衝突オプションがありますが、これはステッパーが多種多様であるためです。 このため、単純なステッパーであっても、少なくとも衝突の概要を完全に把握することは困難です。 ただし、衝突では、グライダーとステッパーが破壊され、生まれ、方向を変える可能性があることが実験により示されています。 ステッパーセルオートマトンの生存率が向上しているため、衝突の結果として制御できない人口増加がしばしば発生します。おそらく、これはグライダーの合成とステッパーの参加による合成の問題の障害になる可能性があります。

そして今、いくつかの例以下は、グライダーとブロックの衝突のオプションを示しています。図から分かるように、衝突の結果は、ステッパ、ハイブであってもよい（蜂の巣）と船舶（船）。逆に、グライダーとハイブの衝突の結果はブロックになる可能性があります。





[37]グライダーとブロック



の衝突の例次の図は、2つの単純なステッパーの衝突の例を示しています。正面衝突では池が残り、側面衝突ではブイは振動子です。





[38] 2つのステッパーの衝突の例



メンバーフォーラムコンウェイ、生命のNHの試合たJuho Pystynen（トロピリウム）が提供します興味深い機能的な衝突の例。彼の許可を得て、それらのいくつかを公開しています。



最初の例では、4つのステッパーが逆のレーキの分岐から流れます。中心から外れた衝突では、彼らは全滅し、グライダーの4つの流れを放出します。





[39] 4つのステッパーストリームがグライダーを生成



する次の例では、対応する逆レーキによって生成された2つの並列ステッパーストリームから7つのグライダーが反映されます。グライダーとステッパーの流れが衝突すると、一連のブロックが形成されます。





[40]グライダーの反射

おわりに

この記事は、ステッパーのセルオートマトンのかなり表面的な研究の結果を示しています。多くの質問は未解決のままです。例：

• グライダーガンが存在するかどうかは不明です。
• ステッパーやグライダーではない宇宙船は1つも発見されていませんが、不可能だと考える理由はありません。
• 発振器の後ろに機関車が残らない
• 寒天はまったく研究されていません。これらは、平面全体をカバーし、空間と時間で周期的な構成です。
• 食べる人、構成、吸収グライダーまたはステッパーは、彼ら自身を傷つけることなく見つかりませんでした。
• グライダー合成は、ステッパーの助けによる合成と同様に研究されていません。

これらの自由回答形式の質問がステッパーのセルオートマトンの研究にアマチュアを引き付けることを願っています。現時点では、学習したゲームLifeの長さと広さよりも、Steppersでの発見は比類ないほど簡単だと確信しています。

ファイルをダウンロードする

MilhinSA.Golly2.5.zip（48.2 kb）-MilhinSAルールとサンプルrleファイル。

Steppers-catalog.zip（221 kb）-セルラーマシンSteppersの構成のカタログ。

SidorovI.Golly2.5.zip（18.9 kb）-例付きのSidorovIルール。

SidorovI.Science_and_Life_1975.03.djvu（187 kb）-ジャーナルScience and Life、1975.03のI. Sidorovによる記事。