ラングトンのアリは9,976歩のカオスの果てに高速道路を作った。ただし盤が2%散らかっているだけで、30万歩でも作らなかった
約8分で読めます

ラングトンのアリは9,976歩のカオスの果てに高速道路を作った。ただし盤が2%散らかっているだけで、30万歩でも作らなかった

ルールはこれだけだ。

  • 白いマスに来たら、右に90度回り、そのマスを黒くして、1歩進む
  • 黒いマスに来たら、左に90度回り、そのマスを白くして、1歩進む

真っ白な盤の上に1匹のアリを置いて、これを繰り返す。乱数は使わない。記憶も持たない。今いるマスの色だけを見て、右か左かを決める。

このアリが、およそ1万歩のあいだ意味不明な模様を描き続けたあと、突然まっすぐな道を作り始めて、二度と戻ってこない。1986年にクリス・ラングトンが見つけたこの現象は「ハイウェイ」と呼ばれている。

なぜ1万歩なのか。散らかった盤から始めても同じことが起きるのか。実装して測った。

実験に使ったコードの全文はGitHubに置いています。

3つの局面

まず全部白の盤で2万歩。黒マスの数を追う。

横軸がステップ、縦軸が黒いマスの数のグラフ。0から500歩までが緑の帯(対称な模様)、500から9,976歩までが橙の帯(カオス)、そこから先が赤の帯(ハイウェイ)で塗り分けられている。9,976歩の位置に破線が引かれ、そこから黒マス数の増え方が直線的になる

9,976歩でハイウェイが始まった。ここでいうハイウェイの検出は「104歩ごとの変位が一定になり、それが6周期続く」という条件で、実測された変位は (−2,−2)(-2, -2)。104歩ごとに斜めに2マスずつ進む、という周期構造がここから永遠に続く。

見た目の変化はこうなる。

ラングトンのアリのアニメーション。最初は小さな対称的な模様が育ち、次に不規則で角ばった塊が広がっていき、最後に塊の端から斜めにまっすぐな帯が伸び始めて画面外へ出ていく。左上にステップ数と、ハイウェイに入ったことを示す表示がある

局面ごとに切り出すと、質の違いがはっきりする。

5枚の白黒スナップショットを縦に並べた図。400ステップは小さな対称な模様、2,000ステップは角ばった塊、6,000ステップはさらに大きく不規則な塊、11,000ステップでは塊の右下から斜めの帯が伸び始め、20,000ステップでは長い直線の帯が画面を横切っている

最初の数百歩は、左右対称の整った模様を描く。そこから対称性が壊れて、角ばった不規則な塊になる。そして塊の縁から、何の予告もなく道が伸びていく。

足取りを時空図(高さ=ステップ数)にすると、この構造がひとつの絵になる。

下のほうでぐるぐる巻いていた軌跡が、あるところから一直線に伸びる。

盤が散らかっていると、ハイウェイは現れない

真っ白な盤からは必ず1万歩前後でハイウェイが出る。では、最初からいくつか黒マスが撒かれていたらどうなるか。4000×40004000 \times 4000 の盤で、初期の黒マス率を変えながら30万歩まで回した。

横軸が最初に撒いた黒マスの割合(0から50%、対数目盛)、縦軸がハイウェイが始まるまでの歩数(対数目盛)のグラフ。0%で9,976歩、0.1%で4,855歩、0.5%で13,157歩、1%で9,572歩、2%で103,010歩と急増し、5%以上は30万歩の上限に赤い×印が並ぶ

初期の黒マス率ハイウェイまで（中央値）5回中の未到達
0%9,976歩0
0.1%4,855歩0
0.5%13,157歩0
1%9,572歩0
2%103,010歩2
5%以上30万歩でも現れず5

0.1%程度の散らかりはむしろハイウェイを早めることがある(4,855歩)。ところが2%を超えたあたりで急に効かなくなり、5%以上では30万歩まで回しても一度も現れなかった。

ここは慎重に書いておきたい。「現れない」ことを確かめたわけではなく、「30万歩以内には現れなかった」だけだ。実は、有限個のマスが黒く塗られたどんな初期配置からでもアリの軌道は必ず非有界になることは証明されている(Bunimovich and Troubetzkoy, 1992)。だが必ずハイウェイに落ち着くかどうかは未解決で、これまで試されたすべての初期配置でハイウェイが出た、という経験則があるだけだ。

つまり私の実験は、その未解決問題を30万歩の範囲で追試して、確認できなかったという結果になる。撒いた黒マスが多いほど、秩序が現れるまでの時間が急激に伸びる。

曲がり方の並びを変える

「白なら右、黒なら左」を RL という文字列で表すと、色を増やして LLRR や RRLLLRLLLRRR のような一般化ができる。これはTurmiteと呼ばれている。同じ6万歩で比べた。

6枚の模様を並べた図。ルールRLは細長い直線の道を含む塊、RLRは細かい格子状の模様、LLRRは小さく整った菱形、LRRRRRLLRはほぼ正方形に密に塗りつぶされた領域、LLRRRLRLRLLRは縦に細長い模様、RRLLLRLLLRRRは丸みを帯びた渦状の模様になっている

ルール到達範囲塗られたマスハイウェイ
RL1008×9806,4869,976歩で発生
RLR97×632,740なし
LLRR33×45845なし
LRRRRRLLR99×999,771なし
LLRRRLRLRLLR306×434,674なし
RRLLLRLLLRRR115×1263,685なし

6万歩の範囲では、ハイウェイを作ったのは古典的な RL だけだった。LLRR は33×45の小さな範囲に整った模様を作ってそこに収まり、LRRRRRLLR は99×99をほぼ埋め尽くす。同じ枠組みで文字を1つ変えただけで、広がり方も模様の質もまったく別物になる。

RL の到達範囲だけが1008×980と桁違いなのは、ハイウェイに乗って遠くまで行ったからだ。他のルールは6万歩ぶん歩いても、100マス四方から出ていない。

まとめ

  • 全部白の盤から9,976歩でハイウェイが始まった。104歩あたり (−2,−2)(-2,-2) の周期構造
  • 経過は「対称な模様(〜500歩)→カオス(〜9,976歩)→ハイウェイ」の3局面
  • 初期に黒マスを0.1%撒くとむしろ早まる(4,855歩)が、2%で103,010歩、5%以上では30万歩でも現れない
  • 「どんな初期配置でも軌道は非有界」は証明済み(Bunimovich and Troubetzkoy, 1992)だが、「必ずハイウェイになる」は未解決のまま
  • ルール文字列を変えた6種のうち、ハイウェイを作ったのは古典的な RL だけだった

0.1%の散らかりがハイウェイを早めた。 ここで長く手が止まった。9,976歩が4,855歩になる。ノイズが秩序の形成を助けている。

一方で2%になると10万歩かかり、5%では30万歩でも出てこない。つまり「少しの乱れは秩序への近道になるが、ある量を超えると秩序そのものが遠のく」という非単調な関係がある。どこかに折り返し地点がある。

もっと落ち着かないのは、その折り返しがどこにあるのかを、私は説明できないことだ。アリのルールは2行しかない。乱数も記憶もない。それでも「なぜ1万歩なのか」「なぜ2%で壊れるのか」に答えられない。完全に書き下せる規則から、書き下せない振る舞いが出てくる。

自分が書いたコードなら中身は分かっているはずだ、という感覚は、たぶんこのあたりで役に立たなくなる。分かっているのは規則のほうだけで、規則が作るものは別物として観測するしかない。

関連記事

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。