講演資料

講義資料スライドの表紙です。スライド画像、または下の要約文中の青いページ番号リンクをクリックすると、別のタブで無駄なノイズのない、純粋なPDFビューア画面が起動し、指定されたページへ直接ジャンプして快適に閲覧できます。

全体概要

本セミナーは、「機械は考えることができるか？」というアラン・チューリングの古典的問いを出発点に据え、人工知能研究の未来を「複雑性理論」という数学的・物理的認識可能性の理論を中軸として考察した意欲的な論考です。[p.2], [p.5]

筆者は「計算主義」の立場に立ち、人間の知能の本質を「計算」として抽象することで、機械と人間を等値しうると主張します。この等値のもとでは「人間にできることは機械にもできる」という強力な主張が成立し、人工知能技術の可能性を考える最も強いメッセージとなります。[p.18], [p.19]

しかし、計算主義の立場からこの問いに誠実に向き合うとき、「何がどこまで計算できるのか」という限界の問題が浮上します。本セミナーはその限界を三世代にわたる「複雑性理論」の発展として整理します。第一世代は1950年代の「計算可能性理論」（チャーチ＝チューリングのテーゼ）、第二世代は1970年代の「計算複雑性理論」（P=NP?問題）、そして第三世代は1980年代以降の「量子複雑性理論」（BQP、ショアのアルゴリズム）です。[p.6], [p.7]

特筆すべきは、第三世代において「情報過程＝物理過程」という認識が確立し、複雑性理論が純粋数学の世界から物理学の中核へと移行した点です。ブラックホールのエントロピー、エンタングルメントのエントロピー、AdS/CFT対応、ER=EPR仮説といった現代物理学の最前線が、量子情報理論と複雑性理論を軸に収斂していく様子が生き生きと描かれます。[p.7], [p.303]

さらに本セミナーは、深層学習（ディープラーニング）の能力と限界をChomsky Hierarchyという形式言語の枠組みで分析し、言語能力・数学的認識能力という人間固有の高次認識能力の機械的実現という課題を正面から論じます。最後に、数学の証明をめぐるVoevodskyの仕事を通じて、「人間と機械の共生」という21世紀の知的営為の新しい形が展望されます。我々の認識の「限界」が精緻に境界付けられる一方で、その限界の認識深化こそが世界認識の拡大と一体であるという逆説的で希望に満ちた結論が、本セミナーを貫く哲学的ライトモチーフです。[p.364]

講義のロードマップ

■ Part I: 計算主義とコネクショニズム

  • この部の核心:

人工知能における「計算主義」の立場を明確にし、人間の知能が感覚・運動的能力、言語能力、数学的・科学的認識能力という複数の階層から構成されることを示します。その上で、ディープラーニング（LSTM・RNN）が形式的パターンの認識と生成においてどこまで有能であり、どこに本質的限界があるかを具体的実験と生成例で検証します。[p.15], [p.32]

  • 論理展開:
  • 計算主義の含意：「計算」という抽象のもとで機械と人間は等値され、人間にできることは機械にもできるという方法論的原理が成立する。[p.19]
  • 知能の階層性：感覚・運動的把握→言語能力→文字による知識の集積→数学的・科学的認識という四層構造を提示し、現在のAI技術が攻めあぐねている課題を特定する。[p.35], [p.36]
  • LSTMの実験（Hochreiter 1997）：有限オートマトンの正規文法学習、掛け算学習、時間的順序パターン認識が可能であることを示す。[p.42], [p.44], [p.45]
  • RNNによる生成（Karpathy 2015）：LinuxソースコードやStack Theory教科書を学習させることで、文脈自由文法レベルの構造をRNNが学習・生成できることを示す一方、交換図式（Diagram）の生成は不可能であることも示す。[p.55], [p.57], [p.61]
  • Chomsky Hierarchyとの対応：Deep LearningはType-3（正規文法）からType-1（文脈依存文法＝自然言語）へと能力を拡大しつつあるが、その意義と限界を形式言語理論で位置付ける。[p.91], [p.92]

■ Part II: 計算可能性理論

  • この部の核心:

ヒルベルトの形式化プログラムとゲーデルの不完全性定理から出発し、チューリング・マシン、チャーチのλ計算、ゲーデル＝エルブランの帰納関数論が「同値」であることの認識に至る「知的黄金時代」を描きます。「証明可能＝計算可能」なものには限界があるという第一世代の複雑性理論が確立する過程を辿ります。[p.65], [p.75]

  • 論理展開:
  • ゲーデルの不完全性定理（1930）：初等数論を含む無矛盾な形式体系内では、その体系自身の無矛盾性は証明不可能であり、ヒルベルト・プログラムの実行不可能性を意味する。[p.69], [p.71]
  • チャーチ＝チューリングのテーゼ：「全ての実効的に計算可能な関数は一般帰納的である」という提案が確立し、計算可能性の第一世代が完成する。[p.78]
  • アッカーマン関数：一般帰納関数として定義されながら、少しのパラメータ増加で事実上計算不能になる関数の存在が、限界の具体性を示す。[p.107], [p.108]
  • ゲンツェンの無矛盾性証明（1936）：ε₀までの超限帰納法を用いてペアノ数論の無矛盾性を証明し、「有限の立場」を超えた証明論の豊かさを示す。[p.104]
  • Chomsky HierarchyとMinimalist Program：自然言語の文法がMildly Context-Sensitiveであるという位置付けと、MergeがRecursiveであることの意義を論じる。[p.95], [p.94]

■ Part III: 計算複雑性理論

  • この部の核心:

1950年代にナッシュとゲーデルが手紙の中で予感し、1970年代にCookとLevinが定式化した「P=NP?問題」を中心に、計算の「複雑さ」を階層的に整理する第二世代の複雑性理論を解説します。さらにコルモゴロフ複雑性、チャイティンの不完全性定理、Busy Beaver問題という「我々に手の届かない有限」という衝撃的な発見を紹介します。[p.130], [p.143]

  • 論理展開:
  • ゲーデルの1956年フォン・ノイマン宛書簡・ナッシュの1955年NSA宛書簡：多項式時間と指数関数的時間の計算量の違いという複雑性理論の核心を、二人の天才が独立に予感していた。[p.133], [p.134]
  • P・NP・PSPACE・EXP・BPPクラスの定義：多項式時間決定可能（P）、証明のチェックが多項式時間で可能（NP）、確率的多項式時間（BPP）等の複雑性クラスを厳密に定義する。[p.147], [p.148]
  • チャイティンの不完全性定理：「どのような特定のビット列をとっても、そのコルモゴロフ複雑性がL以上であることを証明できないような数Lが存在する」という驚くべき定理。その壁Lは数キロバイト程度と極めて小さい。[p.162], [p.164]
  • Busy Beaver問題：BB(7910)が通常の集合論の枠内では決定不能であることがYedidia & Aaronson (2016)により証明され、有限だが計算できない数の存在が明確化された。[p.183], [p.184]

■ Part IV: 量子複雑性理論

  • この部の核心:

ファインマンの「量子コンピュータによる自然のシミュレーション」という問題提起（1982）から始まり、ドイッチェのチャーチ＝チューリング＝ドイッチェのテーゼ、バーンスタイン＆ヴァジラニのBQPクラス定義、ショアのアルゴリズムへと連なる量子複雑性理論の発展を解説します。さらに現代物理学における情報理論・複雑性理論の爆発的展開を描きます。[p.190], [p.191]

  • 論理展開:
  • チャーチ＝チューリング＝ドイッチェのテーゼ：「有限な方法で実現可能な物理システムは、万能計算機械のモデルで完全にシミュレート可能」という物理的原理として計算可能性が再定式化され、「情報過程＝物理過程」という三位一体の図式が生まれる。[p.203], [p.204]
  • BQPクラスとショアのアルゴリズム（1994）：量子コンピュータで多項式時間計算可能なBQPにFactoringが含まれることを示し、RSA暗号の根幹を揺るがす発見として社会的反響を呼んだ。BQPはBPP⊆BQP⊆P^#Pという包含関係を持つ。[p.217], [p.224], [p.225]
  • ブラックホールのエントロピーとER=EPR：ベッケンシュタイン（1973）によるブラックホールエントロピーの面積比例則から、笠・高柳によるエンタングルメントエントロピーのホログラフィック導出（2006）、ラームズダンクの時空とエンタングルメントの結合（2010）、マルダセナ＆サスキンドのER=EPR仮説（2013）へと連なる現代物理学の最前線。[p.246], [p.261], [p.265], [p.286]
  • Susskindによる現代物理学の俯瞰：場の量子論・一般相対論・超弦理論・凝縮系物性論・量子情報理論・複雑性理論が量子エンタングルメントを軸に収斂しつつある全体像。[p.300]

■ Part V: 数学の「証明」をめぐって

  • この部の核心:

数学の証明が「誤り得るもの」「膨大になりすぎるもの」という現実的問題から出発し、Voevodskyの経験と主張を通じて、コンピュータ支援証明（UniMath/Coq）が21世紀の数学の形式を変えていく可能性を論じます。さらに「数学とNP問題」という問いを立て、複雑性理論のMerlin-Arthurクラスを通じて「人間と機械の共生」という新しい知的枠組みを展望します。[p.304], [p.305]

  • 論理展開:
  • 数学の証明の問題：フェルマーの定理、リーマン予想の誤った「証明」、有限単純群の分類（一万ページ超）など、数学の証明が誤り・膨大・検証困難という現実を示す。[p.307], [p.309]
  • Voevodskyの経験とUniMath：フィールズ賞受賞者でさえ自分の論文に誤りがあり、その確認に13年かかった経験から、数学の証明はコンピュータでチェックできるプログラムの形を取るべきという主張に至り、Coqを用いたUniMathライブラリを開発した。[p.321], [p.322], [p.323]
  • 数学とNP問題：数学の証明が「多項式時間で検証可能」であるならば、数学の証明可能な問題全体がNPクラスの構造を持つという示唆と、その違和感の正体を論じる。[p.346], [p.347]
  • Merlin-Arthurクラス（MA/AM）：信頼できない超優秀な数学者Mが証明を提出し、実直な検証者AがそれをチェックするというMAクラスの枠組みは、人間と機械の共生的な知的営為の複雑性理論的表現として示唆的である。AM=MA=NPという予想も紹介される。[p.350], [p.351]