停止問題と決定可能性

対角線論法で停止問題 $HALT$ が決定不能（ただし帰納的可算）であることを示し、決定可能な言語と決定不能な言語の間に成り立つ・成り立たない帰着（例: $HALT \neq \leq_{p} SAT$ 、任意の決定可能な言語は $HALT$ に帰着できる）を判定できる

前提

多項式時間多対一帰着の性質（大学院数学計算理論・ラムダ計算）

この技能までの道筋（22 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
チューリング機械の動作の追跡（大学数学オートマトン・形式言語）
四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
計算量のオーダーの比較（大学数学アルゴリズムと計算量）
多項式時間多対一帰着の性質（大学院数学計算理論・ラムダ計算）

説明

停止問題 $HALT = {⟨ M, w ⟩ : チューリング機械 M は入力 w で停止する}$ は、どんなアルゴリズムでも判定しきれない言語の代表例です。この技能では、対角線論法で $HALT$ が決定不能であること、それでも「停止するものは必ず見つけられる」という意味で帰納的可算であることを示します。そのうえで、帰着 $\leq_{p}$ の性質と組み合わせて、 $HALT \neq \leq_{p} SAT$ や「決定可能な言語はすべて $HALT$ に帰着できる」など、決定可能な言語と決定不能な言語の間の帰着の成否を判定できるようになります。

なぜそうしてよいのか

言葉を定めます。言語 $L$ が決定可能とは、すべての入力で必ず停止し、 $x \in L$ なら受理・ $x \in / L$ なら拒否するチューリング機械があること。 $L$ が帰納的可算とは、 $x \in L$ のときちょうど受理する（ $x \in / L$ のときは拒否してもよいし停止しなくてもよい）チューリング機械があることです。 $HALT$ が帰納的可算なのは、 $⟨ M, w ⟩$ を受け取って $M$ の $w$ 上の動作を 1 ステップずつ模倣し、停止したら受理する機械（万能機械）を作れるからです。 $M$ が停止しないときはこの模倣も終わりませんが、帰納的可算の定義ではそれで構いません。

決定不能性は対角線論法で示します。 $HALT$ を決定する機械 $H$ があったと仮定し、次の機械 $D$ を作ります：「入力 $⟨ M ⟩$ に対し $H$ を $⟨ M, ⟨ M ⟩⟩$ 上で走らせ、『停止する』と出たら無限ループに入り、『停止しない』と出たらすぐ停止する」。 $D$ に自分自身の符号 $⟨ D ⟩$ を与えると、 $D$ が停止するのは $H$ が「 $D$ は $⟨ D ⟩$ で停止しない」と答えたとき、すなわち $D$ が停止しないときに限ります。これは矛盾なので $H$ は存在しません。機械の一覧と入力の一覧を縦横に並べた表の対角成分をことごとく裏返したものが $D$ で、 $D$ はどの行とも対角で食い違うので表に載り得ない、というのが対角線論法の正体です。

帰着の判定には、 $\leq_{p}$ の性質「 $A \leq_{p} B$ かつ $B \in P$ なら $A \in P$ 」と同じ証明をそのまま使います： $A \leq_{p} B$ （帰着関数 $f$ ）で $B$ が決定可能なら、 $f (x)$ を計算してから $B$ の決定機械を走らせれば $A$ も決定できます。同様に $B$ が帰納的可算なら $A$ も帰納的可算です。よって $HALT$ は決定可能な言語（たとえば $SAT$ ）には帰着できません。逆向きは、決定可能な $A$ の決定機械 $M_{A}$ から「 $M_{A}$ を走らせ、受理なら停止、拒否なら無限ループ」という機械 $M_{A}^{'}$ を作っておけば、 $x \mapsto ⟨ M_{A}^{'}, x ⟩$ （固定の文字列 $⟨ M_{A}^{'} ⟩$ を $x$ に付け足すだけなので多項式時間）が $A \leq_{p} HALT$ を与えます。また $HALT$ は帰納的可算ではありません：もしそうなら、 $HALT$ を受理する機械と $HALT$ を受理する機械を 1 ステップずつ交互に走らせ、どちらかが受理した時点で答えれば $HALT$ が決定できてしまうからです。

手順

主張に現れる言語を「決定可能」「帰納的可算だが決定不能（ $HALT$ など）」「帰納的可算でない（ $HALT$ など）」に分類する。 $HALT$ は決定不能・帰納的可算、 $HALT$ は帰納的可算でない
$A \leq_{p} B$ の形の主張で $B$ が決定可能なら、 $A$ も決定可能でなければならない。 $A$ が決定不能なら成り立たない（例: $HALT \neq \leq_{p} SAT$ ）
$A \leq_{p} B$ で $B$ が帰納的可算なら、 $A$ も帰納的可算でなければならない。 $A$ が帰納的可算でなければ成り立たない（例: $HALT \neq \leq_{p} HALT$ ）
$A$ が決定可能で $B = HALT$ なら、 $x \mapsto ⟨ M_{A}^{'}, x ⟩$ （ $M_{A}^{'}$ は「拒否の代わりに無限ループする」 $M_{A}$ ）で $A \leq_{p} HALT$ が成り立つ
補集合が絡むときは $A \leq_{p} B \Rightarrow A \leq_{p} B$ で向きをそろえてから、手順 2〜4 を当てはめる

例題

$HALT = {⟨ M, w ⟩ : チューリング機械 M は入力 w で停止する}$ とし、 $SAT$ は充足可能な CNF 論理式全体の言語、 $\leq_{p}$ は多項式時間多対一帰着とする。次のうち正しいものをすべて選べ。

ア　 $HALT$ は決定可能である。
イ　 $HALT$ は帰納的可算である。
ウ　 $HALT \leq_{p} SAT$ が成り立つ。
エ　 $SAT \leq_{p} HALT$ が成り立つ。
オ　 $HALT$ は帰納的可算である。

例題の解答

【手順 1】分類する。対角線論法により $HALT$ は決定不能なのでアは誤り。 $M$ の $w$ 上の動作を模倣して停止したら受理する機械があるので $HALT$ は帰納的可算で、イは正しい。 $SAT$ は、変数への真偽値の割り当て（有限個）をすべて試せば必ず停止して判定できるので決定可能。

【手順 2】ウ： $HALT \leq_{p} SAT$ なら、帰着関数を計算してから $SAT$ を判定することで $HALT$ が決定可能になり、矛盾。よってウは誤り。

【手順 4】エ： $SAT$ の決定機械を、拒否する代わりに無限ループするよう書き換えた機械 $M^{'}$ をとると、 $φ \in SAT ⟺ M^{'}$ は $φ$ で停止する $⟺ ⟨ M^{'}, φ ⟩ \in HALT$ 。写像 $φ \mapsto ⟨ M^{'}, φ ⟩$ は固定の文字列を付けるだけで多項式時間で計算できるので、エは正しい。

【手順 1 の補足】オ： $HALT$ も帰納的可算なら、 $HALT$ と $HALT$ の受理機械を交互に 1 ステップずつ走らせることで $HALT$ が決定可能になり矛盾。よってオは誤り。

以上より正しいのはイとエ。

答え:

イ, エ

よくある誤り

$SAT$ は $NP$ 完全で「難しい」問題の代表だから $HALT \leq_{p} SAT$ も成り立つとしてしまう誤り。 $SAT$ は決定可能であり、決定可能な言語に帰着できる言語は決定可能なので、正しくは $HALT \neq \leq_{p} SAT$ 。
$A \leq_{p} HALT$ を作るには $x \in A$ かどうかを多項式時間で判定して固定の 2 つの入力に振り分けなければならない、と考えて $SAT \leq_{p} HALT$ を否定してしまう誤り。判定は機械 $M^{'}$ に任せればよく、 $x \mapsto ⟨ M^{'}, x ⟩$ は多項式時間で計算できるので、正しくは任意の決定可能な $A$ について $A \leq_{p} HALT$ 。
$HALT$ が決定不能だから補集合 $HALT$ も帰納的可算だろう、あるいは $HALT$ も帰納的可算でない、としてしまう誤り。正しくは $HALT$ は帰納的可算で、 $HALT$ は帰納的可算でない（両方が帰納的可算なら $HALT$ が決定可能になる）。したがって $HALT \neq \leq_{p} HALT$ であり、補集合への移行から $HALT \neq \leq_{p} HALT$ でもある。
対角線論法で、 $D$ を「 $H$ が『停止する』と答えたら停止する」と作ってしまう誤り。それでは $D$ に $⟨ D ⟩$ を与えても矛盾が出ない。正しくは $H$ の答えを裏返し、「『停止する』なら無限ループ、『停止しない』なら停止」とする。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$Σ = {0, 1}$ とし、言語とは $Σ^{*}$ の部分集合のこととする。チューリング機械 $M$ と入力 $w \in Σ^{*}$ の組の符号化を $⟨ M, w ⟩ \in Σ^{*}$ と書き、停止問題を
$HALT = {⟨ M, w ⟩ ∣ M は入力 w に対して停止する}$
と定める（正しい符号化になっていない列は $HALT$ に属さないものとする）。 $HALT = Σ^{*} ∖ HALT$ とする。
言語 $A, B$ について、 $A \leq_{m} B$ とは、計算可能な全域関数 $f : Σ^{*} \to Σ^{*}$ で、すべての $x \in Σ^{*}$ について $x \in A ⟺ f (x) \in B$ となるものが存在することとする。また、言語 $L$ が帰納的可算であるとは、 $L$ のちょうどすべての元に対して停止して受理するチューリング機械（ $L$ に属さない入力に対しては受理しない）が存在することとする。
次のア〜カのうち、正しいものをすべて選べ。
ア　 $HALT$ は帰納的可算である。
イ　 $HALT$ は帰納的可算である。
ウ　 $HALT$ は決定可能である。
エ　任意の決定可能な言語 $A$ について $A \leq_{m} HALT$ が成り立つ。
オ　ある決定可能な言語 $A$ について $HALT \leq_{m} A$ が成り立つ。
カ　 $HALT \leq_{m} HALT$ が成り立つ。

停止問題と決定可能性

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題