序論：計算の宇宙と単純な規則のパラドックス

伝統的な科学的直感は、複雑な振る舞いを示すシステムには、それに相応する複雑な基礎規則が存在するはずだという仮定に依存してきた。しかし、20世紀後半から始まった計算実験の進展、とりわけスティーブン・ウルフラムによる『A New Kind of Science』（NKS）の提示は、このパラダイムを根本から覆した1。セルオートマトン（Cellular Automata, CA）の研究によって明らかにされたのは、極めて単純な決定論的規則から、ランダムで予測不可能なほど複雑な構造が生成されるという事実であった。この現象はCAに限定された特殊な事例ではなく、計算という概念そのものに内在する普遍的な性質である可能性が高い2。

本報告書では、セルオートマトン以外の多様な単純計算系、すなわちモバイル・オートマトン、チューリング・マシン、置換系（Substitution Systems）、タグ系、およびレジスタマシンなどを網羅的に調査し、それらの形式的差異を超えて共通に見られる複雑性の発現プロセスを分析する。また、これらのシステムが示す挙動が、いかにして「計算的等価性原理（Principle of Computational Equivalence）」という統一的な概念へと収束するのかを論じ、複雑性が普遍的な現象であるという問いに対する決定的な解を提示する。

モバイル・オートマトン：更新の局所性と情報の伝播メカニズム

モバイル・オートマトン（Mobile Automata, MA）は、セルオートマトンに似た離散的な計算モデルであるが、情報の更新プロセスにおいて「並列性」を排し、「逐次性」を極限まで追求した点に特徴がある4。CAでは格子のすべてのセルが毎ステップ同時に更新されるのに対し、MAでは常に一つの「活性セル（Active Cell）」のみが更新の対象となり、その活性点がルールに従って空間を移動していく4。

モバイル・オートマトンの形式的定義と動作

モバイル・オートマトンは、状態（色）を持つ一次元のセル列と、その中の特定の位置を示す活性スキャナーで構成される。各ステップにおいて、システムは以下の規則に従って遷移する。

  1. 現在の活性セルとその左右の隣接セルの状態を参照する4。
  2. ルールに基づき、活性セルの新しい色を決定する6。
  3. ルールに基づき、活性スキャナーを左、右、あるいはその場に移動させる4。

2つの状態を持つMAにおいて、この局所的な近傍を参照するルールの総数は65,536通り存在する4。この膨大なルール空間を網羅的に探索すると、CAで見られたのと同様の階層的な挙動が観察される。

挙動の分類 空間パターンの特徴 複雑性のレベル
定常・反復型 活性セルが狭い範囲に留まり、単純な周期軌道を描く4。 低（クラス1・2相当）
入れ子（ネスト）型 活性セルが規則的に往復しながら範囲を広げ、自己相似的なパターンを形成する6。 中（フラクタル構造）
複雑・ランダム型 活性セルの移動は規則的に見えても、背景に残される色の分布が統計的にランダムになる6。 高（クラス3・4相当）

###

複雑性の希少性と一般化モバイル・オートマトン

注目すべき点は、モバイル・オートマトンにおいて「複雑な挙動」を示すルールの出現頻度が、セルオートマトンに比べて著しく低いことである6。MAでは、ほとんどのルールが単純な反復やネスト構造に収束し、カオス的あるいは複雑なパターンを生成するものは数パーセントにも満たない6。これは、情報の更新が一点に限定されているため、情報の拡散と干渉が起こりにくいことに起因する。

この制約を緩和するために考案されたのが「一般化モバイル・オートマトン（Generalized Mobile Automata）」である。このモデルでは、活性セルが同時に複数存在することを許容し、条件によって活性セルが分裂したり消失したりする6。活性セルの数が増加し、情報の並列処理能力が高まるにつれて、システムの挙動は急速にセルオートマトンのそれに近づき、複雑なパターンの出現率も劇的に向上する6。この事実は、複雑性の発現には「情報の並列性」が有利に働くものの、極限まで制約された逐次システムであるMAであっても、適切なルールを選択すれば、依然として複雑な振る舞いを生成できることを示唆している5。

チューリング・マシン：計算の最小単位と万能性の極限

計算理論の象徴であるチューリング・マシン（Turing Machines, TM）もまた、単純な規則から複雑な振る舞いを生むシステムの典型である。ウルフラムはNKSにおいて、TMを抽象的な数学道具としてではなく、物理的な動的システムとして捉え直し、その「最小構成」における万能性を追求した7。

最小の万能チューリング・マシンの探索

1956年にクロード・シャノンが提起した「最小の万能チューリング・マシン」の探索は、計算機科学における長年の課題であった7。通常、万能性を達成するには複雑な状態遷移図が必要と考えられていたが、ウルフラムは2状態3記号の(2,3)チューリング・マシンが万能である可能性を予測した7。2007年、アレックス・スミスによってこのマシンの万能性が証明され、そのルールセットはわずか6本の命令（状態と記号の組み合わせ）で構成されていることが確認された7。

状態-記号ペア (m, n) 物理的複雑度 (mn) 備考
(15, 2\) 30 ロゴジンによる標準的万能マシン 8
(4, 6\) 24 ロゴジンによる22命令の効率的マシン 10
(2, 3\) 6 スミスによる証明済みの最小万能マシン 7
(2, 4\) 8 ウッズ・ニアリーによる効率的な万能マシン 11

弱い万能性と情報の符号化

(2,3)マシンの証明において議論の的となったのは、初期条件の定義である。標準的な万能チューリング・マシンは、有限の入力以外はすべて空白のテープから開始しなければならないが、スミスが証明した(2,3)マシンは、テープの両端に特定の繰り返しパターンが存在することを許容する「弱い万能性（Weak Universality）」に基づいている7。批判者は、初期条件に複雑性を押し込めていると指摘するが、計算的等価性原理の立場からは、この初期条件の構成プロセス自体が万能計算を含まない限り、システムそのものの計算能力が本質的であるとみなされる2。

このような極小のシステムが万能性を持ち得るという事実は、計算能力が特定の高度な設計によってもたらされるのではなく、単純な相互作用の連鎖の中に「遍在」していることを示している。これは、分子レベルの物理現象が、それ自体で高度な計算を実行している可能性を示唆するものである7。

置換系と幾何学的フラクタル：規則の独立性と干渉の効果

置換系（Substitution Systems）は、構成要素をルールに従って別の要素の集合へと置き換えていくシステムであり、フラクタル幾何学の基礎を成す12。この系の挙動は、置換操作が各要素に対して独立に行われるか、あるいは隣接する要素との「干渉」を伴うかによって決定的に分かれる12。

近傍独立な置換系と入れ子構造の必然性

最も単純な形式の置換系（1Dおよび2Dの独立置換系）では、各ステップで一つの要素が固定された複数の要素に置き換わる。このプロセスは「近傍の状態」に依存しないため、生成されるパターンは必然的に高度な規則性を持つ「入れ子（ネスト）構造」となる12。

  • 例：シェルピンスキーのガスケットは、2次元置換系によって生成される典型的な自己相似図形である14。
  • 成長率：これらの系の要素数の増加は線形再帰（フィボナッチ数列など）によって記述でき、その挙動は完全に予測可能である13。

逐次置換系における複雑性の爆発

情報の複雑性が現れるのは、置換のルールに「順序」や「干渉」が導入された場合である。ウルフラムが提唱した「逐次置換系（Sequential Substitution Systems）」は、文字列全体をスキャンし、最初に見つかった特定のパターンのみを置換する17。

調査によれば、この「逐次性」を導入するだけで、挙動はフラクタル的な規則性を脱却し、ランダムな複雑性を示すようになる18。

  • 頻度：ランダムに選択されたルールのうち、約10,000個に1個の割合で、統計的にランダムで予測不可能なパターンを生成するものが存在する19。
  • 意義：これは、情報の「更新順序」がシステム全体の振る舞いに決定的な影響を与えることを示しており、単純な文字列操作であっても、適切な競合状態が生まれれば、セルオートマトンと同等の複雑な計算能力を持つことを証明している17。

タグ系：数論的直感と計算的万能性の統合

タグ系（Tag Systems）は、エミール・ポストによって1943年に発表された、文字列の先頭を削除し、その内容に応じて末尾に文字を追加する極めて簡潔なシステムである20。このモデルは、文字列の変形という直感的な形式を持ちながら、計算理論における深遠な問題、特にコラッツ予想との関連性で知られている21。

2-タグ系の構造と万能性

タグ系のルールは、削除数（）とアルファベットおよび生成規則の組 で定義される。削除数が2である「2-タグ系」は、歴史的に「複雑な挙動は生まれない」と考えられていた時期があったが、ポスト自身がその予測不可能性に直面し、問題の解決を断念した経緯がある20。

  • 万能性の証明：1960年代、ミンスキーは2-タグ系がチューリング・マシンをシミュレートできることを示し、その万能性を立証した21。
  • 効率性：近年の研究（ウッズ、ニアリーら）によれば、2-タグ系はチューリング・マシンの計算を多項式時間で効率的にシミュレートできることが判明しており、これは「小さな万能マシン」の多くが、見かけによらず強力な計算資源であることを意味している23。

コラッツ予想のタグ系による表現

タグ系の複雑性を象徴するのは、数論における難問「問題」のシミュレーションである。De Mol（2008）らによって示された2-タグ系は、コラッツの反復操作を文字列の長さに変換して実行する21。

2-タグ系の生成規則 数論的な意味
の値を のプロセスへ導くためのフラグ21。
の操作を文字列の削除として表現21。
値の増幅を文字列の追加として表現21。

この系において、初期文字列 'aaa' (n=3) から開始すると、文字列は予測不可能な拡大と収束を繰り返し、最終的に停止（値が1に到達）する。この振る舞いは、タグ系という単純な形式が、人類がいまだ解明できていない高度な数学的真理をその内に秘めていることを示している21。

レジスタマシンとFRACTRAN：算術的最小主義の極致

レジスタマシン（Register Machines）は、現代のコンピュータの抽象的なモデルであり、少数のレジスタに格納された整数を操作する25。このシステムは「加算」「条件付き減算（0でなければ減算してジャンプ）」という二つの基本命令のみで構成されるが、そのシンプルさにもかかわらず、複雑性の発現という点では他の系と遜色ない。

2レジスタによる万能性の実現

マービン・ミンスキーは、わずか2つのレジスタを持つマシンが万能（チューリング完全）であることを証明した26。この証明の核心は、複数の仮想的なレジスタの状態を、単一の整数 の指数として符号化し、素因数分解の一意性を利用して操作するというエレガントな手法にある28。

  • 命令の代替：加算命令は特定の素数での乗算に、減算命令は除算に対応する26。
  • 結論：これにより、物理的なレジスタの数は最小限（2つ）であっても、計算の内容には限界が存在しないことが示された28。

FRACTRAN：分数の乗算のみによるプログラム

ジョン・コンウェイが発明したFRACTRANは、レジスタマシンの概念を極限まで抽象化したシステムである。FRACTRANのプログラムは単なる「分数のリスト」であり、現在の数 に対して、リストの先頭から順に掛けてみて、最初に「結果が整数になる」分数を選んで を更新する29。

コンウェイの「PRIMEGAME」は、14個の分数のリストだけで素数の列を生成する29。

この数列の中で の累乗（）が現れる際、その指数は必ず素数となる29。FRACTRANは、プログラミング言語の構文が算術の基本演算（乗除算）にまで削ぎ落とされたとしても、そこには高度なアルゴリズムを記述する能力が完全に残っていることを証明している31。

計算的等価性原理（PCE）：普遍的な計算能力の法則

これまで見てきたように、CA、MA、TM、タグ系、レジスタマシン、置換系といった、形式も操作対象も異なるシステムが、すべて「単純な規則から複雑な挙動」を生み出し、さらには「万能計算能力」を獲得している。ウルフラムはこの広範な経験的事実に基づき、「計算的等価性原理（Principle of Computational Equivalence, PCE）」を提唱した33。

原理の中核的な主張

計算的等価性原理は、計算の宇宙に関する三つの本質的な洞察を提示している。

  1. あらゆるプロセスは計算である： 自然界の物理現象、人間の思考、そして単純なコンピュータプログラムはすべて、入力を出力に変換する計算プロセスとして等しく定義できる33。
  2. 洗練度の頭打ち： システムの規則が極端に単純でない限り、それらはすべて「同等の洗練度」を持つ計算を実行している。洗練度には連続的な階層があるのではなく、ある一定の閾値を超えると、即座に「最大レベル（万能性）」に到達する33。
  3. 万能性の遍在： 以前は特殊で高度な設計の産物と考えられていた万能性は、実際には計算の宇宙のいたるところに存在する普遍的な属性である33。

伝統的科学への挑戦

PCEは、従来の科学が依拠してきた「予測可能性」の限界を明らかにしている。もしシステムが万能な計算能力を持つならば、その将来の状態を予測することは、システム自体が行う計算量と同等の努力を必要とする35。これが「計算的不可約性（Computational Irreducibility）」である37。

科学的アプローチ 特徴 限界
伝統的数学・物理学 方程式による「近道（Shortcut）」の追求35。 線形・可約な系にのみ適用可能19。
NKS・計算的科学 ステップごとのシミュレーションと観察2。 不可約な挙動の予測には、計算の実行が必須37。

この原理が示唆するのは、我々観測者（人間）の計算能力が、観測対象（自然界のプロセス）の計算能力を「超えることはできない」という事実である35。したがって、複雑な現象の背後に単純な規則を発見できたとしても、その結果を「予見」できるとは限らない。

議論：普遍的現象としての複雑性と計算

本調査によって、単純な規則から複雑な振る舞いが出てくる現象は、計算の形式（データ構造や更新方法）に依存しない「普遍的な現象」であることが明らかになった。

なぜ複雑性が生まれるのか

複雑性が現れる共通の鍵は、規則の「競合」と「情報のフィードバック」にある。

  • モバイル・オートマトンでは、活性セルの移動と色の変更が空間的な履歴を形成し、それが将来の活性セルの挙動を制限する4。
  • タグ系では、先頭の削除と末尾の追加という時間のズレを伴う操作が、情報の不規則な干渉を生む20。
  • レジスタマシンでは、指数の増減という算術的な関係が、高度な論理演算を素因数分解の構造に埋め込んでいる26。

これらはすべて、システムが「自分自身の過去の状態を参照し、それを将来の決定に組み込む」という再帰的な構造を持っていることに起因する2。

普遍性への批判と反論

学術界、特に理論計算機科学の立場からは、PCEが計算量の細かな区別（P vs NPなど）を無視しているという批判がある2。スコット・アーロンソンらは、万能性があるからといって、すべてのシステムが「実質的に等価」であるとみなすのは飛躍であると指摘している38。

しかし、ウルフラムの視点は、実用的な計算の効率性ではなく、システムの「質的な挙動のクラス」に向けられている。(2,3)チューリング・マシンの万能性が証明された事実は、設計者の意図がなくとも、自然発生的なルールの中に最高度の計算能力が宿り得ることを実証しており、この点においてPCEの予見は極めて強力である7。

結論：単純性の向こう側にある普遍的知性

本報告書で網羅的に調査したすべての計算系は、形式の壁を超えて、単純な規則が豊かな複雑性を生成することを示している。モバイル・オートマトンが示す逐次的な複雑性、チューリング・マシンが示す極小の万能性、タグ系やレジスタマシンが示す数論的な奥深さは、すべて計算の宇宙における「同一の真理」の異なる側面を映し出している。

複雑性は、特定の高度な仕組み（並列処理や大規模なメモリ）の産物ではなく、計算という操作の根源に備わっている。そして、計算的等価性原理が主張するように、我々の宇宙に存在するほとんどの非自明なシステムは、互いに等価な計算洗練度を共有している。この事実は、物理学、生物学、さらには人工知能の研究において、複雑な現象を「設計」しようとする努力よりも、計算の宇宙に既に存在する「単純で強力なルール」を「探索」し「活用」するアプローチの重要性を浮き彫りにしている。

最終的に、複雑性が普遍的であるという結論は、我々自身が複雑な存在である理由もまた、宇宙の基本法則が単純であることの論理的な帰結であることを示唆している。計算の宇宙は、少数の文字と数行のルールで綴られた、無限の物語を孕んでいるのである。

引用文献

  1. A New Kind of Science \- Wolfram Media, 5月 15, 2026にアクセス、 https://www.wolfram-media.com/products/nks/
  2. A New Kind of Science \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/A\_New\_Kind\_of\_Science
  3. New Kind of Science \-- from Wolfram MathWorld, 5月 15, 2026にアクセス、 https://mathworld.wolfram.com/NewKindofScience.html
  4. Mobile Automata: A New Kind of Science | Online by Stephen ..., 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p71--mobile-automata/
  5. Mobile Automaton \-- from Wolfram MathWorld, 5月 15, 2026にアクセス、 https://mathworld.wolfram.com/MobileAutomaton.html
  6. Mobile Automata, 5月 15, 2026にアクセス、 https://files.wolframcdn.com/pub/www.wolframscience.com/nks/nks-ch3-sec3.pdf
  7. Wolfram's 2-state 3-symbol Turing machine \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/Wolfram%27s\_2-state\_3-symbol\_Turing\_machine
  8. Universal Turing machine \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/Universal\_Turing\_machine
  9. What's the simplest noncontroversial 2-state universal Turing machine?, 5月 15, 2026にアクセス、 https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine
  10. Small universal Turing machines, 5月 15, 2026にアクセス、 https://www.mobt3ath.com/uplode/book/book-94720.pdf
  11. Small universal Turing machines, 5月 15, 2026にアクセス、 https://justine.lol/sectorlisp2/tneary\_Thesis.pdf
  12. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 190\], 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p190--substitution-systems-and-fractals/
  13. Substitution Systems: A New Kind of Science | Online by Stephen Wolfram \[Page 82\], 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p82--substitution-systems/
  14. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 187\], 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p187--substitution-systems-and-fractals/
  15. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 191\], 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p191--substitution-systems-and-fractals/
  16. Substitution Systems and Fractals: A New Kind of Science | Online by Stephen Wolfram \[Page 188\], 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p188--substitution-systems-and-fractals/
  17. String Substitution Systems: Wolfram Physics Project Technical Background, 5月 15, 2026にアクセス、 https://www.wolframphysics.org/technical-introduction/the-updating-process-for-string-substitution-systems/string-substitution-systems/
  18. Sequential Substitution System \-- from Wolfram MathWorld, 5月 15, 2026にアクセス、 https://mathworld.wolfram.com/SequentialSubstitutionSystem.html
  19. Sequential Substitution Systems: A New Kind of Science | Online by ..., 5月 15, 2026にアクセス、 https://www.wolframscience.com/nks/p90--sequential-substitution-systems/
  20. Tag System \-- from Wolfram MathWorld, 5月 15, 2026にアクセス、 https://mathworld.wolfram.com/TagSystem.html
  21. Tag system \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/Tag\_system
  22. \[PDF\] Tag systems and Collatz-like functions \- Semantic Scholar, 5月 15, 2026にアクセス、 https://www.semanticscholar.org/paper/Tag-systems-and-Collatz-like-functions-Mol/931eeecbcb5a55f31e9aec6c6a628fd348b435c4
  23. On the time complexity of 2-tag systems and small universal Turing machines, 5月 15, 2026にアクセス、 https://dna.hamilton.ie/assets/dw/WoodsNeary-FOCS06.pdf
  24. \[cs/0612089\] On the time complexity of 2-tag systems and small universal Turing machines, 5月 15, 2026にアクセス、 https://arxiv.org/abs/cs/0612089
  25. Register machine \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/Register\_machine
  26. Minsky machine \- Esolang, 5月 15, 2026にアクセス、 https://esolangs.org/wiki/Minsky\_machine
  27. Counter machine \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/Counter\_machine
  28. Computation: Finite and Infinite Machines \- MIT CBA, 5月 15, 2026にアクセス、 http://www.cba.mit.edu/events/03.11.ASE/docs/Minsky.pdf
  29. FRACTRAN \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/FRACTRAN
  30. Fractran A Simple Programming Language \- HKopp \- koppian adventures, 5月 15, 2026にアクセス、 https://hkopp.github.io/2018/03/fractran-a-simple-programming-language
  31. Complexity of Fractran and Productivity \- Jörg Endrullis, 5月 15, 2026にアクセス、 https://joerg.endrullis.de/assets/papers/complexity-productivity-2009.pdf
  32. FRACTRAN: A SIMPLE UNIVERSAL PROGRAMMING LANGUAGE FOR ARITHMETIC \- UNC Computer Science, 5月 15, 2026にアクセス、 https://www.cs.unc.edu/\~stotts/COMP210-s23/madMath/Conway87.pdf
  33. The Principle of Computational Equivalence, 5月 15, 2026にアクセス、 https://files.wolframcdn.com/pub/www.wolframscience.com/nks/nks-ch12.pdf
  34. Principle of Computational Equivalence \-- from Wolfram MathWorld, 5月 15, 2026にアクセス、 https://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html
  35. Computation and the Future of the Human Condition \- Stephen Wolfram, 5月 15, 2026にアクセス、 https://www.stephenwolfram.com/publications/computation-future-human-condition/
  36. 7.3 Computational Capabilities of Our Models \- The Wolfram Physics Project, 5月 15, 2026にアクセス、 https://www.wolframphysics.org/technical-introduction/equivalence-and-computation-in-our-models/computational-capabilities-of-our-models/
  37. Computational irreducibility \- Wikipedia, 5月 15, 2026にアクセス、 https://en.wikipedia.org/wiki/Computational\_irreducibility
  38. Blog Archive » The Aaronson $25.00 Prize \- Shtetl-Optimized, 5月 15, 2026にアクセス、 https://scottaaronson.blog/?p=284