第2章計算理論の基礎

はじめに

「計算とは何か」という根本的な問いは、コンピュータサイエンスの中核をなす問題です。本章では、計算の数学的モデルとしてのチューリング機械を導入し、計算可能性と決定可能性の概念を学びます。これらの概念は、アルゴリズムの限界を理解し、解ける問題と解けない問題を区別する理論的基盤を提供します。

20世紀前半、数学者たちは「効果的に計算可能」とは何かを厳密に定義しようと試みました。その結果、チューリング、チャーチ、クリーネなどによって提案された様々な計算モデルが、すべて同じ計算能力を持つことが明らかになりました。この驚くべき一致は、計算可能性の本質的な特徴を捉えていることを示唆しています。

2.1 計算モデル

2.1.1 チューリング機械の直観的理解

チューリング機械（Turing machine）は、1936年にアラン・チューリングによって提案された抽象的な計算モデルです。人間が紙と鉛筆で行う計算過程を抽象化したもので、以下の要素から構成されます：

無限に長いテープ：記号を書き込める升目に分かれている
読み書きヘッド：テープ上の1つの升目を読み書きできる
有限個の内部状態：機械の「記憶」に相当
遷移規則：現在の状態とテープの記号に基づいて次の動作を決定

チューリング機械は、現在の状態とヘッドが読んでいる記号に基づいて：

新しい記号をテープに書き込む
ヘッドを左または右に移動する
新しい状態に遷移する

2.1.2 チューリング機械の形式的定義

チューリング機械の構成要素

定義 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）を指している

チューリング機械の構成

定義 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 計算可能性

計算可能性の概念と階層

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）：「直観的に計算可能な関数は、チューリング機械で計算可能な関数と一致する」

なぜ「提唱」なのか？

これは数学的定理ではなく、「計算」の本質に関する主張です。理由は以下の通りです：

「直観的計算可能」の非形式性：
- 人間が「計算できる」と感じる概念は主観的
- 厳密な数学的定義を与えることは困難
- 例：「筆算で計算できる」「アルゴリズムで表現できる」
証明不可能性：
- 形式的定義がない概念は証明できない
- 代わりに「経験的証拠」を蓄積する
- 70年以上の検証で反例が見つかっていない

提唱を支持する強力な証拠：

他の計算モデルとの等価性：
現代の計算モデルとの対応：
- プログラミング言語（C, Python, Java等）
- 量子計算機（量子チューリング機械）
- 並列計算機（並列ランダムアクセス機械）
- 神経回路（人工ニューラルネットワーク）
実用的な意義：
- 現代のコンピュータで実行可能なアルゴリズムは、すべてチューリング機械でシミュレート可能
- 逆に、チューリング機械で計算可能なものは、適切なプログラミング言語で実装可能

この提唱の計算機科学における重要性：

1. 計算の本質の統一的理解

Church-Turingの提唱は、「計算とは何か」という根本的な問いに対する答えを提供します。これにより：

計算の普遍性：どのようなコンピュータ（スーパーコンピュータから量子コンピュータまで）も、本質的にはチューリング機械と同じ計算能力を持つ
理論と実践の統一：数学的に定義された計算可能性と、プログラマーが実装できるアルゴリズムが一致する
計算モデルの等価性：ラムダ計算、再帰関数、チューリング機械などが同じ表現力を持つことの説明

2. アルゴリズムの限界の厳密化

この提唱により、「解けない問題」を厳密に定義できるようになりました：

停止問題：「このプログラムは停止するか？」→ 計算不可能
同等性問題：「この2つのプログラムは同じ結果を出すか？」→ 計算不可能
最適化問題：「このプログラムよりも高速なプログラムは存在するか？」→ 一般には計算不可能

# 停止問題の実際的な意味
def will_halt(program_code, input_value):
    """
    この関数は原理的に完全実装不可能です。
    理論的な目的でのみ使用され、停止問題の本質的な計算不可能性を示します。
    → デバッガーやIDEの限界の理論的根拠
    """
    pass

3. 計算複雑性理論の基盤

P、NP、PSPACE等の複雑性クラスは、チューリング機械の計算ステップ数やメモリ使用量による分類です：

P問題：多項式時間でチューリング機械が解ける問題
NP問題：多項式時間で非決定性チューリング機械が解ける問題
P≠NP予想：チューリング機械の決定性と非決定性の表現力の違いに関する予想

4. プログラミング言語設計への影響

チューリング完全性（Turing completeness）という概念を提供：

完全な言語：任意のチューリング機械をシミュレート可能（C、Python、Javaなど）
不完全な言語：表現力に制限がある（正規表現、HTMLなど）
設計の指針：言語に無限ループとデータ構造があれば、チューリング完全になる

# チューリング完全性の最小例
# while文 + 変数操作だけでチューリング完全
i = 0
while i >= 0:  # 無限ループの可能性
    i = some_computation(i)  # 任意の変更

5. 人工知能と機械学習への影響

計算可能AI：人間の知能が計算可能なら、機械で再現可能
学習の限界：機械学習アルゴリズムの理論的上限の理解
意識と計算：「意識は計算なのか？」という哲学的問題への示唆

6. 現代的な意義と応用

量子計算との関係：

量子コンピュータも「拡張チューリング機械」として理解可能
量子超越性（quantum supremacy）も、計算複雑性理論の枠組み内で議論

暗号学への影響：

RSA暗号の安全性 = 「素因数分解は計算困難」
量子コンピュータによる脅威 = 「Shorのアルゴリズムによる多項式時間解法」

ソフトウェア工学への影響：

静的解析の限界：「すべてのバグを自動検出することは不可能」
自動プログラム生成：「仕様から自動的にプログラムを生成することの限界」
テスト理論：「完全なテストは不可能」の理論的根拠

7. 哲学的・概念的重要性

Church-Turingの提唱は、計算機科学を単なる技術分野から、数学・哲学・認知科学と結びつく学問に昇華させました：

計算思考：問題を計算可能な形に分解する思考法
アルゴリズム的思考：手順化できるものとできないものの区別
デジタル世界の理解：コンピュータでできること・できないことの本質的理解

この提唱がなければ、現代の情報社会の理論的基盤は存在しなかったでしょう。

2.3 決定可能性

決定可能性の階層構造

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 チューリング機械の変種

チューリング機械の変種と等価性

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 万能チューリング機械

万能チューリング機械の構成と意義

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 計算可能性の基本定理

対角化論法と決定不能性

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.17 停止問題 HALT は以下の言語である： HALT = {⟨M, w⟩ | M は入力 w で停止する}

直感的理解：停止問題は「与えられたプログラムが無限ループに陥るかどうかを判定する問題」です。これは以下のような日常的な問題に対応します：

デバッガーが「プログラムが停止するか」を判定する
コンパイラが「無限ループを検出する」
静的解析ツールが「プログラムの安全性を保証する」

なぜ停止問題が解けないのか？

問題の本質は自己言及のパラドックスにあります。「この文は偽である」という論理的パラドックスと同じ構造を持っています。

定理 2.8 停止問題 HALT は決定不能である。

証明の戦略：

仮定：停止問題を解くアルゴリズムが存在すると仮定（背理法）
パラドックス構成：この仮定を使って論理的パラドックスを作る
矛盾：パラドックスから矛盾を導く

段階的証明：

ステップ1: 仮定の設定

仮定：停止問題を決定するチューリング機械 H が存在すると仮定します（背理法のため）。

H は以下のように完璧に動作するとします：

H(⟨M, w⟩) = {
    受理   if M は w で停止する
    拒否   if M は w で停止しない（無限ループ）
}

重要な性質：

H 自身は必ず停止する（決定器なので）
H はあらゆるチューリング機械 M と入力 w について正しく判定する
H は「オラクル」のような完璧な停止判定器

具体的なイメージ：

# Hが存在するなら、こんな関数が作れるはず
def perfect_halt_checker(program_code, input_data):
    # この関数は必ず有限時間で終了し、正しい答えを返す
    if program_will_halt(program_code, input_data):
        return True
    else:
        return False

ステップ2: パラドックス機械の構成

鍵となるアイデア：完璧な停止判定器 H を使って、「あまのじゃく」なプログラム D を作ります。

D は以下のように動作します：

D(⟨M⟩) = {
    無限ループ  if H(⟨M, ⟨M⟩⟩) = 受理  （M は自分自身で停止する）
    停止       if H(⟨M, ⟨M⟩⟩) = 拒否  （M は自分自身で停止しない）
}

D の行動原理：

H が「M は停止する」と言ったら → D は無限ループに入る（停止しない）
H が「M は停止しない」と言ったら → D は停止する

なぜ ⟨M, ⟨M⟩⟩ なのか？

⟨M⟩：チューリング機械 M の符号化（プログラムコード）
⟨M, ⟨M⟩⟩：「機械 M に、M 自身のコードを入力として与える」という意味
これは「自己言及」を作り出すための技法

プログラミング言語での例：

def diagonalize(program_source):
    """
    「あまのじゃく機械」D の実装
    """
    if perfect_halt_checker(program_source, program_source):
        # Hが「停止する」と判定したら、無限ループに入る
        while True:
            pass
    else:
        # Hが「停止しない」と判定したら、停止する
        return "finished"

重要な観察： D は H を内部で呼び出すため、H が存在する限り D も構成可能です。D の動作は完全に決定的で、矛盾する要素はありません。

ステップ3: 自己適用によるパラドックス

決定的瞬間：D を自分自身に適用します。つまり、D(⟨D⟩) はどうなるでしょうか？

これは「D という機械に、D 自身のコードを入力として与える」ことを意味します。

論理的分析： D(⟨D⟩) が停止するかしないかは、2つのケースのどちらか一方でなければなりません。それぞれを詳しく検討してみましょう。

Case 1: D(⟨D⟩) が停止すると仮定

前提: D(⟨D⟩) は停止する
H の判定: H(⟨D, ⟨D⟩⟩) = 受理
- なぜなら、H は完璧な停止判定器で、D が⟨D⟩で停止することを正しく判定する

D の動作: D の定義に従うと

H(⟨D, ⟨D⟩⟩) = 受理 → D(⟨D⟩) は無限ループに入る

矛盾: D(⟨D⟩) は停止すると仮定したが、実際には無限ループになる

Case 2: D(⟨D⟩) が停止しないと仮定

前提: D(⟨D⟩) は停止しない（無限ループ）
H の判定: H(⟨D, ⟨D⟩⟩) = 拒否
- H は完璧な停止判定器なので、D が⟨D⟩で停止しないことを正しく判定する

D の動作: D の定義に従うと

H(⟨D, ⟨D⟩⟩) = 拒否 → D(⟨D⟩) は停止する

矛盾: D(⟨D⟩) は停止しないと仮定したが、実際には停止する

パラドックスの本質：

# 自己言及のパラドックスを示すコード
def self_reference_paradox():
    # このプログラム自身について考える
    my_code = get_source_code(self_reference_paradox)
    
    if perfect_halt_checker(my_code, None):
        # 「停止する」と判定されたら、無限ループ
        while True: pass
    else:
        # 「停止しない」と判定されたら、停止
        return
    
    # このプログラムは停止するのか？しないのか？
    # どちらを仮定しても矛盾が生じる！

ステップ4: 結論 どちらの場合も矛盾が生じます。したがって、停止問題を決定する機械 H は存在しません。□

この証明の意義：

アルゴリズムの限界：
- 完全なデバッガは原理的に不可能
- 静的解析には本質的な限界がある
- プログラム検証の限界を明確化
対角化論法の威力：
- カントールの実数非可算性証明と同じ構造
- 自己言及による矛盾の構成
- 計算理論の基本的な証明技法
実用的な含意：
- IDEのデバッガが「完璧」でない理由
- 静的解析ツールが「保守的」な理由
- プログラム検証が「困難」な理由

具体的なプログラミング例：

# 停止問題の具体例
def halts(program, input_data):
    """
    この関数は原理的に実装不可能
    """
    # どんなに頑張っても完全な実装は不可能
    pass

def paradox_program():
    """
    パラドックスを引き起こすプログラム
    """
    if halts(paradox_program, None):
        while True:  # 無限ループ
            pass
    else:
        return  # 停止

2.6.3 認識可能だが決定可能でない言語

定理 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対応問題のインスタンスを解く総当たりアルゴリズムを実装せよ

与えられたドミノのリストから、上下が一致する並べ方を探索
深さ制限付き探索で、解が存在する場合は発見できることを確認

第2章 計算理論の基礎