講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナー「チューリングマシンの拡大と複雑性」は、計算科学における最も根本的な問いの一つ「計算の難しさとは何か、そしてその限界はどこにあるのか」を、チューリングマシンという計算モデルの「拡大」という視点から体系的に探求するものです [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]。
■ Part II: チューリングマシンと複雑性
チューリングマシンの命令体系（遷移関数δ: Q×Σ→Σ×D×Q）を厳密に定式化した上で、「命令セットを複数持つ」「確率的な分岐を持つ」「量子的な重ね合わせを持つ」という三種の拡張が、それぞれ NP、BPP、BQP という質的に異なる複雑性クラスを生み出すことを、チューリングマシンの「木構造」という統一的なイメージで描き出します [p.93-p.141]。
■ Part III: 複雑性理論の転換
「証明者と検証者の対話（Interactive Proof）」という証明概念の転換が、複雑性理論にいかなる革命をもたらしたかを追います。IP=PSPACE（1990年）、MIP=NEXP（1991年）という古典的成果から出発し、量子エンタングルメントを持つMIP*がついにRE（帰納的可算）と等しいことを示す2020年のMIP*=RE定理に至る50年の歴史と、その認識論的含意を探ります [p.164, p.187, p.207-p.213]。
ページのナビゲート