講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナーは「2のn乗の話」と題し、一見シンプルな数式 **2ⁿ** を起点として、数学・計算理論・集合論にまたがる深遠な世界へと聴衆を誘う知的冒険の旅です。2のn乗という概念が、二進数・順列・部分集合・関数という複数の顔を持つことをまず確認し、それをnを無限大に押し広げたとき何が起きるかという問いが全体を貫く中心軸となっています。
第一の柱は「連続体仮説」です。カントールが19世紀末に提唱した「実数の個数 ℭ は 2^{ℵ₀} に等しいか」という問いは、数学史上最も有名な未解決問題の一つとなり、ゲーデル（1940年）によるモデルの無矛盾性証明、コーエン（1963年）による独立性証明という二段階を経て、ZFC集合論からは原理的に証明も反証もできないことが確定しました。これは非ユークリッド幾何学の登場と同様の衝撃を数学の基礎に与えた「非カントール的集合論」の発見を意味します。
第二の柱は「チューリング・マシン」です。1936年にアラン・チューリングが提唱したこの抽象機械は、計算可能性の概念を厳密に定義し、現代コンピュータ科学の礎となっています。本セミナーでは、文字列処理・コピー・括弧照合・条件分岐といった具体的な例を通じてその動作原理を丁寧に解説します。
第三の柱は「計算可能性と複雑性」です。自然数から自然数への関数の圧倒的多数が計算不能であること、アッカーマン関数やBusy Beaver問題が示す「計算可能だが手の届かない有限」の存在、そして多項式時間（P）と指数時間（EXP）の間に横たわる複雑性の壁これらを通じて、2ⁿという指数的爆発が計算の難しさそのものの指標となることが示されます。セミナー全体を通じて、「2のn乗」という素朴な出発点が、数学・論理学・計算理論のもっとも深い問いへの入り口であることが明らかになります。
講義のロードマップ
ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。
■ Part 1: 「2のn乗」の様々な解釈
2ⁿという数式が持つ複数の解釈二進数表現・重複順列・部分集合の個数・関数の集まりを順に展開することで、有限から無限へと概念を自然に拡張する足場を築きます。特に、自然数全体ωに対する 2^ω が「0と1の無限列全体」あるいは「ω上の {0,1} 値関数全体」として解釈できることが、後続パートへの架け橋となります。 [p.3, p.8]
■ Part 2: ℭ = 2^{ℵ₀} ：連続体仮説
「個数を数える」という行為の分析から出発し、カントールが無限集合の濃度を「一対一対応」で定義したことで浮かび上がった驚くべき世界部分が全体と同数の要素を持ち、平面上の点と直線上の点が同数であり、長さゼロのカントール集合が実数全体と同じ濃度を持つを丁寧に解説します。そして連続体仮説がZFC集合論から独立であるというコーエンの定理が、非ユークリッド幾何学の誕生と並ぶ数学史的転換点であることを示します。[p.4, p.37]
■ Part 3: チューリング・マシン入門
チューリング・マシンという単純極まりない抽象機械テープ・ヘッド・有限状態制御が、計算可能なすべての計算のモデルとなり得ることを、7つの具体的な例を通して直感的かつ厳密に示します。無限ループ・Goto・条件分岐といったプログラムの基本構造が、すべてこの枠組みで表現可能であることを確認します。[p.5, p.113]
■ Part 4: チューリング・マシンと計算可能な数
「計算可能」とは何かを帰納的関数（recursive function）として厳密に定義し、チョムスキー階層との対応を確認したうえで、衝撃的な事実自然数上の関数の圧倒的多数が計算不能であることを導きます。さらにアッカーマン関数とBusy Beaver問題を通じて「計算可能だが実際には手が届かない」領域の存在を示し、最後に計算複雑性理論（P・PSPACE・EXP）への橋渡しを行います。[p.6, p.151]
ページのナビゲート