6x6のラップアラウンド・セル・オートマトン・グリッドにおける固有状態の最大シーケンスは1,717であり、この結果はグリッドが大きくなるにつれて複雑さが爆発的に増大するという予測に疑問を投げかけるものである。この発見は、有限の空間に単純なルールを適用した場合でも、特定の数学的特性がいかに創発的な挙動を制限し得るかを浮き彫りにしている。
トーラス・セル・オートマトンのメカニズム
セル・オートマトン（CA）は、それぞれ「生存」または「死亡」の状態をとることができる「セル」のグリッドで構成される。これらの小規模グリッドモデルでは、各セルは角や端にあるものを含む8つの隣接セルを持つ。グリッドは水平方向および垂直方向の両方でラップアラウンドするため、幾何学的にはトーラスとして機能する。
この画像は、端のセルが反対側のセルと相互作用するトーラス幾何学を示している。
コンウェイの「ライフゲーム」のいくつかのバージョンとは異なり、これらのセルは自身の以前の状態を追跡しない。次のターンは、特定のルールに従って、現在生存している隣接セルの数がいくつであるかのみによって決定される。このルールとは、どの隣接セルの数が次ステップで「生存」状態をもたらすかを定義する一連の指示のことである。
このGIFは、メカニズムのセクションで説明されているセル・オートマトン・システムにおける状態の動的な進化を例証している。
「最も長い6x6のチェーンと最も長い5x5のチェーンの比率は、4x4と3x3の比率ほど大きくさえない。」
— Small-Grid Wraparound Cellular Automata
対称性の削減と計算戦略
パターンが繰り返される前に得られる最長のシーケンスを特定するために、研究者は機能的に同一な開始点をフィルタリングしなければならない。平行移動、回転、反転、および反転を考慮することで、固有の開始構成の数を劇的に減らすことができる。例えば、対称性のフィルタリングにより、4x4のケースは65,536からわずか805の固有構成へと削減された。
反転も重要なショートカットを提供する。ルールと開始構成の両方が完全に反転（すべての生存/死亡の状態を入れ替える）している場合、それらは同じパターンを生成する。これにより、正確性を維持しながら、ルールと構成の全探索空間を大幅に分割することが可能になる。
複雑性の傾向と割り切れる因子の影響
この研究は、グリッドサイズ間における複雑性の非線形な成長を明らかにしている。4x4（14状態）から5x5（916状態）への移行は、混雑が減少するにつれて爆発的な拡大を示す一方で、6x6への跳ね上がりはわずか1,717状態にとどまる。この緩やかな増加は、割り切れる性質が状態の多様性を制限する役割を果たしている可能性を示唆している。
HN Digestによる図（justismills.substack.comの報告数に基づく）; 数値はソースの表記通りです。
一つの理論は、6のような高度に割り切れる数字は、5のような素数よりもグリッドを予測可能な挙動にさせるというものである。もし6x6グリッドがより小さなサブグリッドによって完全にタイル状に構成されていれば、それらのセクションは独立して動作する可能性があり、それによって、あまり「規則的」ではない幾何学的構造と比較して、最大可能なシーケンス長が事実上制限されることになる。
大規模グリッドの計算上の限界
小規模なケースはブルートフォースとAIの最適化を通じて解決されているが、より大きなグリッドは依然として手つかずである。7x7グリッドにおける20,000の開始構成のランダムサンプルでは、すでに545,000ステップ以上のシーケンスが得られており、高い複雑性が示されている。
7x7グリッドの正確な最大値を求めるには、現在、多大なリソースが必要である。推定では、高度なエンジニアリングの突破がない限り、標準的なCPUでは数百年、連続的なGPU時間では約5年を要するとされている。