第2章 計算理論の基礎
はじめに
「計算とは何か」という根本的な問いは、コンピュータサイエンスの中核をなす問題です。本章では、計算の数学的モデルとしてのチューリング機械を導入し、計算可能性と決定可能性の概念を学びます。これらの概念は、アルゴリズムの限界を理解し、解ける問題と解けない問題を区別する理論的基盤を提供します。
20世紀前半、数学者たちは「効果的に計算可能」とは何かを厳密に定義しようと試みました。その結果、チューリング、チャーチ、クリーネなどによって提案された様々な計算モデルが、すべて同じ計算能力を持つことが明らかになりました。この驚くべき一致は、計算可能性の本質的な特徴を捉えていることを示唆しています。
2.1 計算モデル
2.1.1 チューリング機械の直観的理解
チューリング機械（Turing machine）は、1936年にアラン・チューリングによって提案された抽象的な計算モデルです。人間が紙と鉛筆で行う計算過程を抽象化したもので、以下の要素から構成されます：
- 無限に長いテープ：記号を書き込める升目に分かれている
- 読み書きヘッド：テープ上の1つの升目を読み書きできる
- 有限個の内部状態：機械の「記憶」に相当
- 遷移規則：現在の状態とテープの記号に基づいて次の動作を決定
チューリング機械は、現在の状態とヘッドが読んでいる記号に基づいて：
- 新しい記号をテープに書き込む
- ヘッドを左または右に移動する
- 新しい状態に遷移する
2.1.2 チューリング機械の形式的定義
graph TD
subgraph "チューリング機械の構成要素"
subgraph "形式的定義: M = (Q, Σ, Γ, δ, q₀, qaccept, qreject)"
States["Q: 状態の有限集合<br/>{q₀, q₁, q₂, ..., qaccept, qreject}"]
InputAlphabet["Σ: 入力アルファベット<br/>{0, 1} または {a, b, c}"]
TapeAlphabet["Γ: テープアルファベット<br/>Σ ∪ {␣} ∪ {補助記号}"]
Transition["δ: 遷移関数<br/>Q × Γ → Q × Γ × {L, R}"]
Initial["q₀: 初期状態<br/>計算開始時の状態"]
Accept["qaccept: 受理状態<br/>入力を受理"]
Reject["qreject: 拒否状態<br/>入力を拒否"]
end
subgraph "遷移規則の例"
Rule1["δ(q₁, 0) = (q₂, 1, R)<br/>状態q₁で0を読む→<br/>状態q₂、1を書く、右へ"]
Rule2["δ(q₂, ␣) = (qaccept, ␣, L)<br/>状態q₂で空白を読む→<br/>受理状態、空白のまま、左へ"]
end
subgraph "チューリング機械の動作原理"
CurrentState["現在の状態 q"]
ReadSymbol["読取り記号 a"]
LookupRule["遷移規則を参照<br/>δ(q, a) = (r, b, X)"]
NewState["新しい状態 r"]
WriteSymbol["書込み記号 b"]
MoveHead["ヘッド移動 X"]
CurrentState --> LookupRule
ReadSymbol --> LookupRule
LookupRule --> NewState
LookupRule --> WriteSymbol
LookupRule --> MoveHead
end
subgraph "計算の終了条件"
AcceptCondition["受理条件<br/>qaccept に到達"]
RejectCondition["拒否条件<br/>qreject に到達"]
InfiniteLoop["無限ループ<br/>停止しない計算"]
end
end
style States fill:#e3f2fd
style Transition fill:#fff3e0
style Rule1 fill:#e8f5e8
style LookupRule fill:#f3e5f5
style AcceptCondition fill:#e8f5e8
style RejectCondition fill:#ffebee
定義 2.1 チューリング機械は7つ組 M = (Q, Σ, Γ, δ, q₀, qaccept, qreject) である。ここで：
- Q：状態の有限集合
- Σ：入力アルファベット（空白記号 ␣ を含まない）
- Γ：テープアルファベット（␣ ∈ Γ かつ Σ ⊆ Γ）
- δ：Q × Γ → Q × Γ × {L, R}：遷移関数
- q₀ ∈ Q：初期状態
- qaccept ∈ Q：受理状態
- qreject ∈ Q：拒否状態（qaccept ≠ qreject）
遷移関数 δ(q, a) = (r, b, X) は以下を意味します：
- 状態 q で記号 a を読んだとき
- 状態 r に遷移し
- 記号 b を書き込み
- ヘッドを X 方向（L：左、R：右）に移動する
2.1.3 チューリング機械の構成と計算
定義 2.2 チューリング機械 M の構成（configuration）は、現在の状態、テープの内容、ヘッドの位置を表す。形式的には、文字列 uqv で表現される。ここで：
- q は現在の状態
- uv はテープの内容（空白でない部分）
- ヘッドは v の最初の記号を指している（v が空なら空白を指している）
例 2.1 構成 1011q₅0111 は：
- 現在の状態：q₅
- テープの内容：10110111…
- ヘッドの位置：5番目の記号（0）を指している
graph LR
subgraph "チューリング機械の構成"
subgraph "テープ"
T1[1] --- T2[0] --- T3[1] --- T4[1] --- T5[0] --- T6[1] --- T7[1] --- T8[1] --- T9[...]
end
subgraph "制御部"
State[状態: q₅]
end
Head[読み書きヘッド]
Head -.-> T5
State -.-> Head
style T5 fill:#ffeb3b
style State fill:#e3f2fd
style Head fill:#fff3e0
end
subgraph "説明"
Info["現在状態: q₅<br/>読取り記号: 0<br/>ヘッド位置: 5"]
end
定義 2.3 構成 C₁ が構成 C₂ に1ステップで遷移することを C₁ ⊢ C₂ と表記する。
遷移規則：δ(q, a) = (r, b, X) のとき、状態 q でヘッドが記号 a を読むと：
- 記号 a を b に書き換える
- 状態を r に変更する
- ヘッドを X 方向（L：左、R：右）に移動する
構成の遷移は状況に応じて以下のようになる：
- 左移動：ucqav ⊢ uqcbv （c は u の最後の記号、a を b に書き換えて左へ移動）
- 右移動：uqav ⊢ ubrv または uqa ⊢ ubr␣
定義 2.4 チューリング機械 M が入力 w を受理するとは：
- 初期構成 q₀w から始めて
- 受理状態を含む構成に到達すること
M が w を拒否するとは：
- 拒否状態を含む構成に到達すること
M が w で停止するとは：
- 受理または拒否すること
2.1.4 チューリング機械の例
| 例 2.2 言語 L = {0ⁿ1ⁿ | n ≥ 0} を認識するチューリング機械 |
この言語は、同数の0と1が順番に並んだ文字列の集合です。
アルゴリズムの概要：
- 最左端の0を見つけてxに置き換える
- 右に移動して対応する1を見つけてyに置き換える
- 左に戻って次の0を探す
- すべての0と1が対応したら受理、そうでなければ拒否
形式的な記述： M = (Q, Σ, Γ, δ, q₁, qaccept, qreject) where:
- Q = {q₁, q₂, q₃, q₄, q₅, qaccept, qreject}
- Σ = {0, 1}
- Γ = {0, 1, x, y, ␣}
遷移関数δ：
δ(q₁, 0) = (q₂, x, R) // 0をxに変えて右へ
δ(q₁, y) = (q₁, y, R) // yをスキップ
δ(q₁, ␣) = (qaccept, ␣, R) // すべて処理済みなら受理
δ(q₂, 0) = (q₂, 0, R) // 0をスキップ
δ(q₂, y) = (q₂, y, R) // yをスキップ
δ(q₂, 1) = (q₃, y, L) // 1をyに変えて左へ
δ(q₃, 0) = (q₃, 0, L) // 0をスキップして左へ
δ(q₃, y) = (q₃, y, L) // yをスキップして左へ
δ(q₃, x) = (q₁, x, R) // xに到達したら右へ
// エラー処理
δ(q₁, 1) = (qreject, 1, R)
δ(q₂, ␣) = (qreject, ␣, R)
計算例：入力 “0011” に対する計算過程
q₁0011 ⊢ xq₂011 ⊢ x0q₂11 ⊢ x0yq₃1 ⊢ xq₃0y1 ⊢ q₃x0y1 ⊢ xq₁0y1
⊢ xxq₂y1 ⊢ xxyq₂1 ⊢ xxyyq₃ ⊢ xxyq₃y ⊢ xxq₃yy ⊢ xq₃xyy
⊢ xxq₁yy ⊢ xxyq₁y ⊢ xxyyq₁ ⊢ xxyy␣qaccept
2.2 計算可能性
graph TD
subgraph "計算可能性の概念と階層"
subgraph "計算可能関数"
Computable["チューリング計算可能関数<br/>f: Σ* → Σ*<br/>・全ての入力で停止<br/>・正しい出力を生成"]
PartialComputable["部分計算可能関数<br/>f: Σ* ⇀ Σ*<br/>・定義域で停止<br/>・定義域外で停止しない"]
Examples["例:<br/>・加算、乗算<br/>・文字列操作<br/>・ソート、探索"]
end
subgraph "Church-Turingの提唱"
Thesis["直観的計算可能 ≡ チューリング計算可能<br/>・数学的定理ではない<br/>・計算の本質に関する主張"]
Evidence["支持する証拠<br/>・他の計算モデルとの等価性<br/>・実用プログラムとの対応<br/>・70年以上の検証"]
Models["等価な計算モデル<br/>・λ計算 (Church)<br/>・再帰関数 (Kleene)<br/>・Post機械<br/>・RAM"]
end
subgraph "計算可能性の限界"
Decidable["決定可能問題<br/>・有限時間で判定<br/>・Yes/No を確定"]
Undecidable["決定不能問題<br/>・アルゴリズムが存在しない<br/>・原理的に解けない"]
Examples2["決定不能な例<br/>・停止問題<br/>・同値問題<br/>・ヒルベルト第10問題"]
end
end
style Computable fill:#e8f5e8
style Thesis fill:#fff3e0
style Decidable fill:#e3f2fd
style Undecidable fill:#ffebee
style Examples2 fill:#ffebee
2.2.1 チューリング計算可能関数
定義 2.5 関数 f: Σ* → Σ* がチューリング計算可能（Turing computable）であるとは、以下を満たすチューリング機械 M が存在することである：
- すべての w ∈ Σ* に対して
- M を入力 w で開始すると
- M は停止し、テープ上に f(w) のみが残る
例 2.3 文字列を逆順にする関数 rev: {0,1}* → {0,1}* はチューリング計算可能である。
証明の概要：以下のアルゴリズムを実装するチューリング機械を構成できる：
- 入力の最後の文字を記憶
- その文字を消去
- テープの右端に移動してその文字を書く
- 元の位置に戻って繰り返す
2.2.2 部分関数と計算可能性
実際の計算では、すべての入力に対して定義されない関数（部分関数）も重要です。
定義 2.6 部分関数 f: Σ* ⇀ Σ* がチューリング計算可能であるとは、以下を満たすチューリング機械 M が存在することである：
- f(w) が定義されている場合、M は停止して f(w) を出力する
- f(w) が定義されていない場合、M は停止しない（無限ループまたは拒否状態に入る）
2.2.3 Church-Turingの提唱
Church-Turingの提唱（Church-Turing thesis）： 「直観的に計算可能な関数は、チューリング機械で計算可能な関数と一致する」
これは数学的定理ではなく、「計算」の本質に関する主張です。以下の事実がこの提唱を支持します：
- 他の計算モデルとの等価性：
- ラムダ計算（Church）
- 再帰関数（Kleene）
- Post機械
- ランダムアクセス機械 これらはすべてチューリング機械と同じ計算能力を持つ
- プログラミング言語との対応： 現代のプログラミング言語で書けるアルゴリズムは、すべてチューリング機械でシミュレート可能
2.3 決定可能性
graph TD
subgraph "決定可能性の階層構造"
subgraph "言語クラスの包含関係"
Finite["有限言語<br/>・文字列の有限集合<br/>・常に決定可能"]
Regular["正規言語<br/>・DFA/NFAで認識<br/>・正規表現で記述"]
ContextFree["文脈自由言語<br/>・PDAで認識<br/>・CFGで生成"]
Decidable["決定可能言語<br/>・必ず停止するTM<br/>・全入力でYes/No"]
Recognizable["認識可能言語<br/>・TMで認識<br/>・停止しない場合あり"]
AllLanguages["全ての言語<br/>・認識不能言語を含む"]
Finite --> Regular
Regular --> ContextFree
ContextFree --> Decidable
Decidable --> Recognizable
Recognizable --> AllLanguages
end
subgraph "決定可能言語の性質"
Closure["閉包性<br/>・和集合 ∪<br/>・積集合 ∩<br/>・補集合 ¯<br/>・連結 ○<br/>・クリーネ閉包 *"]
Algorithm["決定アルゴリズム<br/>・入力を読む<br/>・有限ステップで判定<br/>・必ず停止"]
Examples["例<br/>・PRIME: 素数判定<br/>・CONNECTED: 連結性<br/>・MATCHING: マッチング"]
end
subgraph "認識可能だが決定不能"
ATM["受理問題 ATM<br/>{⟨M,w⟩ | M は w を受理}<br/>・万能TMで認識可能<br/>・停止問題への還元で決定不能"]
Complement["補言語<br/>ATM の補集合は認識不能<br/>→ 決定不能の証明"]
Reduction["還元による証明<br/>停止問題 → ATM<br/>対角化論法"]
end
end
style Finite fill:#e8f5e8
style Decidable fill:#e3f2fd
style Recognizable fill:#fff3e0
style AllLanguages fill:#ffebee
style ATM fill:#ffe0b2
style Reduction fill:#f3e5f5
2.3.1 言語と決定問題
定義 2.7 アルファベット Σ 上の言語（language）は、Σ* の部分集合である。
計算理論では、問題を言語として形式化します：
- 問題のインスタンス → 文字列
- “Yes”のインスタンス → 言語の要素
- “No”のインスタンス → 言語に含まれない文字列
例 2.4
-
PRIME = {n n は2進表記された素数} -
CONNECTED = {⟨G⟩ G は連結グラフ}
2.3.2 決定可能言語
定義 2.8 言語 L が決定可能（decidable）または再帰的（recursive）であるとは、L を決定するチューリング機械が存在することである。すなわち、ある機械 M が存在して：
- w ∈ L ならば M は w を受理する
- w ∉ L ならば M は w を拒否する
- M はすべての入力で停止する
決定可能言語の例：
- 有限言語：すべての有限言語は決定可能
- 正規言語：DFAで認識される言語
- 文脈自由言語：CFGで生成される言語
定理 2.1 決定可能言語は以下の演算に関して閉じている：
- 和集合：L₁, L₂ が決定可能 → L₁ ∪ L₂ も決定可能
- 積集合：L₁, L₂ が決定可能 → L₁ ∩ L₂ も決定可能
- 補集合：L が決定可能 → L̄ も決定可能
- 連結：L₁, L₂ が決定可能 → L₁L₂ も決定可能
- クリーネ閉包：L が決定可能 → L* も決定可能
証明（和集合の場合）： L₁ を決定する機械を M₁、L₂ を決定する機械を M₂ とする。 L₁ ∪ L₂ を決定する機械 M を以下のように構成する：
M = “入力 w に対して：
- M₁ を w でシミュレートする
- M₁ が受理したら、受理する
- M₁ が拒否したら、M₂ を w でシミュレートする
- M₂ が受理したら受理、拒否したら拒否する”
M₁, M₂ は必ず停止するので、M も必ず停止する。□
2.3.3 認識可能言語
定義 2.9 言語 L が認識可能（recognizable）または再帰的可算（recursively enumerable）であるとは、L を認識するチューリング機械が存在することである。すなわち、ある機械 M が存在して：
- w ∈ L ならば M は w を受理する
- w ∉ L ならば M は w を拒否するか、永遠に動作し続ける
定理 2.2 L が決定可能 ⟺ L と L̄ の両方が認識可能
証明（⇒）：L が決定可能なら、定義より L は認識可能。 L を決定する機械の受理と拒否を入れ替えれば L̄ を決定する機械が得られるので、L̄ も認識可能。
（⇐）：L を認識する機械を M₁、L̄ を認識する機械を M₂ とする。 以下の機械 M は L を決定する：
M = “入力 w に対して：
- M₁ と M₂ を並行してシミュレートする
- M₁ が受理したら、受理する
- M₂ が受理したら、拒否する”
w ∈ L または w ∈ L̄ のいずれかが成り立つので、M は必ず停止する。□
2.4 チューリング機械の変種
graph TD
subgraph "チューリング機械の変種と等価性"
subgraph "多テープチューリング機械"
MultiTape["k-テープ機械<br/>・k本の独立テープ<br/>・各テープに読み書きヘッド<br/>・δ: Q × Γᵏ → Q × Γᵏ × {L,R}ᵏ"]
MTAdvantage["利点<br/>・プログラミングが容易<br/>・時間効率が良い<br/>・実用的なアルゴリズム"]
MTExample["例: テープ1 = 入力<br/>テープ2 = 作業領域<br/>テープ3 = 出力"]
end
subgraph "非決定性チューリング機械"
NTM["非決定性TM<br/>・複数の選択肢<br/>・並行計算パス<br/>・1つでも受理なら受理"]
NTMTree["計算木<br/>分岐する計算パス<br/>幅優先探索でシミュレート"]
NTMEquiv["等価性<br/>決定性TMでシミュレート可能<br/>指数的時間増加"]
end
subgraph "その他の変種"
LBA["線形拘束オートマトン<br/>・入力長に比例する領域<br/>・文脈依存言語と等価"]
PTM["確率的TM<br/>・ランダムビット使用<br/>・エラー確率あり<br/>・効率的アルゴリズム"]
OTM["オラクルTM<br/>・外部情報源アクセス<br/>・相対的計算可能性<br/>・複雑度理論の基礎"]
end
subgraph "計算能力の等価性"
Standard["標準TM"]
Standard -.->|"シミュレート"| MultiTape
Standard -.->|"シミュレート"| NTM
Standard -.->|"制限"| LBA
Equivalence["Church-Turingの提唱<br/>全ての合理的な計算モデルは<br/>チューリング機械と等価"]
end
end
style MultiTape fill:#e3f2fd
style NTM fill:#fff3e0
style LBA fill:#f3e5f5
style Standard fill:#e8f5e8
style Equivalence fill:#ffe0b2
2.4.1 多テープチューリング機械
定義 2.10 k-テープチューリング機械は、k 本の独立したテープを持ち、各テープに独立した読み書きヘッドを持つ。
遷移関数：δ: Q × Γᵏ → Q × Γᵏ × {L, R}ᵏ
定理 2.3 多テープチューリング機械は、単一テープチューリング機械と同じ計算能力を持つ。
証明の概要：k-テープ機械 M を単一テープ機械 S でシミュレートする。 S のテープを k 個の領域に分け、各領域が M の各テープを表現する。 ヘッドの位置は特殊な記号でマークする。
例：3テープ機械の構成
テープ1: a b c
↑
テープ2: x y z
↑
テープ3: 1 2 3
↑
を単一テープで表現：
#â b c#x ŷ z#1̂ 2 3#
（ˆ はヘッドの位置を示す）
S の1ステップで M の1ステップをシミュレートできる。□
2.4.2 非決定性チューリング機械
定義 2.11 非決定性チューリング機械（NTM）では、遷移関数が遷移の集合を返す： δ: Q × Γ → P(Q × Γ × {L, R})
各ステップで、機械は可能な遷移の中から非決定的に1つを選択する。
定義 2.12 NTM M が入力 w を受理するとは、少なくとも1つの計算パスが受理状態に到達することである。
定理 2.4 非決定性チューリング機械は、決定性チューリング機械と同じ計算能力を持つ。
証明の概要：NTM N を決定性TM D でシミュレートする。 D は N のすべての可能な計算パスを幅優先探索で系統的に探索する。
計算木の各ノードは N の構成を表し、子ノードは可能な遷移先を表す。 D は以下のように動作：
- 深さ1のすべてのパスを探索
- 深さ2のすべてのパスを探索
- 以下同様
受理構成が見つかれば受理、すべての有限パスが拒否なら拒否。□
2.4.3 線形拘束オートマトン
定義 2.13 線形拘束オートマトン（Linear Bounded Automaton, LBA）は、テープの使用を入力長に比例する範囲に制限したチューリング機械である。
形式的には、入力の両端に特殊な端記号を置き、その間でのみ動作する。
定理 2.5 LBAで認識される言語のクラスは、文脈依存言語のクラスと一致する。
2.4.4 確率的チューリング機械
定義 2.14 確率的チューリング機械（Probabilistic TM）は、各ステップでコイン投げの結果を利用できるチューリング機械である。
形式的には、特別な状態でランダムビットを生成し、その結果に基づいて遷移する。
確率的計算の受理条件：
- 片側誤り：w ∈ L → Pr[M accepts w] ≥ 2/3、w ∉ L → Pr[M accepts w] = 0
- 両側誤り：w ∈ L → Pr[M accepts w] ≥ 2/3、w ∉ L → Pr[M accepts w] ≤ 1/3
2.5 万能チューリング機械
graph TD
subgraph "万能チューリング機械の構成と意義"
subgraph "符号化の概念"
Encoding["チューリング機械の符号化<br/>M → ⟨M⟩<br/>・状態を番号で表現<br/>・遷移規則をリスト化<br/>・一意な文字列表現"]
Example["符号化例<br/>状態: q₁, q₂, ...<br/>記号: a₁, a₂, ...<br/>遷移: ⟨i,j,k,l,D⟩"]
SelfRef["自己参照<br/>機械が自分の記述を<br/>入力として受け取る"]
end
subgraph "万能機械の構成"
UTM["万能チューリング機械 U<br/>入力: ⟨M, w⟩<br/>動作: M を w でシミュレート<br/>出力: M の計算結果"]
ThreeTape["3テープ構成<br/>テープ1: M のテープ内容<br/>テープ2: M の遷移規則<br/>テープ3: M の現在状態"]
SimulationStep["シミュレーション手順<br/>1. 現在状態と記号を読む<br/>2. 遷移規則を検索<br/>3. 状態更新、記号書換え<br/>4. ヘッド移動"]
end
subgraph "万能性の意義"
StoredProgram["プログラム内蔵方式<br/>・プログラムもデータ<br/>・ソフトウェアの基礎<br/>・現代コンピュータの原理"]
SelfModifying["自己修正プログラム<br/>・実行中に自分を変更<br/>・コンパイラ、インタープリター<br/>・人工知能の基礎"]
Limitations["計算の限界<br/>・万能機械でも解けない問題<br/>・停止問題の決定不能性<br/>・アルゴリズムの本質的限界"]
end
subgraph "応用と影響"
ModernCS["現代コンピュータ科学<br/>・ソフトウェア工学<br/>・プログラミング言語<br/>・オペレーティングシステム"]
Complexity["計算量理論<br/>・P vs NP問題<br/>・時間・空間計算量<br/>・アルゴリズム設計"]
AI["人工知能<br/>・機械学習<br/>・パターン認識<br/>・知識表現"]
end
end
style UTM fill:#e3f2fd
style StoredProgram fill:#e8f5e8
style Limitations fill:#ffebee
style ModernCS fill:#fff3e0
style SelfRef fill:#f3e5f5
2.5.1 チューリング機械の符号化
チューリング機械自体を文字列として表現できます。
定義 2.15 チューリング機械 M = (Q, Σ, Γ, δ, q₀, qaccept, qreject) の符号化 ⟨M⟩ は、M の構造を一意に表現する文字列である。
符号化の例：
- 状態を q₁, q₂, …, qₙ と番号付け
- 記号を a₁, a₂, …, aₘ と番号付け
- 遷移 δ(qᵢ, aⱼ) = (qₖ, aₗ, D) を ⟨i, j, k, l, D⟩ として符号化
2.5.2 万能チューリング機械の構成
定理 2.6 万能チューリング機械 U が存在する。U は入力 ⟨M, w⟩ に対して、M が w に対して行う計算をシミュレートする。
証明の概要：U を3テープ機械として構成する：
- テープ1：シミュレート対象の機械 M のテープ内容
- テープ2：M の遷移規則（⟨M⟩の一部）
- テープ3：M の現在の状態
U の動作：
- 入力 ⟨M, w⟩ を適切なテープに配置
- M の初期構成を設定
- 以下を繰り返す：
- 現在の状態と読んでいる記号から、適用する遷移規則を探す
- 遷移規則に従って、状態を更新し、記号を書き換え、ヘッドを移動
- 受理状態に達したら受理、拒否状態に達したら拒否
単一テープ機械でも同様の構成が可能。□
2.5.3 万能性の意義
万能チューリング機械の存在は、以下の重要な帰結をもたらします：
- プログラム内蔵方式：プログラム（チューリング機械）をデータとして扱える
- 計算の理論的限界：万能機械でも解けない問題の存在を示唆
- 現代のコンピュータ：本質的に万能チューリング機械の実装
2.6 計算可能性の基本定理
graph TD
subgraph "対角化論法と決定不能性"
subgraph "対角化言語の構成"
DiagonalLang["対角化言語 Ld<br/>Ld = {⟨M⟩ | M は ⟨M⟩ を受理しない}<br/>・自己参照の矛盾を利用<br/>・カントールの対角線論法"]
SelfReference["自己参照の問題<br/>機械 M が自分の記述 ⟨M⟩<br/>を入力として受け取る"]
Contradiction["矛盾の導出<br/>⟨H⟩ ∈ Ld ⟺ H は ⟨H⟩ を受理しない<br/>しかし H は Ld を認識"]
end
subgraph "停止問題の決定不能性"
HaltingProblem["停止問題 HALT<br/>{⟨M,w⟩ | M は w で停止}<br/>・最も基本的な決定不能問題<br/>・対角化論法で証明"]
Reduction["還元による証明<br/>HALT が決定可能なら<br/>ATM も決定可能になる<br/>しかし ATM は決定不能"]
Consequence["帰結<br/>・完全なデバッガは不可能<br/>・プログラム検証の限界<br/>・静的解析の限界"]
end
subgraph "Rice の定理"
RiceTheorem["Rice の定理<br/>TMの計算する関数の<br/>非自明な性質は<br/>すべて決定不能"]
Properties["決定不能な性質例<br/>・空言語の認識<br/>・有限言語の認識<br/>・特定言語の認識"]
TrivialProps["自明な性質<br/>・常に真<br/>・常に偽<br/>→ これらは決定可能"]
end
subgraph "計算可能性の階層"
ComputableLevel["計算可能レベル<br/>・0レベル: 決定可能<br/>・1レベル: 認識可能<br/>・nレベル: n-1レベルのオラクル"]
Hierarchy["算術階層<br/>・Σ₀, Π₀: 決定可能<br/>・Σ₁, Π₁: 認識可能<br/>・Σₙ, Πₙ: より複雑"]
Applications["応用<br/>・計算複雑性理論<br/>・数理論理学<br/>・集合論"]
end
end
style DiagonalLang fill:#ffebee
style HaltingProblem fill:#ffebee
style RiceTheorem fill:#fff3e0
style ComputableLevel fill:#e3f2fd
style Contradiction fill:#ffebee
2.6.1 対角化言語
定義 2.16 対角化言語 Ld を以下のように定義する： Ld = {⟨M⟩ | M は ⟨M⟩ を受理しない}
定理 2.7 Ld は認識可能でない。
証明（対角線論法）： Ld が認識可能と仮定し、それを認識する機械を H とする。 ⟨H⟩ ∈ Ld かどうかを考える：
-
⟨H⟩ ∈ Ld とすると、定義より H は ⟨H⟩ を受理しない しかし、H は Ld を認識するので、⟨H⟩ ∈ Ld なら H は ⟨H⟩ を受理する（矛盾）
-
⟨H⟩ ∉ Ld とすると、定義より H は ⟨H⟩ を受理する しかし、H は Ld を認識するので、⟨H⟩ ∉ Ld なら H は ⟨H⟩ を受理しない（矛盾）
したがって、Ld は認識可能でない。□
2.6.2 認識可能だが決定可能でない言語
定理 2.8 認識可能だが決定可能でない言語が存在する。
証明：受理言語 LATM を考える： LATM = {⟨M, w⟩ | M は w を受理する}
LATM は認識可能：万能チューリング機械 U により、⟨M, w⟩ に対して M を w でシミュレートする。M が w を受理すれば U も受理し、M が拒否または無限ループすれば U も同様に動作する。
LATM は決定可能でない：背理法で示す。LATM を決定する機械 H が存在すると仮定する。以下の機械 D を構成する：
D = “入力 ⟨M⟩ に対して：
- H を ⟨M, ⟨M⟩⟩ でシミュレートする
- H が受理したら拒否、拒否したら受理する”
すると D は Ld = {⟨M⟩ | M は ⟨M⟩ を受理しない} を認識することになる。 しかし定理2.7により Ld は認識可能でない。矛盾。□
2.7 計算の階層
2.7.1 言語クラスの包含関係
これまでに学んだ言語クラスの関係：
定理 2.9 以下の真の包含関係が成り立つ： 有限言語 ⊊ 正規言語 ⊊ 文脈自由言語 ⊊ 決定可能言語 ⊊ 認識可能言語 ⊊ すべての言語
2.7.2 計算可能関数の性質
定理 2.10（s-m-n定理）プログラムの部分適用に相当する操作が計算可能である。
形式的には、2変数の計算可能関数 f(x, y) に対して、計算可能な関数 s が存在し、 すべての x, y に対して φ_s(x)(y) = f(x, y)
ここで φᵢ は符号 i を持つチューリング機械が計算する関数。s(x)はxを引数とする関数を表す。
定理 2.11（再帰定理）すべてのチューリング機械 T に対して、機械 R が存在し、R と T(⟨R⟩) は同じ言語を認識する。
これは、自己の記述を得ることができるプログラムの存在を保証します。つまり、プログラムが自身のソースコードを読み込んだり、変更したりできる能力を意味し、プログラミングにおける再帰的構造や自己言及的なプログラムの理論的基盤を提供します。
章末問題
基礎問題
-
以下の言語を認識するチューリング機械を構成せよ： (a) {0ⁿ1ⁿ2ⁿ | n ≥ 0} (b) {ww | w ∈ {0,1}} (c) {w ∈ {0,1} | w は回文}
-
2つの2進数の和を計算するチューリング機械を設計せよ。入力形式は ⟨x⟩#⟨y⟩ とする。
-
以下の言語が決定可能であることを証明せよ： (a) ADFA = {⟨B, w⟩ | B は DFA で、B は w を受理する} (b) ECFG = {⟨G⟩ | G は文脈自由文法で、L(G) = ∅}
-
L₁ = {w w は偶数個の0を含む} と L₂ = {w w は3の倍数個の1を含む} が決定可能であることを示し、L₁ ∩ L₂ を決定するアルゴリズムを示せ。 -
非決定性チューリング機械が言語 {0ⁿ1ⁿ n ≥ 0} ∪ {0ⁿ1²ⁿ n ≥ 0} を線形時間で認識できることを示せ。
発展問題
-
多テープチューリング機械から単一テープチューリング機械への変換において、時間計算量がどのように変化するか解析せよ。
-
非決定性チューリング機械 N が時間 t(n) で動作するとき、それをシミュレートする決定性チューリング機械の時間計算量の上界を求めよ。
-
チューリング機械の停止性を判定する「近似アルゴリズム」を考える。入力の一定割合以上で正しく判定できるアルゴリズムは存在しないことを証明せよ。
探究課題
-
Church-Turingの提唱に対する批判や限界について調査し、量子計算やDNA計算などの新しい計算モデルとの関係を論ぜよ。
-
計算可能性理論の歴史的発展について調査し、ヒルベルトの第10問題やゲーデルの不完全性定理との関連を説明せよ。
実装課題
1. 簡単なチューリング機械シミュレータを実装せよ
class TuringMachine:
def __init__(self, states, alphabet, tape_alphabet,
transitions, start_state, accept_state, reject_state):
# 初期化
def step(self):
# 1ステップ実行
def run(self, input_string, max_steps=1000):
# 入力文字列に対して実行
# 受理/拒否/タイムアウトを返す
| 例として、{0ⁿ1ⁿ | n ≥ 0} を認識する機械を実装し、テストせよ。 |
2. Post対応問題のインスタンスを解く総当たりアルゴリズムを実装せよ
- 与えられたドミノのリストから、上下が一致する並べ方を探索
- 深さ制限付き探索で、解が存在する場合は発見できることを確認