チューリングマシンの拡大と複雑性

全体概要

本セミナー「チューリングマシンの拡大と複雑性」は、計算科学における最も根本的な問いの一つ——「計算の難しさとは何か、そしてその限界はどこにあるのか」——を、チューリングマシンという計算モデルの「拡大」という視点から体系的に探求するものです [p.1], [p.2]。

議論の起点は「有限の限界」という哲学的・数理的な問いに置かれています。私たちが「具体的に扱える有限なもの」とは何かを問うと、自然数のレベルから「帰納的可算」、そして「多項式時間で計算可能なもの」へと、有限の概念が段階的に絞り込まれてきた歴史が浮かび上がります [p.18]〜[p.26]。複雑性理論とは、この「有限の限界」を精密に分類・記述しようとする理論であると言えます。

技術的な核心は、チューリングマシンに「どのような拡張を施すか」によって、受理される問題の複雑性クラスが劇的に変化するという事実にあります。決定性チューリングマシン（P）、非決定性チューリングマシン（NP）、確率性チューリングマシン（BPP）、そして量子チューリングマシン（BQP）という四種の計算モデルが、それぞれ異なる複雑性クラスを定義します [p.131]〜[p.141]。この対応関係を精緻に描き出すことが、本セミナーの中心的な技術的貢献です。

そして終盤では、1990年代以降に登場した「Interactive Proof」という証明概念の根本的転換に焦点を当てます [p.164]〜[p.169]。「証明者（Prover）」と「検証者（Verifier）」を分離し、両者の対話として証明を捉え直すこのアプローチは、NP→NEXP→NEEXPという複雑性クラスの階層的拡張を可能にし、ついに2020年の「MIP*=RE定理」という革命的な成果に到達します [p.207]〜[p.209]。この定理は、「多項式時間」という制約に縛られていた複雑性理論を、「帰納的可算（RE）」という計算可能性理論の中核概念と結びつけ、有限と無限の深い関係を照射します [p.213]〜[p.214]。本セミナーは、この循環する認識の深化こそが新しい理解への出発点であるという著者の確信のもとに構成されています [p.3]。

講義のロードマップ

■ Part I: 複雑性理論の基本概念

• この部の核心:

複雑性理論がなぜ「有限の限界」から出発するのかを哲学的・数理的に動機づけた上で、「多項式時間」「時間計算量・空間計算量」「PとNP」という基礎概念を、チューリングマシンによる定義と結びつけながら体系的に導入します。有限の限界の三段階（可算無限ω、帰納的可算、多項式）という精緻な整理が、この部の最大の貢献です [p.21]〜[p.26]。

• 論理展開:
• ゼノンの逆理からカントールの集合論まで、「無限と連続」をめぐる哲学・数学史を俯瞰し、複雑性理論が「有限の捉え方」を核心に置く理由を示します [p.14]〜[p.16]。
• 有限の「限界」を、①自然数の上限ω（可算無限）、②帰納的可算（チューリングマシンで計算可能なもの）、③多項式時間（人間が現実的に扱えるもの）の三段階で精緻化します [p.21]〜[p.26]。
• 時間複雑性（P, EXP, 2-EXP）と空間複雑性（PSPACE, EXPSPACE）の階層を `DTIME(f(x))` / `DSPACE(f(x))` として定義し、両者が交互に入れ子になる構造を図示します [p.41]〜[p.43]。
• NPを「解の検証が多項式時間で可能なクラス」として直観的に導入し、「証明は難しいが検証はやさしい」という本質を抽出した上で、「非決定性チューリングマシンで多項式時間で受理されるクラス（NTIME(p(n))）」という第二の定義を提示します [p.47]〜[p.54]。

■ Part II: チューリングマシンと複雑性

• この部の核心:

チューリングマシンの命令体系（遷移関数δ: Q×Σ→Σ×D×Q）を厳密に定式化した上で、「命令セットを複数持つ」「確率的な分岐を持つ」「量子的な重ね合わせを持つ」という三種の拡張が、それぞれ NP、BPP、BQP という質的に異なる複雑性クラスを生み出すことを、チューリングマシンの「木構造」という統一的なイメージで描き出します [p.93]〜[p.141]。

• 論理展開:
• チューリングマシンの一命令を `A 0→1:R A`（現在状態・読み文字→書き文字:移動方向・次状態）の形式で定義し、命令セット（遷移集合）δと配置状態（Configuration）の概念を導入します [p.74]〜[p.87]。
• 決定性チューリングマシン（一本道の配置状態列）と非決定性チューリングマシン（分岐する木構造）を対比し、非決定性マシンの「受理＝一つでもacceptパスが存在すること」という定義を明確にします [p.93]〜[p.96]。また、非決定性マシンを三テープ（入力・Path・出力）の決定性マシンでシミュレートできることを示し、P⊆NPを導きます [p.108]〜[p.112]。
• 確率性チューリングマシンを「枝分かれ確率が異なるBPPの木構造」として、非決定性マシンと対比します。BPPクラスは「x∈Lならacceptの確率が2/3以上」という確率的条件で定義されます [p.123]〜[p.128]。
• 量子チューリングマシンが定義するBQPクラスをBPPと対比し、古典複雑性（P, NP, BPP, MA）と量子複雑性（BQP, QMA, QIP）の対応構造を整理します [p.141]〜[p.159]。

■ Part III: 複雑性理論の転換

• この部の核心:

「証明者と検証者の対話（Interactive Proof）」という証明概念の転換が、複雑性理論にいかなる革命をもたらしたかを追います。IP=PSPACE（1990年）、MIP=NEXP（1991年）という古典的成果から出発し、量子エンタングルメントを持つMIP*がついにRE（帰納的可算）と等しいことを示す2020年のMIP*=RE定理に至る50年の歴史と、その認識論的含意を探ります [p.164]〜[p.187]〜[p.207]〜[p.213]。

• 論理展開:
• 古典的証明（命題πの演繹列）がNP完全問題であることを示した上で、InteractiveProofは「証明者は常に正しいとは限らない」「検証者は確率的に動作する」という二つの想定の転換によって証明概念を拡張することを解説します [p.170]〜[p.172]。PCP定理（NP⊆PCP[log n, 1]）は、log nビットの乱数だけで証明の数ビットをサンプルするだけでNP証明を検証できるという驚異的な内容です [p.189]〜[p.191]。
• グラフの三色塗り分け問題を例に、頂点数n/2ⁿ/2^(2ⁿ)のグラフへと問題を拡張することで、証明の複雑性NP/NEXP/NEEXPと検証の複雑性P/EXP/EEXPが対になって出現することを具体的に示します [p.197]〜[p.200]。
• NatarajanとWrightによるNEEXP⊆MIP*（2019年）の成果を基盤に、JNVWYはIntrospectionとゲームのcompression手法を繰り返し適用することで、NEEEXP, NEEEEXP, ... という無限の階層がすべてMIP*に含まれ、その極限がRE⊆MIP*となることを証明します [p.206]〜[p.209]。
• MIP*=REは、「多項式時間」の制約を超えることで、有限の複雑性理論を「帰納的可算（RE）」という無限を扱う計算可能性理論と接続します。これはカントールの超限順序数ε₀（=ω^ω^ω^...）の構成と深い類比関係にあり、ゲーデルの不完全性定理とゲンツェンの無矛盾性証明を結ぶ「有限の中の無限、無限の中の有限」という主題に収斂します [p.213]〜[p.223]。