2のn乗の話（Turingマシンについて）

全体概要

本セミナーは「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]

• 論理展開:
• 二進数 b_n…b_0 = Σ b_i・2^i という展開式を確認し、小数点以下への拡張も示す。[p.11], [p.12]
• 「二つのものをn個並べる重複順列の数」として 2ⁿ を把握し、n=3,4の具体例を列挙する。[p.16]
• n個の要素を持つ集合の部分集合数が 2ⁿ であることを帰納法で厳密に証明する。[p.22]
• 自然数を「自分より小さい自然数の集合」と定義し、2ⁿ を n={0,…,n-1} から 2={0,1} への関数の集まりとして再解釈。n=1,2,3,4 の全函数を具体的に列挙する。[p.25], [p.26], [p.27], [p.28], [p.29], [p.30], [p.31], [p.32]
• nを無限大ωに拡張し、2^ω を「無限の0と1の並び」として定義する。[p.34]

---

■ Part 2: ℭ = 2^{ℵ₀} ：連続体仮説

• この部の核心:

「個数を数える」という行為の分析から出発し、カントールが無限集合の濃度を「一対一対応」で定義したことで浮かび上がった驚くべき世界——部分が全体と同数の要素を持ち、平面上の点と直線上の点が同数であり、長さゼロのカントール集合が実数全体と同じ濃度を持つ——を丁寧に解説します。そして連続体仮説がZFC集合論から独立であるというコーエンの定理が、非ユークリッド幾何学の誕生と並ぶ数学史的転換点であることを示します。[p.4], [p.37]

• 論理展開:
• 「数える」ことの分析：順序数（Ordinals）と基数（Cardinals）の区別を、具体的な「箱の中のものを数える」図解で明確化する。[p.39], [p.40], [p.50]
• 無限集合の不思議：奇数・偶数・有理数・n個の自然数の組が、いずれも自然数全体と一対一対応することを示す（ヒルベルトの無限ホテルを含む）。[p.61], [p.62], [p.63], [p.64], [p.65], [p.67], [p.68]
• カントールの対角線論法：実数が自然数と一対一対応しないことを二通りの方法で証明し、実数の濃度 ℭ が非可算であることを確立する。[p.71], [p.72], [p.73], [p.74], [p.75]
• 平面とカントール集合の濃度：平面上の点が直線上の点と同濃度であること（座標のインターリーブ）、長さゼロのカントール集合が実数と同濃度であることを示す。[p.77], [p.78], [p.79], [p.81], [p.82], [p.83], [p.84]
• 連続体仮説 ℭ = ℵ₁ = 2^{ℵ₀} の定式化とヒルベルトの23の問題第1問への採択。[p.96], [p.97], [p.98], [p.99]
• ゲーデル（1940年）による無矛盾性証明と、コーエン（1963年）による独立性証明の意義を解説し、「非カントール的集合論」の発見として位置づける。[p.103], [p.108], [p.110]

---

■ Part 3: チューリング・マシン入門

• この部の核心:

チューリング・マシンという単純極まりない抽象機械——テープ・ヘッド・有限状態制御——が、計算可能なすべての計算のモデルとなり得ることを、7つの具体的な例を通して直感的かつ厳密に示します。無限ループ・Goto・条件分岐といったプログラムの基本構造が、すべてこの枠組みで表現可能であることを確認します。[p.5], [p.113]

• 論理展開:
• チューリング・マシンのメカニズム：テープ・ヘッド・状態遷移表の三要素と、停止状態Hの特別な役割を説明する。[p.116], [p.117]
• 例1（文字列長）：状態一つで0を1に書き換えながら右移動し、停止時に「一進数」で長さを表現する。[p.120], [p.121]
• 例2（1の個数の偶奇）：Even/Odd二状態でパリティを追跡し、PrintEven/PrintOddで結果を出力する。[p.123], [p.124], [p.125]
• 例3（文字列コピー）：Fetch→Copy→Mark→Backという状態遷移の連鎖で、AとBの間の文字列をBとCの間に複製する。[p.127], [p.128], [p.129]
• 例4（括弧バランス）：右括弧と左括弧を順にXで消去していく対角的アルゴリズムで正否を判定する。[p.130], [p.131]
• 例5〜7（無限ループ・Goto・条件分岐）：これらがすべてチューリング・マシンの状態と遷移で実現可能であることを示す。[p.145], [p.146], [p.147], [p.148]

---

■ Part 4: チューリング・マシンと計算可能な数

• この部の核心:

「計算可能」とは何かを帰納的関数（recursive function）として厳密に定義し、チョムスキー階層との対応を確認したうえで、衝撃的な事実——自然数上の関数の圧倒的多数が計算不能であること——を導きます。さらにアッカーマン関数とBusy Beaver問題を通じて「計算可能だが実際には手が届かない」領域の存在を示し、最後に計算複雑性理論（P・PSPACE・EXP）への橋渡しを行います。[p.6], [p.151]

• 論理展開:
• チョムスキー階層：正規言語→文脈自由→文脈依存→帰納的可算（チューリング・マシン）という包含関係と、自然言語がMildly Context-Sensitiveに位置するとされることを示す。[p.156], [p.157], [p.158]
• 帰納的集合と帰納的可算：計算可能性（全域関数）と帰納的可算性（部分関数）の違いを、S∈r.e. かつ S̄∈r.e. ⟺ Sが帰納的という定理で整理する。[p.162], [p.163], [p.164], [p.165]
• 停止問題の決定不能性：対角線論法を応用した計算表の構成により、停止問題を解くチューリング・マシンが存在しないことを証明する。[p.167], [p.169], [p.170], [p.171], [p.172]
• 計算可能関数の個数：チューリング・マシンが高々可算個しか存在しないため計算可能関数も可算個に限られる一方、自然数上の全関数は 2^ω 個（非可算）あり、大部分が計算不能であることを示す。乱数列とConwayの自由意志定理をその文脈で論じる。[p.176], [p.177], [p.178]
• アッカーマン関数：一般帰納関数として定義され原理的には計算可能だが、m,nが少し大きくなるだけで Ack(4,n) = 2^{n+3}-3、Ack(4,1) = 65533 等、実用的に計算不能な規模に爆発することを表で示す。[p.183], [p.184], [p.185]
• Busy Beaver問題：BB(1)〜BB(4)は判明しているが BB(5)以降は未確定であり、2016年にはBB(7910)・BB(1919)がZFC集合論から独立（決定不能）であることが証明された。有限の値を持ちながら数学的に到達不能な数の存在を示す。[p.187], [p.188], [p.189], [p.190], [p.191], [p.192], [p.193], [p.194], [p.195], [p.196], [p.197], [p.198], [p.199]
• 計算複雑性理論へ：P（多項式時間）・PSPACE（多項式空間）・EXP（指数時間 2^{q(n)}）の定義を提示し、nと2ⁿの間の隔たりが「計算の難しさ」の本質的な指標となることを示す。[p.201]