講演資料


講義資料スライドの表紙

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

全体概要

このセミナー「20181015Math3」は、マルレクが展開する数理・計算理論シリーズの一環として、「コンピュータは何を計算できるのか、そしてその限界はどこにあるのか」という根源的な問いを、数学・歴史・現代AI研究の交差点から深く掘り下げる講義です。

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

さらに講義は現代の計算複雑性理論へと進み、P問題・NP問題というコンピュータ科学最大の未解決問題 [p.167]〜[p.170] を解説します。そして量子計算・BQPクラス [p.180]〜[p.183] へと議論を展開し、Shorのアルゴリズムによる素因数分解の効率化が暗号理論に与える衝撃を論じます。最終章では計算複雑性と物理学・宇宙の構造（エンタングルメント・複雑性・重力）の深い関係を問う最前線の議論 [p.185]〜[p.194] まで到達します。「計算とは何か」という問いが、数学・情報科学・物理学を貫く統一的テーマとして結晶する、知的密度の高い講義です。

講義のロードマップ

■ Part 1: 算数の計算アルゴリズム——手続きとしての計算

  • この部の核心:

コンピュータが実行する「アルゴリズム」の本質を、小学校の算数（掛け算・割り算・分数の四則演算）を題材に具体化します。人間が紙の上で行う計算手順を形式的ステップとして分解することで、「計算とは何か」を直観的に捉えさせる導入部です [p.8]〜[p.19]〜[p.22]〜[p.31]。

  • 論理展開:
  • 37×64のような2桁同士の掛け算を、段階的なステップ（部分積の加算）に分解して示す [p.9]〜[p.16]。
  • 2352÷21など割り算の手順を形式化し、「計算量（ステップ数）」の概念を導入する [p.18], [p.19]。
  • 分数の加減乗除（1/2+2/3、2/3−1/2、1/2×2/4、1/2÷2/4 等）をそれぞれ具体的なステップで示し、通分・倍分の手続きを明示する [p.22]〜[p.31]。

■ Part 2: ディスレクシアと学習支援——計算アルゴリズムの教育的背景

  • この部の核心:

計算アルゴリズムの教育という文脈で、Dyslexia（読み書き障害）の問題が取り上げられます。算数の手順を視覚化・構造化することが、特定の学習困難を持つ生徒への支援に繋がるという教育的問題意識が示されます [p.46], [p.47]。

  • 論理展開:
  • Dyslexiaの定義・特性と、算数学習における困難の関係が概説される [p.46], [p.47]。
  • 計算手順の図示・視覚的分解が学習支援ツールとして機能することが示唆される [p.48]〜[p.57]。

■ Part 3: チューリングマシン——計算の形式モデル

  • この部の核心:

「計算」を数学的に厳密に定義したチューリングマシンの仕組みを、具体的なテープ・状態遷移・ヘッドの動作として解説します。計算とは「有限の規則で記号を書き換える手続き」に過ぎないという洞察が、以降の計算可能性理論の基盤となります [p.93]〜[p.110]。

  • 論理展開:
  • チューリングマシンの基本構成（テープ・状態・遷移規則）を図示し、「B 1 0 0 1 1 0 B」のような具体的テープ上での動作例を示す [p.97]〜[p.104]。
  • 「1の個数を数えて末尾に結果を書く」「2進数列をコピーする」「括弧の対応を検証する」など、段階的に複雑な計算タスクの実装例を詳細に展開する [p.102]〜[p.124]。
  • チューリングマシンで計算できることの「普遍性」と、そのシンプルな規則の力強さを強調する [p.97], [p.146]。

■ Part 4: 計算可能性の限界——ゲーデル・チューリング・チャーチ

  • この部の核心:

1930年代に数学・論理学の世界を震撼させた「計算できないことがある」という発見を、ゲーデルの不完全性定理・チューリングの停止問題・チャーチ＝チューリングのテーゼという三つの知的成果を通じて解説します。「証明できない真実がある」「停止するかどうか判定できないプログラムがある」という命題は、計算理論の根幹です [p.82]〜[p.92]。

  • 論理展開:
  • ゲーデルの不完全性定理（1930年）：「自己言及的な命題G（自分自身が証明不可能であることを主張する命題）」の構成により、無矛盾な体系は必ず決定不能な命題を含むことを示す [p.84], [p.85]。
  • チューリングの停止問題：`halts(g)` 関数が存在すると仮定した場合の矛盾（`def g(): if halts(g): loop_forever()`）を示し、停止判定プログラムが原理的に作れないことを証明する [p.86]。
  • チャーチ＝チューリングのテーゼ：「効果的に計算可能な関数は一般帰納的関数である」というテーゼが1940年代に確立し、計算可能性の範囲が確定したことを述べる [p.92]。

■ Part 5: Busy Beaver——計算可能性の極北

  • この部の核心:

Busy Beaver問題は、「Nステートのチューリングマシンが停止前に書き込む最大の1の個数BB(N)」を問う問題です。この関数は単に「大きい」のではなく、「いかなるチューリングマシンが計算しうる関数よりも速く増大する」という意味で、数学的に計算不可能であることが証明されています [p.130]〜[p.142]。

  • 論理展開:
  • BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107 は既知だが、BB(5)≥47,176,870、BB(6)≥7.412×10^36534 と爆発的に増大する [p.130], [p.131]。
  • BB(6)の下限値の10進数展開（数十ページにわたる巨大な数）を実際に掲載し、その規模感を体感させる [p.132]〜[p.137]。
  • 2016年にYedidia & Aaronsonが「BB(7910)の値は集合論の公理系では証明できない」ことを示し、後に改良されてBB(1919)も同様であることが示された [p.141]。
  • Busy Beaverは計算複雑性の「上限」であり、それを超える関数は存在しないという意味で計算可能性理論の到達点をなす [p.139], [p.142]。

■ Part 6: 計算複雑性理論——PとNP

  • この部の核心:

「解けるか否か」という計算可能性に続き、「効率よく解けるか」という計算複雑性の問題に移ります。P（多項式時間で解ける問題）とNP（多項式時間で答えを検証できる問題）の違い、そして「P=NP?」というコンピュータ科学最大の未解決問題を解説します [p.167]〜[p.170]。

  • 論理展開:
  • P問題とNP問題の定義を整理し、素因数分解（NとN=p×qの関係）を具体例としてNPに属する問題の特徴を説明する [p.168]。
  • co-NP・NP完全問題の概念を導入し、NP完全問題がPに属するかどうかが未解決であることを強調する [p.169]。
  • 2000年にクレイ数学研究所がP=NP?問題をミレニアム問題の一つに選定し、賞金100万ドルが懸けられていることを紹介する [p.170]。

■ Part 7: 量子計算とBQP——Shorのアルゴリズムの衝撃

  • この部の核心:

量子コンピュータが効率的に解けるBQP（有界誤り量子多項式時間）クラスを導入し、1994年にShorが示した「素因数分解はBQPに属する」という結果が、RSA暗号の安全性を原理的に破壊し得ることを解説します [p.180]〜[p.183]。

  • 論理展開:
  • BQPはBernstein & Vaziraniが1993年に定義した量子計算の複雑性クラスであることを述べる [p.182]。
  • Shor(1994)の素因数分解アルゴリズムがBQPに属することが示され、RSA暗号への影響が論じられる [p.181], [p.182]。
  • BQPとP、NPの包含関係の現状（BQP⊄NP、NP⊄BQP の可能性がいずれも未証明）を図示する [p.182], [p.183]。

■ Part 8: 計算複雑性と物理——エンタングルメント・重力・宇宙

  • この部の核心:

講義の最終章では、計算複雑性の概念が物理学・宇宙論と深く結びつくという最前線の議論に踏み込みます。Susskind らによる「エンタングルメントと複雑性が時空の幾何（ブラックホールの内部体積）に対応する」という仮説は、理論物理とコンピュータ科学の統合の可能性を示唆します [p.185]〜[p.194]。

  • 論理展開:
  • Nature 2015年論文「The quantum source of space-time」を参照し、量子エンタングルメントが時空を生成するという概念を導入する [p.186]。
  • Susskind「Entanglement and Complexity: Gravity and Quantum Mechanics」講演を参照し、ブラックホールの計算複雑性（回路複雑性）が内部体積の増大に対応するという主張を紹介する [p.189]。
  • MA・AMなどの対話的証明複雑性クラスや、COQなどの定理証明支援系も計算複雑性の文脈で言及される [p.194]。
  • AIと計算複雑性、「計算可能性の限界がAI研究の限界に何を示唆するか」という問いで講義全体を締め括る [p.195]。