ラングトンのアリ

ラングトンのアリは、同じ仲間のアリの中で最も単純なものです。空白を0として番号を付けたn色があるとき、規則は色ごとにRかLを1つ割り当てた文字列$r = r_0 r_1 \cdots r_{n-1}$です。ラングトンのアリはRLに当たります。アリがマスpにいて方向dを向いているとき、1歩は次のようになります。

アリに記憶はなく、足元の色しか見ません。ここでは整った模様からもつれへ、そして道へと進む様子を観察できます。逆向きに動かしたり、行く手のマスを塗ったり、別の文字列を試したりもできます。

色はルールの状態を表します。平面に端はなく、反対側へ回り込むこともありません。パネル上部の曲線は、各ステップ後の着色マス数を表します。

空白の平面を上向きに出発すると、アリはまず小さく整った模様を作ります。473歩目のように、半回転で対称になるものもあります。次に、ランダムに見えるもつれが約1万歩続きます。その後9 977歩目からは同じ104歩を繰り返し、1周期ごとに(−2, 2)、つまり左へ2マス、下へ2マスずれます。こうしてハイウェイと呼ばれる斜めの帯を作り、104歩ごとに色付きマスがちょうど12個増えます。繰り返すのはアリの動きと足元の帯だけです。後ろのもつれはその場に残ります。

数周期繰り返しただけでは証明になりません。次の周期で色付きマスに出会い、道を外れるかもしれないからです。そのため、このページは検証後にだけ道が続くことを保証します。直近の周期が終わった時点で、その間に読んだマスをアリの変位だけずらすと、そこには元のマスが周期の開始前に持っていた色が並び、アリも開始時と同じ方向を向いている必要があります。さらに、今後の各周期で前の周期の範囲を越えるマスは、現在空白であり、検証した周期以降のどの周期でも訪れていない必要があります。すると各周期で前とまったく同じ状況に出会うので、同じ動きが永遠に続きます。曲線の破線は繰り返しの開始点です。先に色付きマスがあると、ページはそこを丸で囲み、保証を出しません。

したがって空白の平面については、計算とこの検証を合わせて道が続くことが証明されています。RLでは、色付きマスが有限個ある盤面で試されたものはすべて最後に道を作りますが、どの盤面でもそうなるとは、まだ誰も証明していません。

どの1歩も取り消せます。アリは直前に移動した方向を向いているので、出てきたマスは後ろにあり、そのマスの色は循環の次の色へ進んでいます。1歩戻す操作は

となります。つまり、盤面とアリから1歩前の状態が決まります。逆方向は記録の逆再生ではなく、規則に従ってアリを逆に動かします。

文字を増やすと、訪れるたびにマスは次の色へ進みます。空白の平面から始めても、規則ボタンごとにまったく違う形が育ちます。LLRRは対称に見える模様、LRRRRRLLRはほぼ埋まった正方形、RRLLLRLLLRRRは成長する三角形になります。この3つが最終的にどうなるかは分かっていません。LLRRRLRLRLLRでは約3万歩後に道ができます。

クリス・ラングトンは1986年、人工生命の例としてこのアリを記述しました。