パターソンワーム

パターソンのワームは、 1971 年にマイク パターソンとジョン ホートン コンウェイによって考案されたセル オートマトンの一種で、先史時代の特定のワームの行動と摂食パターンをモデル化するために考案されました。このモデルでは、ワームは食物を表す線分に沿って三角形のグリッド上の点の間を移動します。ワームの方向転換は、ワームが現在いる点に隣接する、食べられた線分と食べられていない線分の構成によって決まります。単純なルールで制御されているにもかかわらず、ワームの行動は極めて複雑になる可能性があり、1 つの変種の最終的な運命はまだわかっていません。

このワームは1970年代初頭にパターソン、コンウェイ、マイケル・ビーラーによって研究され、1973年6月にビーラーによって記述され、^[1] 1973年11月にサイエンティフィック・アメリカン誌のマーティン・ガードナーの「数学ゲーム」コラムで発表されました。^[2]

エレクトロニック アーツの 1983 年のゲーム「Worms?」は、パターソンのワームをインタラクティブに実装したもので、ワームがルールのない方向に曲がるたびに停止し、ユーザーが方向を選択できるようにして、そのワームにそのルールを設定します。

パターソンのミミズは、先史時代のミミズの行動をシミュレートする試みである。これらの生物は池の底の堆積物を食べ、すでに通った道をたどることは避けた。そこには食べ物が乏しいからである。しかし、食べ物はまばらにあるため、ミミズにとっては以前の道の近くに留まることが利益となる。ミミズの種類によって、通った道からどれだけ離れるか、いつ方向転換するか、どれだけ急に方向転換するかなど、生来のルールが異なる。^[1] 1969年、ラウプとセイラチャーは化石化したミミズの道のコンピューターシミュレーションを作成し、このシミュレーションに触発されてパターソンとコンウェイは規則的なグリッド上の理想的なミミズを研究するための簡単なルールセットを開発した。^[3]

コンウェイのオリジナルのモデルは直交グリッド上のワームだったが、これでは3種類のワームしか生成されず、いずれもあまり面白くない行動を示した。パターソンは三角形グリッド上のワームを考えた。^[1]パターソンのワームはビーラーによってマサチューセッツ工科大学の AIメモ(#[1])で説明され、1973年11月にマーティン・ガードナーの「数学ゲーム」コラム「サイエンティフィック・アメリカン」で発表され、^[2]後にガードナー1986に再掲載された。^[4]これらのシミュレーションは、細胞と細胞間の関係に焦点を当てた同時期に開発された他のセルオートマトンとはアプローチが異なっていた。^[5]このような単純なコンピュータモデルは実際の生物の行動を正確に記述するには抽象的すぎるが、非常に単純なルールでさえ、その軌跡に似たパターンを生じさせることができることを実証している。^[6]

ワームは無限の三角形のグリッドのどこかの点から出発します。ワームは各点で交わる 6 つのグリッドラインの 1 つに沿って移動を開始し^[6]、1 単位の距離を移動すると新しい点に到着します。ワームは次に、通過したグリッドラインと通過していないグリッドラインの分布に基づいて、どの方向に進むかを決定します。方向はワームの視点からの相対的なものです。ワームがこれまでにこの分布に遭遇したことがない場合は、通過していないグリッドラインに沿って移動することができます。それ以降、ワームがその分布に再び遭遇した場合は、同じ方法で移動する必要があります。通過していないグリッドラインがない場合、ワームは死に、シミュレーションは終了します。^[1]

新しいタイプの交差点に遭遇したときにどの方向に曲がるかによって、ワームには多くの異なるタイプがあります。ワームのさまざまな種類は、すべての方向に番号を割り当て、新しいタイプの交差点に遭遇するたびに選択された方向をリストすることで体系的に分類できます。^[7]

6 つの方向には、次のように番号が付けられています。

したがって、方向0はワームがまっすぐ進み続けることを示し、方向1はワームが 60° 右折することを示します。他の方向についても同様です。ワームは、方向3はワームが通過したばかりのグリッドラインであるため、その方向には移動できません。したがって、ルール {1,0,5,1} を持つワームは、最初に選択を行う必要があるときは方向 1 に移動し、次に選択を行う必要があるときは方向 0 に移動し、以下同様に続きます。使用可能なグリッドラインが 1 つしかない場合、ワームはそれを選択するしかなく、通常は明示的にリストされません。

ルールセットが0で始まるワームは、永遠に直線を描き続けます。これは些細なケースなので、通常はワームは、食べられていないグリッド線のみがある点に遭遇したときに方向転換しなければならないと規定されています。さらに、鏡像対称の重複を避けるために、ワームの最初の方向転換は右折でなければなりません。^[1]ワームは、3 回目に原点に戻ると、未通過のエッジがなくなるため、死にます。ワームにとって致命的になり得るのは原点だけです。^[8]

ワームルールの組み合わせは1,296通りあります。^[4]これは次の議論からもわかります。

1. ワームが、食べたばかりのセグメント以外に食べられたセグメントがないノードに遭遇した場合、ワームは急に曲がることも、緩やかに曲がることもできます。これは、上の図に示されている状況です。左または右の最初の選択によって、単純に互いを鏡像にした組み合わせが生成されるため、実質的には違いはありません。
2. 食べられたセグメントが 1 つあるノードに遭遇した場合、残りの 4 つのうちのいずれかに沿って移動できます。ワームが最初に起点に戻るときのみ、この特性があります。
3. 2 つのセグメントが食べられている場合、食べられているセグメントの位置が重要です。存在できる 2 つのセグメントの交差点のタイプは、最初のルールによって生成されるものだけです。この交差点には 4 つの異なる進入方向があり、それぞれに 3 つの出発方向の選択肢があります。これにより、ルールを選択する際に 81 通りの選択肢が考えられます。
4. ワームが元の場所に戻ると、食べられた 3 つの部分に遭遇し、その分布に関係なく、食べられていない残りの 2 つの部分から選択する必要があります。
5. 食べられた部分が 4 つある場合、食べられていない部分は 1 つだけ残り、虫はそれを食べなければなりません。

したがって、ルールの組み合わせは 2×4×81×2x1=1,296 通りある。その多くは他のルールの鏡像的な複製であり、ルールセット内のすべての選択を行う前に消滅するルールもあるため、411 の異なる種が残る（無限直線ワームを含めると 412）。^[8]これらの種のうち 336 は最終的に消滅する。73 のパターンは無限の挙動を示す。つまり、元の状態に戻らない繰り返しパターンに落ち着く。さらに 2 つは無限であると強く信じられており、1 つは未解決のままである。11 のルールは複雑な挙動を示す。これらは何十億回も繰り返した後でも消滅せず、明らかに無限のパターンを採用することもない。これらの最終的な運命は、2003 年に Benjamin Chaffin が新しい解決方法を開発するまで不明であった。何時間ものコンピュータ処理の後、11のルールのうち9つが解かれ、ワームには{1,0,4,2,0,2,0}と{1,0,4,2,0,1,5}のルールが残った。^[7]最初のルールはTomas Rokickiによって解かれ、57兆（5.7×10 ¹³）のタイムステップ後に停止し、{1,0,4,2,0,1,5}のみが未解決のままであると判定された。Rokickiによると、ワームは5.2×10 ^{19 のタイムステップ後もまだアクティブである。彼は}Bill GosperのHashlifeに基づくアルゴリズムを使用して、並外れた速度でワームをシミュレートした。^[8]この動作は、最長パスがわずか16セグメントである関連する長方形グリッドワームよりもかなり複雑である。^[6]

2 種類の異なるワームが同じ経路を形成することは可能ですが、必ずしも同じ順序で移動するとは限りません。^[1]最も一般的な経路は、最短経路でもあります。7 点式MOT テスト/核シェルターのシンボルです。^[4]この経路の一例が、上のアニメーション図に示されています。合計で 299 種類の経路があり、そのうち 209 種類は 1 種類のワームによって形成されています。^[1]

• 忙しいビーバー – 特定のサイズで最も長く稼働するチューリングマシン
• ラングトンのアリ – 創発的な動作を持つ 2 次元チューリング マシン
• チューリングマシン – 抽象マシンを定義する計算モデル
• Turmite  – 2次元グリッド上のチューリングマシン

• Rokicki のワームページ
• スヴェンのワームページ