ラングトンのアリ

ラングトンのアントは、非常に単純なルールセットを持ちながら、複雑な動作を見せる2次元チューリングマシンです。 1986年にクリス・ラングトンによって発明され、黒と白のセルの正方格子上で動作します。 ^{[1]このアイデアは、より多くの色と状態を追加する}ターマイトなど、いくつかの異なる方法で一般化されています。

平面上の正方形は、黒または白でさまざまな色で表示されます。ここでは、1 つの正方形を「アリ」と見なします。アリは、1 歩進むごとに、4 つの基本方向のいずれかに移動できます。「アリ」は、以下の規則に従って移動します。

• 白いマス目では、時計回りに90度回転し、マス目の色を反転し、1単位前進します。
• 黒い四角では、反時計回りに90度回転し、四角の色を反転し、1単位前進します。

ラングトンのアリはセルオートマトンとしても説明でき、グリッドは黒または白で色付けされ、「アリ」のマス目には黒/白の状態とアリの現在の移動方向の組み合わせをエンコードするために8つの異なる色のうちの1つが割り当てられています。^[2]

これらの単純なルールは複雑な行動につながります。完全に白いグリッドから始めると 、3つの異なる行動モードが明らかになります。 ^[3]

1. シンプルさ。最初の数百の動きで、対称的な非常に単純なパターンが作成されます。
2. 混沌。数百回の動きの後、黒と白の正方形の大きな不規則なパターンが現れます。アリは、約 10,000 ステップまで疑似ランダムな経路をたどります。
3. 出現する秩序。最終的にアリは、無限に繰り返される 104 ステップの反復的な「ハイウェイ」パターンを構築し始めます。

試験されたすべての有限の初期構成は、最終的に同じ反復パターンに収束し、「ハイウェイ」がラングトンのアリのアトラクターであることを示唆しているが、誰もこれがすべての初期構成に当てはまることを証明できていない。アリの軌道は初期構成に関係なく常に無制限であることだけがわかっている^[4]  – これはコーエン-コング定理として知られている。^[5]

2000年にガジャルドらは、ラングトンのアリの単一インスタンスの軌跡を使用して任意のブール回路を計算する構成を示しました。 ^[2]

グレッグ・タークとジム・プロップは、ラングトンのアリの単純な拡張として、2色だけではなく、より多くの色を使うことを検討した。^[6]色は循環的に変更される。命名には単純なスキームが使われる。連続する色ごとに、左折するか右折するかを示すために「L」または「R」の文字が使われる。この命名スキームでは、ラングトンのアリは「RL」という名前が付けられている。

これらの拡張された Langton のアリの中には、何度も対称になるパターンを生成するものがあります。最も単純な例の 1 つは、アリの「RLLR」です。これが起こるための十分な条件の 1 つは、循環リストとして見られるアリの名前が、連続する同じ文字「LL」または「RR」のペアで構成されていることです。(「循環リスト」という用語は、最後の文字が最初の文字とペアになる可能性があることを示しています) 証明にはTruchet タイルが関係します。

• ラングトンのアリの複数色拡張におけるパターンの例:
• 
  RLR: 無秩序に成長します。このアリが高速道路を生み出すかどうかは不明です。
• 
  LLRR: 対称的に成長します。
• 
  LRRRRRLLR: 周囲の四角形のスペースを埋めます。
• 
  LLRRRLRLRLRL: 複雑な高速道路を作成します。
• 
  RRLLLRLLLRRR: 15900 回繰り返して拡大および移動する塗りつぶされた三角形を作成します。
• 
  L ₂ NNL ₁ L ₂ L ₁ : 六角形のグリッド、円形に成長します。
• 
  L ₁ L ₂ NUL ₂ L ₁ R ₂ : 六角形のグリッド、螺旋状に成長します。
• 
  R ₁ R ₂ NUR ₂ R ₁ L ₂ : アニメーション。

六角形のグリッドでは、最大 6 つの異なる回転が可能です。ここでは、N (変更なし)、R ₁ (時計回りに 60°)、R ₂ (時計回りに 120°)、U (180°)、L ₂ (反時計回りに 120°)、L ₁ (反時計回りに 60°) と表記されています。

ラングトンのアリのさらなる拡張は、チューリングマシンの複数の状態を考慮することです。あたかもアリ自体が変化する色を持っているかのように。これらのアリは「チューリングマシンシロアリ」の短縮形であるターマイトと呼ばれます。一般的な行動には、高速道路の生成、無秩序な成長、螺旋状の成長などがあります。^[7]

• いくつかのターミットの例:
• 
  螺旋状の成長。
• 
  半ば混沌とした成長。
• 
  混乱した成長期を経て高速道路が建設される。
• 
  独特の質感を持つ混沌とした成長。
• 
  拡大するフレームの中に独特の質感をもたせた成長。
• 
  フィボナッチ螺旋を構築します。
• 
  成長するダイヤモンドの構築

複数のラングトンのアリが 2D 平面上で共存することができ、それらの相互作用によって、さまざまな組織化された構造を集合的に構築する複雑な高次オートマトンが生成されます。

それらの相互作用をモデル化する方法は様々であり、シミュレーションの結果は選択に大きく依存する可能性があります。^[8]

2次元平面上では、複数のアリが共存することができますが、それらは出会ったときに何が起こるかを定義するルールがある必要があります。エド・ペッグ・ジュニアは、例えば左右に曲がることができ、出会ったときに2つに分裂して互いに消滅するアリについて考えました。 [ ^9]

• コンウェイのライフゲーム – 2次元セルオートマトン
• ラングトンのループ – 自己複製セルオートマトンパターン
• パターソンの虫 – 摂食行動をモデル化するセルオートマトンファミリー

ウィキメディア・コモンズには、ラングトンのアリとターマイトに関連するメディアがあります。

• ワイスタイン、エリック・W.「ラングトンアリ」。マスワールド。
• クリス・ラングトンが「コロニー」内で相互作用する複数のアリを実演している
• イアン・スチュワートによる「数学的レクリエーション」コラムでは、万物の理論の比喩としてラングトンのアリを使用しています。ラングトンのアリが無限であることの証明が含まれています。
• Langton の Ant の複数色拡張におけるルールを生成するためのすばらしいスクリプト
• DataGenetics、Langton の Ant (および Life)