ラングトンのアリベータ

ラングトンのアリについて

ラングトンのアリは規則が2行しかない機械です。白いマスにいれば右に90度、黒いマスなら左に90度向きを変え、いたマスの色を反転させて1マス前進します。クリストファー・ラングトンが1986年、人工生命の研究で紹介しました。このツールの標準規則「RL」がまさにこれで、文字1つが色1つに対応します(0番の色=白でR、1番の色でL)。

リセットすると256×256格子の中央に上向きのアリが1匹置かれます。格子の端は反対側とつながっている(トーラス)ので、アリが外に落ちることはありません。速度スライダーは1フレームで何ステップ計算するかを決め、既定の100なら毎秒約6,000ステップ進みます。

観察1: カオスの後に現れるハイウェイ

最初の数百ステップ、アリは対称に近い小さな模様を描き、やがて不規則な塊を広げていきます。この状態が約1万ステップ続いたあと、アリは突然104ステップ周期の同じ動きを繰り返し、斜め一方向にまっすぐ伸びる帯を作り始めます。これが「ハイウェイ」です。既定速度なら2秒ほどで見られます。

ハイウェイ上でアリは104ステップごとに横2マス・縦2マス進みます。斜め1マスあたり平均52ステップです。このツールのテストコードも、1万1千ステップ後の104ステップで移動量が(±2, ±2)になることを確認しています。

ハイウェイがなぜ生まれるのか、どんな初期状態からでも必ず生まれるのかは証明されていません。証明されているのはより弱い事実で、無限平面ではどんな有限の初期模様から始めても、アリの軌跡は有限の範囲にとどまりません。

観察2: ドーナツ格子でハイウェイが壊れるとき

無限平面ならハイウェイは永遠に続きます。このツールの格子は有限のドーナツなので、ハイウェイは端を越えて反対側から戻り、やがて最初のカオス領域や自分の跡にぶつかります。その瞬間に規則的な動きが崩れ、再びカオスが始まります。別の向きに新しいハイウェイができることもあります。

概算すると、256マスの格子ではハイウェイが一周して塊に届くまで縦横それぞれ200マス近く進む必要があり、1マス52ステップならさらに1万ステップほどかかります。そのため2万ステップ前後で衝突しやすくなります(塊の大きさで前後します)。1024²を選べばずっと長く続きます。

観察3: 色を増やした規則

規則文字列の長さが色の数です。アリはi番の色のマスでi番目の文字どおりに向きを変え、マスをi+1番の色にします(最後の色の次は0番)。L=左、R=右、N=直進、U=Uターンで、最大32色まで使えます。

• RLR: 長く回してもハイウェイを作らず、不規則に広がり続けることが多い規則です。
• LLRR: 4色の規則。RLと形の育ち方を比べてみてください。
• LRRRRRLLR、RRLLLRLLLRRRのような長い規則: 三角形や四角形のような幾何学的な形に育つものがあります。
• NやUを含む規則: 直進やUターンが入ると、まったく違う模様になります。

アリを何匹も放すと

キャンバスを押すと、その場所にランダムな向きのアリが追加されます(最大256匹)。アリたちは1世代に番号順で1ステップずつ動き、同じ格子を塗るので、あるアリが反転させたマスを次のアリがすぐ読みます。2匹だけでも互いの跡を消し合い、ハイウェイができなかったり遅れたりするのはよくあることです。

画面下には「世代」と「移動」が別々に表示されます。アリが10匹なら1世代で10回動くので、移動数は世代数の10倍の速さで増えます(途中で加えたアリは、その時点から加算されます)。速度スライダーは移動の総量を基準にしているため、アリが多いほど世代の進みは遅くなります。

チューリング完全性

ガハルド、モレイラ、ゴレスは2002年の論文で、初期配置をうまく用意すればアリ1匹の軌跡で任意のブール回路を計算できることを示しました。このツールは常に空の格子から始まるため、そうした構成を描いて試すことはできません。

例

使い方

1. 規則プリセットを選ぶか、L・R・N・Uからなる規則を入力します(2〜32文字)。
2. 速度スライダーで1フレームあたりのステップ数を決めます。
3. キャンバスを押してアリを追加し、最初からボタンで空の格子とアリ1匹に戻します。

よくある質問

関連ガイド

• 単純な規則が複雑な世界を生むしくみ: ライフゲームから自然渋滞まで