ラングトンの蟻

盤の上を1匹のアリが歩く。規則は2行しかない。 白いマスに来たら右へ90度、黒いマスに来たら左へ90度。曲がったらそのマスの色を反転して、1マス前へ。 それだけ。この規則を回すと、アリは1万ステップ近くのあいだ、 どこにも秩序の見当たらない模様を描き続ける。そしてあるとき突然、幅の決まった一本道を斜めに引きはじめ、二度と戻ってこない。 誰も「道路を作れ」とは書いていない。

盤面。橙の三角がアリで、頂点が進行方向。マスの色は状態を表す。 端はトーラス（右端の隣は左端）なので、アリはいずれ一周して自分の作った模様に戻ってくる。

状態
ステップ0
出発点からの距離0
塗られたマス—

高速道路：未検出

盤面の一周：まだ

約1万ステップの混沌のあと、周期104の高速道路が生まれる。

RL のまま速度を上げて放っておく。 1万ステップ手前まではただの染みにしか見えないのに、 ある瞬間から斜めの帯が伸びはじめる。同じ規則を回し続けているだけで、途中で何も変えていない。

逃走の記録

出発点からアリまでの距離を、時間に対して描いたもの。 混沌の相では、アリは自分の作った模様のなかを行ったり来たりするので、この線はほとんど横ばいで揺れる。 高速道路が始まると、アリは毎周期きっかり同じだけ遠ざかるので、線が折れて直線になる。 相転移の瞬間が1本の折れ線として見える。

アルゴリズムと実装

Christopher Langton が1986年に提示した、2次元チューリングマシンとも読めるセルオートマトン。 状態を持つ「頭」が盤面を歩き、足元のマスを読んで書き換えながら動く。

規則

1ステップは、足元のマスの状態を見て次の3つを順に行うだけ。

  1. 回転 — 状態0（塗られていない）なら右へ90度、状態1（塗られている）なら左へ90度。
  2. 書き換え — 足元のマスの状態を次の状態へ。2状態なら単に反転。
  3. 前進 — 回転後の向きに1マス。
状態0の上・上向き 右へ90°・塗って・前進
規則の1文字目 R：状態0のマスでは右へ。
状態1の上・上向き 左へ90°・戻して・前進
2文字目 L：状態1のマスでは左へ。塗りは状態0へ戻る。

向きの持ち方

向きは 0=上, 1=右, 2=下, 3=左 の整数1個。 時計回りに並べてあるので、右折は (dir + 1) & 3、左折は (dir + 3) & 3 で済む。 左折を -1 ではなく +3 と書くのは、負の剰余を避けるため。 移動は方向ごとの差分表 dx = [0, 1, 0, -1]、dy = [-1, 0, 1, 0] を引くだけ （画面座標なので上は y が減る向き）。

規則文字列 — 一般化ラングトンの蟻

規則を RL という2文字の文字列とみなすと、そのまま多状態へ広げられる。 長さ n の文字列に対してマスは n 状態を持ち、状態 s のマスに来たら 文字列の s 文字目の向きへ曲がり、状態を (s + 1) mod n にする。 n = 2 で RL と書けば元のラングトンの蟻に戻る。

文字列を変えると挙動は劇的に変わる。LLRR は対称な模様を保ったまま成長し、 LRRRRRLLR は縁のそろった正方形を埋めていき、RLR はいつまでも混沌のまま広がる。 規則の長さや L と R の比といった単純な指標からは、どれになるかを言い当てられない。

盤面と描画

  • 盤面は長さ N² の Uint8Array 一本。座標 (x, y) は y * N + x。
  • 描画は毎フレーム全マスを走査しない。N×N ピクセルの ImageData を1枚持ち、 マスの状態が変わった瞬間に対応する4バイトだけ書き換える。 フレーム末に putImageData して、それを表示用キャンバスへ拡大して1回貼る。
  • 拡大時は imageSmoothingEnabled = false。 これを切らないと1マスが隣とにじみ合い、1ピクセル幅の高速道路が消えてしまう。
  • 1フレームに数千ステップ進めても、コストは「変わったマスの数だけの4バイト書き込み」と 1回の貼り付けに収まる。fillRect をステップごとに呼ぶ実装とは桁が変わる。

本当は無限の盤面

このモデルの盤面は本来無限に広い平面で、そこがミソでもある。 画面に収めるためにここではトーラス（Schellingの分居モデルと同じく端がつながった盤）にしているので、 高速道路はいずれ端から反対側へ回り込み、自分が昔描いた模様に突っ込む。 そこで規則の前提だった「未踏の白い領域」が尽き、道路は壊れて混沌へ戻る。 これはモデルの性質ではなく有限の盤に押し込めたことによる人工物で、 統計の「盤面の一周」表示はその瞬間を知らせるためにある。

高速道路の検出

高速道路は「アリの状態が周期 p ごとに、同じ変位だけずれて再現される」状態にほかならない。 そこでアリの軌跡だけを見て判定している。折り返しのない絶対座標を履歴に持ち、 128ステップおきに p = 1…400 を小さいほうから試して、次を全部満たす p を探す。

  • 時刻 t, t−p, t−2p, … t−6p で向きがすべて一致する。
  • 連続する6つの区間の変位がすべて等しい。
  • その変位が 0 でない（同じ場所での周回運動を除くため）。

ただしこれだけだと足りない。混沌の相にも、数百ステップだけ小さな周期でまっすぐ進む 偽の高速道路が現れる（周期4程度のものが典型）。 そこで条件を満たした p はいったん候補として保留し、 1024ステップ持ちこたえて初めて確定とする。本物は数万ステップ続くので落ちない。

これは経験則であって証明ではない。盤面の色まで比べていないので、 偶然の一致を拾う可能性は残る。確定後も成り立つか確認し続け、崩れたら取り消す。 表示している開始ステップは 候補が立った時刻 − 6p の推定値。

古典的な RL なら、見つかる周期は 104、 1周期あたりの変位は斜めに2マス、推定開始は 約10000ステップ （文献でよく挙がる値は9977で、この推定の粒度で見ればぴったり重なる）。 盤が十分に広ければ、トーラスの端で一度壊れたあと、 瓦礫のなかからまた新しい高速道路が立ち上がるのも見える。 初期盤面は毎回同じ（全部が状態0）で乱数も使っていないので、 この模様はいつ実行しても1マスの狂いもなく同じ。混沌に見えるが確率は1つも入っていない。

分かっていること、分かっていないこと

アリの軌跡が有界にならないこと、つまりどんな有限の初期配置から始めても アリはいくらでも遠くへ行くことは、Bunimovich と Troubetzkoy によって1992年に証明されている。 証明は「無限回訪れるマスの集合」の端にあたるマスを取り、そこでの出入りの回数を数えて矛盾を導く形をとる。

一方で、必ず高速道路ができるのかは未解決。 白紙から始めた場合に約1万ステップで道路が現れることは何度も観測されているが、 任意の有限初期配置について同じことが言えるかは証明されていない。 規則2行のモデルの、いちばん目立つ振る舞いが未証明のまま残っている。

配色について

マスの状態は「0の次が1」という順序を持つ量なので、色は単一色相の明度ランプにしている （暗いほど若い状態）。状態数は規則文字列の長さで変わるため、凡例に状態番号と曲がる向きを併記して、 色だけに頼らずに読めるようにした。アリだけは唯一の橙で、盤面のどの状態とも衝突しない。