1. テーマの全体像と技術的背景

計算科学と複雑性は、現代の科学技術において重要な役割を果たす概念です。その起源は、関連する学術分野の歴史的発展に深く深く根ざしています。本ジャンルでは、計算科学と複雑性の基礎理論から応用、そして関連する学際的分野への展開について議論します。ここでは、計算科学と複雑性の主要な概念、歴史的発展、およびその現代的意義を探求します。

MaruLaboが「計算科学と複雑性」という大局テーマで探求しているのは、「計算の限界はどこにあるのか」「何が計算可能で、何が計算不可能なのか」「計算の難しさとは何か」という、コンピュータ・サイエンスの最も根源的な問いに対する多角的かつ現代的なアプローチです。これは単なる技術的な課題に留まらず、人間が認識し得る「有限」と、その外側に広がる「無限」との関係性を、数理的・哲学的に深く考察する壮大な物語でもあります。

この探求の出発点は、アラン・チューリングが提唱した抽象的な計算モデル「チューリングマシン」にあります。このシンプルなモデルは、あらゆる計算プロセスを記述できる普遍性を持つ一方で、その能力と限界を精密に分析する基盤となりました。MaruLaboでは、このチューリングマシンに「どのような拡張を施すか」という視点から、決定性（P）、非決定性（NP）、確率性（BPP）、量子（BQP）といった、異なる能力を持つ計算モデルが生み出す複雑性クラスを体系的に解説しています [20210226TuringComplex]。これにより、我々が「現実的に計算可能」と考える多項式時間計算の範囲を明確にし、その壁がいかに深く、しかし時に乗り越えられ得るものであるかを浮き彫りにします。

特に重要な転換点は、1990年代以降に発展した「Interactive Proof（対話型証明）」の概念です。これは、従来の静的な証明概念を覆し、証明者（Prover）と検証者（Verifier）との「対話」を通じて命題の正しさを確率的に検証するという、革新的なアプローチです [20210226TuringComplex]。この対話型証明は、計算複雑性理論の枠組みを劇的に拡張し、IP=PSPACEやMIP=NEXPといった画期的な成果を生み出しました。

さらに現代においては、このInteractive Proofが、量子情報理論の文脈で生まれた「nonlocalゲーム」と構造的に同一であることが発見され、計算科学と量子物理学という異なる分野の知見が融合する様が示されています [20210110inter-comp]。この融合の極致が、2020年に証明された「MIP*=RE定理」です。これは、量子エンタングルメントを持つ証明者との対話を用いることで、多項式時間の制約を遥かに超える「帰納的可算（RE）」な問題まで検証可能であることを示し、有限の計算複雑性理論と、チューリングマシンが扱う無限を内包する計算可能性理論とを、深く結びつける革命的な成果となりました [20210226TuringComplex]。この定理は、ゲーデルの不完全性定理やカントールの無限の階層といった、20世紀数学の主要なテーマとも共鳴し、「有限の中の無限、無限の中の有限」という哲学的深淵を再認識させます。

同時に、MaruLaboは「証明」そのものの本質にも深く切り込んでいます。対話型証明支援システムCoqを用いたセミナーでは、「正しい命題であること」と「証明を持つこと」の厳密な区別が、直観主義論理の視点から鮮やかに解説されます [20230611HelloCoq]。ゲーデルの不完全性定理が示唆する「正しいが証明を持たない命題」の存在は、まさにこの二つの基準の乖離を物語っており、機械と人間が協働して厳密な証明を構築するプロセスを通して、数学的真理への到達がいかに繊細で複雑な行為であるかを浮き彫りにします。

また、AIとの「対話」を通じて、その知識の深さや限界（「知っていないこと」）をどのように見極めるかという実践的な問いも探求されています [20200930InteractiveP]。これは、計算の能力と限界が、具体的なAIの振る舞いとしてどのように現れるか、そして我々人間がそれをいかに認識すべきかという、現代社会におけるAIリテラシーの根幹に関わる問題提起です。

このようにMaruLaboの「計算科学と複雑性」は、チューリングマシンの原理から、量子情報科学との融合、証明論の哲学的基礎、そしてAIとのインタラクションまで、計算という行為が持つ無限の可能性と、それに伴う深遠な限界を、数理的・技術的、そして認識論的な多角的な視点から解き明かそうとする、壮大な知の探求なのです。

2. このジャンルの関連セミナーのリスト

  • 計算理論入門 ー 「やさしい計算」と「むずかしい計算」[20181015]
  • 2のn乗の話（チューリングマシンの話） [20200630]
  • チューリングマシンを学ぼう！ [20210108x]
  • 機械と人間のインタラクション [20200930]
  • Interactive Proofと複雑性 [20210110x]
  • 確率と証明 [20201203x]
  • チューリングマシンの拡大と複雑性 [20210226]
  • 計算複雑性理論入門 [20240908x]
  • コンピュータ・サイエンスの現在 — MIP*=RE定理とは何か？– [20201127-1x]
  • MIP*=RE 入門– Interactive Proofとnonlocal ゲーム — [20201225-1]
  • 計算科学とエントロピー — コロモゴロフ複雑性とアルゴリズム論的情報理論 [20210903x]

3. 関連セミナーの概要

本ジャンルでは、チューリングマシンを基盤に計算可能性と複雑性の基礎概念を確立し、その限界と拡張を探求します。計算複雑性クラスの階層的構造、Interactive Proofsによる証明概念の革新、そしてMIP*=RE定理を通じて、計算可能性理論との接続を深めます。また、コロモゴロフ複雑性や形式的検証、AIの推論能力評価といった多角的なアプローチにより、複雑性の本質に迫ります。

  • 計算理論入門 ー 「やさしい計算」と「むずかしい計算」[20181015]

講義は大きく二つの軸で構成されています。第一の軸は「算数・数学の計算アルゴリズム」を題材にした、計算の手順（アルゴリズム）とは何かの具体的探求です。掛け算・割り算・分数演算のステップを丁寧に追うことで、コンピュータが処理する「手続き」の本質を直感的に掴ませます [p.9〜p.19、p.22〜p.31]。

第二の軸、そしてこの講義の真髄は「計算可能性と計算複雑性の理論史」です。1930年代にゲーデルの不完全性定理 [p.84, p.85]、チューリングの停止問題 [p.86]、そしてチャーチ＝チューリングのテーゼ [p.92] が相次いで登場し、「計算できないことが証明できること」が明らかになった知的革命を丁寧に辿ります。チューリングマシンの具体的な動作原理 [p.97〜p.110] を実例で示した後、Busy Beaverという「計算可能性の極北」 [p.130〜p.142] に至ります。

  • 2のn乗の話（チューリングマシンの話） [20200630]:

「2ⁿ」を起点に、二進表現や関数空間といった計算・情報科学の基礎概念を解説し、計算対象や状態空間の指数的増加という複雑性の源泉を提示します。チューリング・マシンによる計算可能性の厳密な定義を通じて、現代計算理論の基盤を確立します。停止問題やBusy Beaver問題を通じて計算不能性や実用的な計算限界を分析し、P/EXP等の複雑性クラスへの導入を行います [20200630]。

  • チューリングマシンを学ぼう！ [20210108x]:

「チューリング・マシン」は、今から80年以上前の1936年に、当時24歳だったアラン・チューリングが計算のモデルとして提案した、とてもシンプルな構造を持つ「マシン」です。ある意味、究極のRISCマシンです。

もちろん、その時代には、現在のようなコンピューターは、影も形もありませんでした。それにもかかわらず、チューリング・マシンは、コンピュータの働きの最も重要なモデルであり続けています。それは、驚くべきことです。

セミナーの前半で、次のような内容でチューリング・マシンの基本を学びます。
　●　テープとヘッッド
　●　状態と状態の遷移
　●　チューリングマシンの命令とその実行
　●　簡単なチューリングマシンのプログラム

  • 機械と人間のインタラクション [20200930]:

大規模言語モデル(GPT-3)の知識表現能力と推論限界を、人間との対話実例を用いて客観的に検証します。量子計算とNP完全問題といった複雑な概念に対するAIの応答を分析し、表層的な正答と概念の深い理解との乖離を特定します。「問いの反復と変化」という対話戦略が、AIの「知らないこと」を可視化する有効なアプローチであることを実証し、AIの信頼性と限界に関する洞察を提供します [20200930]。

CHSHゲームやMagic Squareゲーム等をnonlocal gameと呼ぶ。nonlocal というのは、これらのゲームでは、非局所的なエンタングルメントの性質を利用して、古典的な相関を超える高い勝率を実現しているからである。
nonlocalゲームは、量子論が古典論とは異なるものであることを、理論的・実験的に明らかにしようとする取り組みの中で生まれたものであるが、それは、Interactive
Proofと、同じ構造をしていた。
CHSHゲームは 1960年代に生まれ、Interactive Proofは1990年代に発展するのだが、両者が同一の構造を持つという認識は、21世紀に入ってから生まれたものだ。

通常のチューリングマシン(決定性チューリングマシン)は、一つの遷移表(命令セット)δを持つ。この時、マシンとテープの状態を一つのノードとみなしてマシンの実行を、ノードからノードへの遷移のグラフとして考えると、このグラフは、枝分かれのない、すべてのノードが一直線上に並んだものになる。

二つの遷移表(命令セット)δ0とδ1を持つチューリングマシンを考える。あるノード上で、δ0とδ1のどちらの命令セットを選ぶかは決まっていない。この時、このマシンで可能な実行のグラフは、木構造になる。こうしたマシンを非決定性チューリングマシンという。実は、遷移表は、二つ以上あってもいい。

  • チューリングマシンの拡大と複雑性 [20210226]:

チューリングマシンの拡張（決定性、非決定性、確率性、量子）を通じ、P, NP, BPP, BQPといった主要な複雑性クラスの定義と計算能力の限界を体系的に分析します。Interactive Proofという証明概念の導入により複雑性理論を拡張し、IP=PSPACE, MIP=NEXPなどの階層的関係性を精密に記述します。MIP*=RE定理を解説し、量子エンタングルメントを用いた分散型証明システムが帰納的可算集合（RE）全体を受理可能であることを示します [20210226]。

  • コンピュータ・サイエンスの現在 — MIP*=RE定理とは何か？– [20201127-1x]:

コンピュータ・サイエンスは、今、大きな転換点を迎えています。
その変化は、一言で言えば、コンピュータ・サイエンスは、単に「コンピュータ＝計算機についての理論」ではなく、情報理論や物理学や数学などの数学的手法を用いる幅広い数理科学の中心的な理論として登場しつつあると言うことです。

こうしたコンピュータ・サイエンスの進化を象徴的に示すのが、2020年の1月に証明された “MIP* = RE定理”（「ミップ・スター・イコール・アールイー定理」と読みます）です。この定理は、数十年間未解決であった純粋数学の問題を解決し、また、同じく未解決であった量子力学の基本的な問題を解決しました。こうした問題の解決が、数学者や理論物理学者によってではなく、「コンピュータ・サイエンティスト」によって行われたことは、ある意味驚くべきことです。

  • MIP*=RE 入門– Interactive Proofとnonlocal ゲーム — [20201225-1]:

計算科学の根幹をなす抽象計算機械（チューリングマシン）の原理を解説し、決定性（DTM）と非決定性（NTM）の計算モデルの差異を明確にします。テープとヘッド、状態遷移に基づくチューリングマシンの動作を形式的にモデル化し、NTMにおける複数の遷移表と「木構造」としての実行パスにより、NPクラスを数学的に厳密に定義します。これにより、アルゴリズムの計算限界を理論的に提示し、暗号理論や最適化問題の基盤を提供します [20201225-1]。

  • 計算科学とエントロピー — コロモゴロフ複雑性とアルゴリズム論的情報理論 [20210903x]:

「ランダムさ」という直観的概念に対し、計算理論に基づいた厳密な複雑性定義の枠組みを探求します。コロモゴロフ複雑性をオブジェクトの最短記述長として導入し、その不変性、計算不能性、およびチャイティンの不完全性定理を提示します。アルゴリズム論的情報量を定義し、シャノンエントロピーとの関係性を確立します。また、アルゴリズム論的熱力学を構築し、複雑性と情報・計算・熱力学の統合的視点を提供します [20210903x]。