ISEGORIA / 数学百科事典
セル・オートマトン：局所規則から生まれる計算
隣のセルしか見ないのに、計算し、成長し、渋滞するセルの格子を扱います。256 個の初等ルールとその対称性、グライダーと銃をもつコンウェイのライフゲーム、一万歩の混沌ののちに高速道路を作るラングトンのアリ、そして厳密な基本図をもつ交通モデルとしてのルール 184 を調べます。
前提知識: 論理と計算可能性、初等的な確率
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. 256 個の初等ルール
0 か 1 の値をもつセルの一列を、一斉に更新します。各セルの新しい値は、自分と両隣の古い値だけで決まります。近傍は 2³ = 8 通りあり、ルールはそれぞれに出力を割り当てるので、ルールは 2⁸ = 256 個です。ウルフラムは 111 を先頭にして八つの出力を二進数として読み、ルールに番号を付けました。図の上のアイコンがルールそのものです。どの出力でもクリックして反転できます。時間は下向きに進みます。ルール 90 は一つのセルからシェルピンスキーの三角形を描き、ルール 30 は中央の列がランダムに見え、ルール 110 は相互作用する粒子を支えてチューリング完全です。再生を押すと行が現れていきます。
計算例. ルール 90 の出力は 01011010 なので \(f(a,b,c)=a\oplus c\)、つまり各セルは両隣の和 mod 2 です。一つの 1 から始めると時刻 \(t\) の行はパスカルの三角形の第 \(t\) 行 mod 2 で、\(2^{s(t)}\) 個の 1 を含みます。\(s(t)\) は \(t\) の二進展開に含まれる 1 の個数です。ルール 30 は \(f=a\oplus(b\lor c)\) で、中央の列は 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 と始まります。
注意点. 行は端でつながっているので、端に達した模様は反対側から入ってきます。一つのセルから始める場合は、表示する行の範囲では何も回り込まないように幅を選んでいます。左右を鏡映しにしたり 0 と 1 を入れ替えたりするとルール番号は変わりますが振る舞いは変わりません。256 個のルールは 88 個の同値類に分かれ、表示はその類の最小の番号を示します。ウルフラムの四つのクラス（一様、周期的、混沌的、複雑）は典型的な振る舞いの記述であって定理ではありません。同じルールでも初期行が違えば振る舞いが変わることがあり、クラスを一般に判定することは決定不能です。
本質的に異なる初等ルールが 256 個ではなく 88 個なのはなぜですか？
相対的な付け替えを除いて力学を変えない対称性が二つあります。\(a\) と \(c\) の役割を入れ替える鏡映と、入力と出力の両方で 0 と 1 を入れ替える補集合です。二つは合わせて 256 個のルールに作用する位数 4 の群を生成し、バーンサイドの補題が軌道を数えます。\((256+64+16+16)/4=88\) で、四つの項は恒等変換、鏡映（100/001 と 110/011 の対が一致する必要があるので \(2^6\)）、補集合（\(2^4\)）、その積（\(2^4\)）で固定されるルールの個数です。
2. コンウェイのライフゲーム
正方格子の各セルは八つの隣人を数えます。生きたセルは生きた隣人が 2 個か 3 個なら生き残り、それ以外なら死にます。死んだセルは生きた隣人がちょうど 3 個なら誕生します。それ以外は何も決めていないのに、このルールは四世代ごとに斜めに一マス進むグライダー、落ち着くまでに 1103 世代かけて成長する五つのセルの R ペントミノ、そして 30 世代ごとにグライダーを永遠に撃ち出すゴスパーの銃を支えます。どのセルでもクリックして反転させ、再生を押してください。右のグラフは個体数を記録します。ルールを変えると B3/S23 がどれほど特別かが分かります。Seeds は爆発し、Day & Night は生死の入れ替えについて対称です。
計算例. グライダーは 5 個のセルです。四世代後に同じ五つのセルが一行一列ずれて再び現れるので、速さは \(c/4\)、つまり一世代に一マスという光速の四分の一です。4 個のセルのブロックは決して変わりません。生きた各セルはちょうど 3 個の生きた隣人をもち、隣接する死んだセルの隣人は高々 2 個だからです。横に並んだ三つのセルのブリンカーは縦の三つになり、また戻ります。周期 2 です。
注意点. ここでの格子は 64 × 40 で端がつながっているので、右から出たグライダーは左から入り、置いてきたものと衝突することがあります。ライフゲームは無限の平面で定義され、そこでは銃のグライダーは永遠に飛び去ります。R ペントミノが最終的な個体数 116 に達するにはこのトーラスより広い場所が必要なので、ここでは違う形に落ち着きます。ライフゲームはチューリング完全であり、任意のパターンからの長期的な振る舞いは決定不能です。第 \(t\) 世代の個体数を与える公式はなく、計算するしかありません。
ライフゲームでは一世代に一マスより速く進めるものがなく、グライダーがそれより遅いのはなぜですか？
セルが誕生できるのは、その 3 × 3 近傍にすでに生きたセルがあるときだけなので、生きたセルの集合は一世代に各方向へ高々一マスしか広がりません。これが光速 \(c\) です。速さ \(c\) で動くパターンは毎世代新しい前線でちょうど三つの親から誕生し、後ろに生きたものを何も残さない必要があります。前線の三つの親に何ができるかを詳しく調べると、ライフゲームのどんなパターンも縦横方向に \(c/2\)、対角線方向に \(c/4\) より速くは動けないことが分かります。グライダーは形を一マス隣に作り直すのに四世代を要するので、対角線方向の上限をちょうど達成しています。
3. ラングトンのアリ
白いセルの格子の上にアリがいます。各ステップでアリは、白いセルなら右に、黒いセルなら左に向きを変え、いるセルの色を反転させ、一マス前に進みます。これがルールのすべてで、しかも可逆です。逆向きに動かすとアリは来た道を戻ります。およそ一万歩の間、アリは対称に見える塊、次いで混沌とした乱れを描きます。そしておよそ一万歩ののちに高速道路、すなわち周期 104 の斜めの帯を作り始め、それを永遠に延ばし続けます。ステップのスライダーをドラッグするか再生を押してください。右のグラフは黒いセルを数え、表示は高速道路が始まったかどうかを示します。
計算例. 各ステップはちょうど一つのセルを反転させるので、黒いセルの数は \(\pm1\) ずつ変わり、ステップ数と同じ偶奇をもちます。11,000 歩のあとでは偶数です。高速道路は 104 歩ごとに斜めに二マスずれて繰り返すので、高速道路に乗ってからはアリの原点からの距離は 104 歩ごとに \(2\sqrt2\) ずつ増え、黒いセルの数は一周期ごとに 12 増えます。
注意点. ここでの格子は有限で、高速道路はいずれ端に達しますが、スライダーはその手前で止まります。このアリについて証明されていることは、見えていることより少ないのです。コーエンとコンの定理は、黒いセルが有限個のどんな初期配置からでも軌道は非有界であると述べますが、どんな有限の初期配置からでも必ず高速道路が現れることは、試したすべての場合に支持された予想にすぎません。初期パターンを変えてみてください。黒い正方形からは二千歩足らずで高速道路が現れますが、ランダムな区画からは高速道路が走り出しても古い残骸にぶつかり、実行が終わる前に混沌へ溶け戻ることがあります。
アリの経路が非有界でなければならないのはなぜで、なぜそれは高速道路の証明にならないのですか？
アリが有界な領域にとどまると仮定します。すると状態（位置、向き、有限個のセルの色）は有限個で、有限集合上の可逆写像は置換なので、運動は周期的です。格子を市松模様に塗ると、アリは横の移動と縦の移動を交互に行うので、周期的な経路に沿ってセルは一貫した模様をなし、最も端の角のセルは毎回同じ側から入って同じ側へ出なければならず、一方向からしか入れないことになります。これは向きを変えるルールに反します。よって有界な周期運動は存在しません。非有界性はアリが遠くへ行くことを言うだけで、どのように行くかは言いません。高速道路は遠くへ行く一つの方法にすぎず、もっと遅く乱雑な脱出を排除するものはありません。
4. 交通としてのルール 184
環状道路に車を置きます。一つのセルに車は一台までで、前のセルが空いていれば各車は一ステップに一マス進みます。これが初等ルール 184 で、車の数を保存します。時間が下向きの時空図では、自由に流れる車は右下がりの線で、渋滞は濃い帯です。渋滞の中のどの車も前に進むか止まるかしかしないのに、渋滞の先頭は一ステップに一マスずつ後ろへ動きます。右には流量、すなわち一ステップにある地点を通過する車の数を密度に対して描いています。密度 1/2 未満ではやがてすべての車が動き、流量は ρ に等しくなります。1/2 を超えるとすべての隙間が後ろへ動き、流量は 1 − ρ です。金色の点をドラッグして ρ を変えてください。ランダムな減速を入れると、厳密な三角形が実際の道路の丸みを帯びた曲線に変わります。
計算例. 200 セルの環に 70 台なら \(\rho=0.35\) です。高々 100 ステップのうちに渋滞は解消し、すべての車が毎ステップ動き、測定される流量はちょうど 0.35 です。130 台なら \(\rho=0.65\) で、70 個の隙間が毎ステップ後ろへ動き、流量はちょうど \(1-0.65=0.35\) です。止まった車で満ちた道路から、同じ流量が得られます。
注意点. ルール 184 の最高速度は一ステップに一マスで、反応時間もないので、基本図は完全な三角形で、渋滞が自然に成長することはありません。\(\rho=1/2\) での最大流量 1/2 はルールの性質であって運転者の性質ではありません。ナーゲルとシュレッケンベルクの模型は確率 \(p\) のランダムな減速を加えます。走っている車が理由もなく減速することがあるのです。このただ一つの追加が、自由な流れの中から現れる渋滞、\(p\) に依存して決して 1/2 に達しない流量、そして実測値の散らばりを生み出します。表示する流量は、過渡状態を捨てたあとの最後の 100 ステップの平均です。
渋滞の中のどの車も前へ進むのに、渋滞が後ろへ動くのはなぜですか？
ルール 184 を車ではなく隙間について読み直してください。隙間は、その左のセルに車があるときにちょうど一マス左へ動きます。これは車のルールの鏡像です。つまり空のセルは同じ速さで逆向きに流れる第二の流れであり、渋滞の先頭は隙間が到着する場所です。密度 1/2 を超えると隙間は車より少なく、どの隙間の左にも常に車があるので、すべての隙間が毎ステップ動き、流量は隙間の密度 \(1-\rho\) です。