ラングトンのアリとは？わかりやすく解説

ラングトンのアリ（英: Langton's ant）は、クリストファー・ラングトンが発明した単純な規則で記述される2次元チューリングマシンである。

概要

平面が格子状に構成され、各マスが白または黒で塗られる。ここで、1つのマスを「アリ」とする。アリは各ステップで前後左右のいずれかのマスに移動することができる。アリは以下の規則に従って移動する。

白いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
黒いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。

この単純な規則で驚くほど複雑な動作をする。当初でたらめな動作をしているが、アリはほぼ例外なく10000歩ほどうろついた後に真っ直ぐな「道」を作る動作に入る。これは初期のパターンがどうであろうと殆ど関係ない。このことは、この「道」（highway）が、ラングトンのアリのアトラクタであることを示唆している。

ラングトンのアリはセル・オートマトンと見ることもできる。この場合、背景は白か黒で、アリは向きとそのマスの背景色の組み合わせで8色の状態をとることになる。

以下の図は3匹のラングトンのアリの動きを示したものである（色は識別のためにつけているが、上記の説明で白いマスとされているものがアリによって違う色になっているだけである）。

ラングトンのアリの拡張

2色でなくもっと多数の色を使うような単純な拡張が存在する^[1]^[2]。この場合、色の変化は反転ではなく循環となり、アリの動きは各色ごとに右か左に向きを変えて1マス進むことになる。これを色の順に L（左）と R（右）を並べて表す。オリジナルのラングトンのアリの規則は、従って「RL（黒白）」になる。

このように拡張したラングトンのアリの中には常に対称なパターンを何度も生み出すものがある。例えば規則「RLLR」のアリがそのような動作をする。'LL' および 'RR' という文字列で規則が構成されている場合、このような振る舞いを見せるとわかっている（RLLRの場合、最後の R は最初の R と繋がっている。なぜなら最後の色は最初の色に変化するため）。

脚注

^ Gale, D.; J. Propp, S. Sutherland, S.Troubetzkoy (1995). “Further Travels with My Ant”. Mathematical Entertainments column, Mathematical Intelligencer 17: 48–56.
^ 別冊日経サイエンス　コンピューターレクリエーションIV　遊びの展開　「2次元チューリングマシンとチョロアリが平面に描く軌跡」

外部リンク

Paterson's worms^{[リンク切れ]}
Further Travels with my Ant 上述の対称なパターンについての考察
http://www.theory.org/software/ant/
http://www.math.sunysb.edu/~scott/ants/
http://www.hut.fi/~jblomqvi/langton/index.html Java applet ^{[リンク切れ]}
http://www.ing-mat.udec.cl/~anahi/langton
“Langton's Ants - in Javascript · Ross Scrivener” (英語) (2012年2月26日). 2019年1月7日閲覧。 Javascriptで任意のデモを試すことが出来る

[1] Gale, D.; J. Propp, S. Sutherland, S.Troubetzkoy (1995). “Further Travels with My Ant”. Mathematical Entertainments column, Mathematical Intelligencer 17: 48–56.

[2] 別冊日経サイエンス　コンピューターレクリエーションIV　遊びの展開　「2次元チューリングマシンとチョロアリが平面に描く軌跡」

[1]

[2]

ラングトンのアリとは？ わかりやすく解説