第2章計算理論の基礎

章プロフィール

チューリング機械と計算可能性

読了目安 4〜5週間

難易度 ★★★☆

章構成 7節

主要トピック

計算モデル
計算可能性
決定可能性
チューリング機械の変種
万能チューリング機械
計算可能性の基本定理
計算の階層

戻り先

付録A: 記法付録C: 解答付録D: 用語付録F: 進捗

はじめに

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

学習目標

チューリング機械（TM）の形式定義（状態・アルファベット・遷移・受理）を説明できる
構成（configuration）と計算の概念、受理/拒否/停止の違いを述べられる
決定可能性・認識可能性の基本例（A_TM, HALT_TM の周辺）を説明できる
還元（多対1・チューリング還元）の考え方を要約し、簡単な例を追える
ユニバーサルTMとシミュレーションの枠組みを概説できる

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

2.1 計算モデル

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

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

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

チューリング機械は、現在の状態とヘッドが読んでいる記号に基づいて次の動作を行います。

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

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

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

定義 2.1 チューリング機械は7つ組 \(M=(Q, \Sigma, \Gamma, \delta, q_0, q_{\mathrm{accept}}, q_{\mathrm{reject}})\) である。ここで、各記号の意味は次のとおりである。

\(Q\)：状態の有限集合
\(\Sigma\)：入力アルファベット（空白記号 ␣ を含まない）
\(\Gamma\)：テープアルファベット（\(␣ \in \Gamma\) かつ \(\Sigma \subseteq \Gamma\)）
\(\delta: Q \times \Gamma \rightharpoonup Q \times \Gamma \times \{L, R\}\)：遷移関数（部分関数）
\(q_0 \in Q\)：初期状態
\(q_{\mathrm{accept}} \in Q\)：受理状態
\(q_{\mathrm{reject}} \in Q\)：拒否状態（\(q_{\mathrm{accept}} \ne q_{\mathrm{reject}}\)）

本書では、受理状態 \(q_{\mathrm{accept}}\) および拒否状態 \(q_{\mathrm{reject}}\) では \(\delta\) を未定義とし、その時点で停止（halt）すると定義します。

遷移関数 \(\delta(q, a) = (r, b, X)\) は（\(\delta(q, a)\) が定義されるとき）次を意味する。

状態 q で記号 a を読んだとき
状態 r に遷移し
記号 b を書き込み
ヘッドを X 方向（L：左、R：右）に移動する

本書ではヘッド移動の方向集合を {L, R} に固定し、静止動作 S は認めません（S を含む定義も文献によっては用いられますが、必要になれば S を排除する変換が可能です）。

2.1.3 チューリング機械の構成と計算

定義 2.2 チューリング機械 M の構成（configuration）は、現在の状態、テープの内容、ヘッドの位置を表す。形式的には、文字列 uqv で表現される。ここで、各記号の意味は次のとおりである。

q は現在の状態
uv はテープの内容（空白でない部分）
ヘッドは v の最初の記号を指している（v が空なら空白を指している）

例 2.1 構成 \(1011\,q_5\,0111\) は次のとおりである。

現在の状態：\(q_5\)
テープの内容：10110111…
ヘッドの位置：5番目の記号（0）を指している

チューリング機械の構成

定義 2.3 構成 \(C_1\) が構成 \(C_2\) に1ステップで遷移することを \(C_1 \vdash C_2\) と表記する。

遷移規則：δ(q, a) = (r, b, X) のとき、状態 q でヘッドが記号 a を読むと、次のように動作する。

記号 a を b に書き換える
状態を r に変更する
ヘッドを X 方向（L：左、R：右）に移動する

構成の遷移は状況に応じて以下のようになる（u, v は空文字 ε を含み得る）。

左移動
- u が空でないとき：ucqav ⊢ urcbv
  （c は u の最後の記号。a を b に書き換え、ヘッドを左へ1つ移動して c を指す）
- u = ε のとき：qav ⊢ r␣bv
  （左端からさらに左へ移動する場合、未使用領域の空白 ␣ を指す）
右移動
- v が空でないとき：uqav ⊢ ubrv
  （a を b に書き換え、ヘッドを右へ1つ移動して v の先頭を指す）
- v = ε のとき：uqa ⊢ ubr␣
  （右端からさらに右へ移動し、空白 ␣ を指す）

補足（境界での挙動の例）は次のとおりである。

... u q a    ⊢    u b r ␣    ⊢    u b r c
                             （c を書込む遷移があれば ␣ を上書き）

このように、テープは必要に応じて左右に拡張される（未使用領域は ␣ で満たされる）。

定義 2.4 チューリング機械 M が入力 w を受理するとは次のとおりである。

初期構成 \(q_0w\) から始めて
受理状態 \(q_{\mathrm{accept}}\) を含む構成に到達すること

M が w を拒否するとは次のとおりである。

拒否状態 \(q_{\mathrm{reject}}\) を含む構成に到達すること

M が w で停止するとは次のとおりである。

受理または拒否すること（本書の定義では、受理状態・拒否状態では \(\delta\) が未定義なのでその時点で停止する）

2.1.4 チューリング機械の例

例 2.2 言語 L = \(\{0^{n}1^{n} \mid n \ge 0\}\) を認識するチューリング機械

この言語は、同数の0と1が順番に並んだ文字列の集合です。

アルゴリズムの概要

最左端の0を見つけてxに置き換える
右に移動して対応する1を見つけてyに置き換える
左に戻って次の0を探す
すべての0と1が対応したら受理、そうでなければ拒否

形式的な記述 \(M = (Q, \Sigma, \Gamma, \delta, q_1, q_{\mathrm{accept}}, q_{\mathrm{reject}})\)。ここで：

\(Q = \{q_1, q_2, q_3, q_4, q_5, q_{\mathrm{accept}}, q_{\mathrm{reject}}\}\)
\(\Sigma = \{0, 1\}\)
\(\Gamma = \{0, 1, x, y, ␣\}\)

遷移関数 \(\delta\) は次のとおりである。

（以下のコード風表記では、\(q_{\mathrm{accept}}\) と \(q_{\mathrm{reject}}\) をそれぞれ q_accept, q_reject と略記する。）

δ(q_1, 0) = (q_2, x, R)  // 0をxに変えて右へ
δ(q_1, y) = (q_1, y, R)  // yをスキップ
δ(q_1, ␣) = (q_accept, ␣, R)  // すべて処理済みなら受理

δ(q_2, 0) = (q_2, 0, R)  // 0をスキップ
δ(q_2, y) = (q_2, y, R)  // yをスキップ
δ(q_2, 1) = (q_3, y, L)  // 1をyに変えて左へ

δ(q_3, 0) = (q_3, 0, L)  // 0をスキップして左へ
δ(q_3, y) = (q_3, y, L)  // yをスキップして左へ
δ(q_3, x) = (q_1, x, R)  // xに到達したら右へ

// エラー処理
δ(q_1, 1) = (q_reject, 1, R)
δ(q_2, ␣) = (q_reject, ␣, R)

計算例：入力 \(0011\) に対する計算過程 \[ \begin{aligned} q_10011 &\vdash xq_2011 \vdash x0q_211 \vdash x0yq_31 \vdash xq_30y1 \vdash q_3x0y1 \vdash xq_10y1 \\{} &\vdash xxq_2y1 \vdash xxyq_21 \vdash xxyyq_3 \vdash xxyq_3y \vdash xxq_3yy \vdash xq_3xyy \\{} &\vdash xxq_1yy \vdash xxyq_1y \vdash xxyyq_1 \vdash xxyy␣q_{\mathrm{accept}} \end{aligned} \]

2.2 計算可能性

計算可能性の概念と階層

2.2.1 チューリング計算可能関数

定義 2.5 関数 \(f: \Sigma^{\ast} \to \Sigma^{\ast}\) がチューリング計算可能（Turing computable）であるとは、以下を満たすチューリング機械 M が存在することである。

すべての \(w \in \Sigma^{\ast}\) に対して
M を入力 w で開始すると
M は停止し、テープ上に f(w) のみが残る

例 2.3 文字列を逆順にする関数 \(\mathrm{rev}: \{0,1\}^{\ast} \to \{0,1\}^{\ast}\) はチューリング計算可能である。

証明の概要：以下のアルゴリズムを実装するチューリング機械を構成できる。

入力の最後の文字を記憶
その文字を消去
テープの右端に移動してその文字を書く
元の位置に戻って繰り返す

2.2.2 部分関数と計算可能性

実際の計算では、すべての入力に対して定義されない関数（部分関数）も重要です。

定義 2.6 部分関数 \(f: \Sigma^{\ast} \rightharpoonup \Sigma^{\ast}\) がチューリング計算可能であるとは、以下を満たすチューリング機械 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 アルファベット \(\Sigma\) 上の言語（language）は、\(\Sigma^{\ast}\) の部分集合である。

計算理論では、問題を言語として形式化します。

問題のインスタンス → 文字列
“Yes”のインスタンス → 言語の要素
“No”のインスタンス → 言語に含まれない文字列

例 2.4

PRIME = \(\{n \mid n \text{ は2進表記された素数}\}\)
CONNECTED = \(\{\langle G\rangle \mid G \text{ は連結グラフ}\}\)

2.3.2 決定可能言語

定義 2.8 言語 L が決定可能（decidable）または再帰的（recursive）であるとは、L を決定するチューリング機械が存在することである。すなわち、ある機械 M が存在し、次の条件を満たす。

w ∈ L ならば M は w を受理する
w ∉ L ならば M は w を拒否する
M はすべての入力で停止する

決定可能言語の例は次のとおりである。

有限言語：すべての有限言語は決定可能
正規言語：DFAで認識される言語
文脈自由言語：CFGで生成される言語

定理 2.1 決定可能言語は以下の演算に関して閉じている。

和集合：\(L_1, L_2\) が決定可能 → \(L_1 \cup L_2\) も決定可能
共通部分（intersection）：\(L_1, L_2\) が決定可能 → \(L_1 \cap L_2\) も決定可能
補集合：L が決定可能 → \(\overline{L}\) も決定可能
連結：\(L_1, L_2\) が決定可能 → \(L_1L_2\) も決定可能
クリーネ閉包：L が決定可能 → \(L^{\ast}\) も決定可能

証明（和集合の場合）。 \(L_1\) を決定する機械を \(M_1\)、\(L_2\) を決定する機械を \(M_2\) とする。 \(L_1 \cup L_2\) を決定する機械 M を以下のように構成する。

M = “入力 w に対して：

\(M_1\) を w でシミュレートする
\(M_1\) が受理したら、受理する
\(M_1\) が拒否したら、\(M_2\) を w でシミュレートする
\(M_2\) が受理したら受理、拒否したら拒否する”

\(M_1\), \(M_2\) は必ず停止するので、M も必ず停止する。□

2.3.3 認識可能言語

定義 2.9 言語 L が認識可能（recognizable）または再帰的可算（recursively enumerable）であるとは、L を認識するチューリング機械が存在することである。すなわち、ある機械 M が存在し、次の条件を満たす。

w ∈ L ならば M は w を受理する
w ∉ L ならば M は w を拒否するか、永遠に動作し続ける

定理 2.2 L が決定可能 ⟺ L と \(\overline{L}\) の両方が認識可能

証明（⇒）：L が決定可能なら、定義より L は認識可能。 L を決定する機械の受理と拒否を入れ替えれば \(\overline{L}\) を決定する機械が得られるので、\(\overline{L}\) も認識可能。

（⇐）：L を認識する機械を \(M_1\)、\(\overline{L}\) を認識する機械を \(M_2\) とする。以下の機械 M は L を決定する。

M = “入力 w に対して：

\(M_1\) と \(M_2\) を並行してシミュレートする
\(M_1\) が受理したら、受理する
\(M_2\) が受理したら、拒否する”

w ∈ L または w ∈ \(\overline{L}\) のいずれかが成り立つので、M は必ず停止する。□

2.4 チューリング機械の変種

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

2.4.1 多テープチューリング機械

定義 2.10 k-テープチューリング機械は、k 本の独立したテープを持ち、各テープに独立した読み書きヘッドを持つ。

遷移関数：\(\delta: Q \times \Gamma^{k} \rightharpoonup Q \times \Gamma^{k} \times \{L, R\}^{k}\)

定理 2.3 多テープチューリング機械は、単一テープチューリング機械と同じ計算能力を持つ。

証明の概要：k-テープ機械 M を単一テープ機械 S でシミュレートする。 S のテープを k 個の領域に分け、各領域が M の各テープを表現する。ヘッドの位置は特殊な記号でマークする。

例：3テープ機械の構成

テープ1: a b c
         ↑
テープ2: x y z
           ↑
テープ3: 1 2 3
         ↑

これを単一テープで表現する。

# [a] b c#x [y] z#[1] 2 3#

（[ ] はヘッドが指すセルを示す）

M の1ステップをシミュレートするには、単一テープ上で各領域を走査してヘッド位置を特定し、更新後にマークを付け直す必要がある。したがって「計算可能性（受理する/しない）の同値」と「時間計算量のオーバーヘッド」は区別して扱う。計算量の観点では、t(n) ステップの k-テープ計算は単一テープで概ね \(O(t(n)^2)\) 時間でシミュレートできる（十分大きな n で t(n) ≥ n を仮定）。 □

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のすべてのパスを探索
以下同様

受理構成が見つかれば受理する。受理構成が存在しない場合の停止性は N の前提に依存する（下記注参照）。□ （注）N が認識器（recognizer）の場合、受理パスが存在しないときに非停止パスがあり得るため、D は停止しないことがある。「拒否で必ず停止」まで主張するには、N が全計算パスで停止する decider であることが前提となる。

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, \Sigma, \Gamma, \delta, q_0, q_{\mathrm{accept}}, q_{\mathrm{reject}})\) の符号化 \(\langle M\rangle\) は、M の構造を一意に表現する文字列である。

符号化の例は次のとおりである。

状態を \(q_1, q_2, \ldots, q_n\) と番号付け
記号を \(a_1, a_2, \ldots, a_m\) と番号付け
遷移 \(\delta(q_i, a_j) = (q_k, a_l, D)\) を \(\langle i, j, k, l, D\rangle\) として符号化

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 = \(\{\langle M\rangle \mid M \text{ は } \langle M\rangle \text{ を受理しない}\}\)

定理 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 = \(\{\langle M,w\rangle \mid M \text{ は入力 } w \text{ で停止する}\}\)

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

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

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

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

定理 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.9 認識可能だが決定可能でない言語が存在する。

証明：受理言語 LATM を考える。 LATM = \(\{\langle M,w\rangle \mid M \text{ は } w \text{ を受理する}\}\)

LATM は認識可能：万能チューリング機械 U により、⟨M, w⟩ に対して M を w でシミュレートする。M が w を受理すれば U も受理し、M が拒否または無限ループすれば U も同様に動作する。

LATM は決定可能でない：背理法で示す。LATM を決定する機械 H が存在すると仮定する。以下の機械 D を構成する。

D = “入力 ⟨M⟩ に対して：

H を ⟨M, ⟨M⟩⟩ でシミュレートする
H が受理したら拒否、拒否したら受理する”

すると D は Ld = \(\{\langle M\rangle \mid M \text{ は } \langle M\rangle \text{ を受理しない}\}\) を認識することになる。しかし定理2.7により Ld は認識可能でない。矛盾。□

2.7 計算の階層

2.7.1 言語クラスの包含関係

これまでに学んだ言語クラスの関係。

定理 2.10 以下の真の包含関係が成り立つ。

有限言語 ⊂ 正規言語 ⊂ 文脈自由言語 ⊂ 決定可能言語 ⊂ 認識可能言語 ⊂ すべての言語

2.7.2 計算可能関数の性質

定理 2.11（s-m-n定理）プログラムの部分適用に相当する操作が計算可能である。

形式的には、2変数の計算可能関数 f(x, y) に対して、計算可能な関数 s が存在し、すべての x, y に対して \(\varphi_{s(x)}(y) = f(x, y)\)

ここで \(\varphi_i\) は符号 i を持つチューリング機械が計算する（部分）関数であり、s は x を与えると「y ↦ f(x, y)」を計算する機械の符号を返す。

定理 2.12（再帰定理）すべてのチューリング機械 T に対して、機械 R が存在し、R と \(T(\langle R\rangle)\) は同じ言語を認識する。

これは、自己の記述を得ることができるプログラムの存在を保証します。つまり、プログラムが自身のソースコードを読み込んだり、変更したりできる能力を意味し、プログラミングにおける再帰的構造や自己言及的なプログラムの理論的基盤を提供します。

まとめ

TM は計算の標準モデルであり、受理・決定・認識の区別が重要
還元は問題の難しさ比較の基本手法で、計算可能性・複雑性の両領域で中核
多テープ/非決定性などの拡張は計算力を保ちつつ効率性のみ変える場合がある

次章への橋渡し

第2章では計算一般の標準モデルを手に入れました。次章ではその視点を有限オートマトンやプッシュダウンオートマトンのような制約付きモデルへ下ろし、どの言語がどの機械で扱えるかを階層として整理します。

補助資料を併用するなら、理論の使われ方は付録E の第2章節、理解確認は付録F の第2章節を参照してください。

参考文献と次の一歩

図版の再参照: 本章の図をまとめて見返したいときは付録H: 図版ガイドと図一覧を参照してください。
標準: Michael Sipser, 『Introduction to the Theory of Computation』. チューリング機械、決定可能性、万能計算機の導入を一冊で追える定番教科書です。
原典: Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”. 計算可能性の標準モデルがどのような問題意識から導入されたかを確認できます。
出典メモ: 本章で扱うチューリング機械中心の記述は、Church–Turing の見方を前提にした現代的な標準整理です。歴史的背景まで確認したい場合は Turing の原論文と第4章を往復すると理解が安定します。
次の一歩: 制約付き計算モデルの違いを整理したい読者は第3章へ、計算の限界そのものを先に見たい読者は第4章へ進んでください。演習の回収には付録C（第2章）を使います。
章末問題
代表演習と詳細解答は付録C（第2章）を参照。

取り組み方ガイド

迷ったら次の表の順で進め、詰まったら「主に戻る節」にある定義・例題・注意点を先に見直してください。

区分	推奨順	主に戻る節	使い方
基礎問題	1番目	2.1〜2.3	機械モデルと判定可能性の基礎を固める
発展問題	2番目	2.4〜2.7	シミュレーションと上界評価を詰める
探究課題	3番目	2.1〜2.7	歴史的背景と拡張モデルを比較する
実装課題	4番目	2.1, 2.2, 2.4	小さな機械で仕様を試してから拡張する

基礎問題

以下の言語を認識するチューリング機械を構成せよ。 (a) \(\{0^{n}1^{n}2^{n} \mid n \ge 0\}\) (b) \(\{ ww \mid w \in \{0,1\}^{\ast} \}\) (c) \(\{ w \in \{0,1\}^{\ast} \mid w \text{ は回文} \}\)

ヒント:
- (a) カウンタやマークを用いて 0/1/2 の個数を対応付ける。複数走査またはマルチトラックで対応可能。
- (b) 真ん中の境界を非決定的に仮定して検証する設計が有効。
- (c) 先頭と末尾を照合しながら内側へ進む戦略（マーク/ヘッド往復）。
2つの2進数の和を計算するチューリング機械を設計せよ。入力形式は ⟨x⟩#⟨y⟩ とする。
以下の言語が決定可能であることを証明せよ。 (a) ADFA = \(\{\langle B,w\rangle \mid B \text{ は DFA で、} B \text{ は } w \text{ を受理する}\}\) (b) ECFG = \(\{\langle G\rangle \mid G \text{ は文脈自由文法で、} L(G) = \emptyset\}\)

ヒント: (b) 到達可能・生成可能な記号の削除で S から終端へ導出が存在するかを判定（標準アルゴリズム）。
\(L_1 = \{w \mid w \text{ は偶数個の0を含む}\}\) と \(L_2 = \{w \mid w \text{ は3の倍数個の1を含む}\}\) が決定可能であることを示し、\(L_1 \cap L_2\) を決定するアルゴリズムを示せ。
非決定性チューリング機械が言語 \(\{0^{n}1^{n} \mid n \ge 0\} \cup \{0^{n}1^{2n} \mid n \ge 0\}\) を線形時間で認識できることを示せ。

ヒント: 分岐でどちらの形かを選び、それぞれに応じた一回走査検証を設計。

発展問題

多テープチューリング機械から単一テープチューリング機械への変換において、時間計算量がどのように変化するか解析せよ。
非決定性チューリング機械 N が時間 t(n) で動作するとき、それをシミュレートする決定性チューリング機械の時間計算量の上界を求めよ。
チューリング機械の停止性を判定する「近似アルゴリズム」を考える。入力の一定割合以上で正しく判定できるアルゴリズムは存在しないことを証明せよ。

ヒント: 対角化や Rice の定理の枠組みで近似器への還元・矛盾を構成する。

探究課題

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^{n}1^{n} \mid n \ge 0\}\) を認識する機械を実装し、テストせよ。

2. Post対応問題のインスタンスを解く総当たりアルゴリズムを実装せよ

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

第2章 計算理論の基礎