全体概要
このセミナー「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]。
■ Part 2: ディスレクシアと学習支援——計算アルゴリズムの教育的背景
計算アルゴリズムの教育という文脈で、Dyslexia（読み書き障害）の問題が取り上げられます。算数の手順を視覚化・構造化することが、特定の学習困難を持つ生徒への支援に繋がるという教育的問題意識が示されます [p.46, p.47]。
■ Part 3: チューリングマシン——計算の形式モデル
「計算」を数学的に厳密に定義したチューリングマシンの仕組みを、具体的なテープ・状態遷移・ヘッドの動作として解説します。計算とは「有限の規則で記号を書き換える手続き」に過ぎないという洞察が、以降の計算可能性理論の基盤となります [p.93〜p.110]。
■ Part 4: 計算可能性の限界——ゲーデル・チューリング・チャーチ
1930年代に数学・論理学の世界を震撼させた「計算できないことがある」という発見を、ゲーデルの不完全性定理・チューリングの停止問題・チャーチ＝チューリングのテーゼという三つの知的成果を通じて解説します。「証明できない真実がある」「停止するかどうか判定できないプログラムがある」という命題は、計算理論の根幹です [p.82〜p.92]。
■ Part 5: Busy Beaver——計算可能性の極北
Busy Beaver問題は、「Nステートのチューリングマシンが停止前に書き込む最大の1の個数BB(N)」を問う問題です。この関数は単に「大きい」のではなく、「いかなるチューリングマシンが計算しうる関数よりも速く増大する」という意味で、数学的に計算不可能であることが証明されています [p.130〜p.142]。
■ Part 6: 計算複雑性理論——PとNP
「解けるか否か」という計算可能性に続き、「効率よく解けるか」という計算複雑性の問題に移ります。P（多項式時間で解ける問題）とNP（多項式時間で答えを検証できる問題）の違い、そして「P=NP?」というコンピュータ科学最大の未解決問題を解説します [p.167〜p.170]。
■ Part 7: 量子計算とBQP——Shorのアルゴリズムの衝撃
量子コンピュータが効率的に解けるBQP（有界誤り量子多項式時間）クラスを導入し、1994年にShorが示した「素因数分解はBQPに属する」という結果が、RSA暗号の安全性を原理的に破壊し得ることを解説します [p.180〜p.183]。
■ Part 8: 計算複雑性と物理——エンタングルメント・重力・宇宙
講義の最終章では、計算複雑性の概念が物理学・宇宙論と深く結びつくという最前線の議論に踏み込みます。Susskind らによる「エンタングルメントと複雑性が時空の幾何（ブラックホールの内部体積）に対応する」という仮説は、理論物理とコンピュータ科学の統合の可能性を示唆します [p.185〜p.194]。