§E15.5決定可能性と停止問題

最終更新

認識器は言語に属する入力に対して有限時間で受理するが、属さない入力では停止しないことがある。決定器は、属さない入力を含む全入力に対して有限時間で結論を返す。この停止条件の差を明確にすると、停止問題が認識可能でありながら決定可能ではないという二つの結論を区別することができる。

1 三つの言語クラス

定義 1.1. アルファベットΣ\Sigma上の言語L⊆Σ∗L\subseteq\Sigma^*について、次のように定める。

  1. LLが決定可能 (decidable) であるとは、全入力で停止し、LLの要素を受理し、それ以外を拒否する TM が存在することをいう。
  2. LLが認識可能 (recognizable) であるとは、w∈Lw\in Lの場合に限ってwwを受理する TM が存在することをいう。w∉Lw\notin Lでは拒否しても停止しなくてもよい。
  3. LLが余認識可能 (corecognizable) であるとは、Σ∗∖L\Sigma^*\setminus Lが認識可能であることをいう。

例 1.2 (決定器と停止しない認識器).Σ={0,1}\Sigma=\{0,1\}とし、L={w∈Σ∗:w は文字 1 を含む}L=\{w\in\Sigma^*:w\text{ は文字 }1\text{ を含む}\}とする。

機械DDは、ヘッドを右へ動かしながらテープを走査し、11を読んだら受理し、空白を読んだら拒否する。入力010010では、位置00の00を読んで右へ動き、位置11の11を読んで受理する。入力0000では、二つの00に続いて位置22の空白を読み、拒否する。任意の入力wwでDDは高々∣w∣+1|w|+1回の読取りで停止するため、DDはLLの決定器であり、LLは決定可能である。

機械RRは、11を読んだら受理し、00または空白を読んだ場合には書き換えずに右へ動き続けるとする。RRが受理することとw∈Lw\in Lは同値なので、RRはLLの認識器である。しかしRRは、0000のようなLLに属さない入力では右へ動き続けて停止しない。決定可能性の定義が要求するのは、全入力で停止する機械が一つ存在することであり、LLの全ての認識器が停止することではない。

さらに、DDの受理状態と拒否状態を交換した機械は、全入力で停止し、Σ∗∖L={w∈Σ∗:w は 1 を含まない}\Sigma^*\setminus L=\{w\in\Sigma^*:w\text{ は }1\text{ を含まない}\}の要素だけを受理する。したがってΣ∗∖L\Sigma^*\setminus Lは認識可能であり、LLは決定可能、認識可能、かつ余認識可能である。

決定可能性から二つの認識可能性を得る方向では、決定器の受理と拒否を交換する。逆方向では、LLとΣ∗∖L\Sigma^*\setminus Lの認識器を同時に進め、先に受理した側から所属を決定する。

定理 1.3. 言語L⊆Σ∗L\subseteq\Sigma^*が決定可能であるための必要十分条件は、LLが認識可能かつ余認識可能であることである。

証明. まずLLが決定可能であり、DDがその決定器であるとする。同じ機械DDはLLの認識器である。さらに、DDの受理状態と拒否状態を交換した機械DswapD_{\mathrm{swap}}を考える。DDは全入力で停止するため、DswapD_{\mathrm{swap}}も全入力で停止する。w∈Σ∗∖Lw\in\Sigma^*\setminus Lの場合に限ってDswapD_{\mathrm{swap}}は受理するので、DswapD_{\mathrm{swap}}はΣ∗∖L\Sigma^*\setminus Lの認識器である。したがってLLは認識可能かつ余認識可能である。

逆に、RRをLLの認識器、SSをΣ∗∖L\Sigma^*\setminus Lの認識器とする。入力wwに対して、R(w)R(w)とS(w)S(w)の配置を別々に保存し、RRを一段、SSを一段という順序で交互に模倣する機械DDを構成する。R(w)R(w)が受理した時点でDDは受理し、S(w)S(w)が受理した時点でDDは拒否する。片方が拒否状態で停止しても、もう片方の模倣を継続する。

各w∈Σ∗w\in\Sigma^*はLLとΣ∗∖L\Sigma^*\setminus Lのちょうど一方に属する。w∈Lw\in LならばR(w)R(w)が有限時間で受理し、w∈Σ∗∖Lw\in\Sigma^*\setminus LならばS(w)S(w)が有限時間で受理する。したがってDDは全入力で停止する。また、二つの認識器の定義により、DDが受理する場合はw∈Lw\in Lであり、拒否する場合はw∉Lw\notin Lである。ゆえにDDはLLの決定器である。▨

2 機械の符号化と万能機械

各 TM の状態、テープ文字、および移動方向へ非負整数の番号を付ける。有限個の遷移(q,a,q′,b,D)(q,a,q',b,D)を区切り付き二進文字列として並べれば、機械全体を有限文字列⟨M⟩\langle M\rangleに符号化することができる。区切りの整合性、状態番号の範囲、および停止状態からの遷移がないことを有限回の走査で検査することができる。さらに、全ての

(q,a)∈(Q∖{qacc,qrej})×Γ(q,a)\in (Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma

について、左辺が(q,a)(q,a)である遷移がちょうど一つ存在することを検査する。この検査により、遷移表が全域かつ一価であることが保証される。機械と入力の組も⟨M,w⟩\langle M,w\rangleとして符号化する。

定理 2.1. 符号化された決定性 TM と入力の組を受け取る TMUUで、任意の TMMMと任意の入力wwについて次を満たすものが存在する。

  1. U(⟨M,w⟩)U(\langle M,w\rangle)は、M(w)M(w)が受理する場合に限って受理する。
  2. U(⟨M,w⟩)U(\langle M,w\rangle)は、M(w)M(w)が拒否する場合に限って拒否する。
  3. U(⟨M,w⟩)U(\langle M,w\rangle)は、M(w)M(w)が停止しない場合には停止しない。

不正な符号を入力された場合、UUは拒否する。

証明. 最初に多テープ機械VVを構成する。第1テープには⟨M⟩\langle M\rangleの遷移表を保存し、第2テープにはwwから作ったMMのテープ内容を保存する。第3テープにはMMの現在状態とヘッド位置を二進表記で保存する。不正な符号は有限の構文検査で拒否する。

初期状態では、第2テープにwwとそれに続く空白を置き、第3テープにq0q_0とヘッド位置00を置く。現在状態がqaccq_{\mathrm{acc}}ならVVは受理し、qrejq_{\mathrm{rej}}なら拒否する。それ以外の場合には、第2テープ上の現在位置から走査記号aaを読み、第1テープを左端から走査して左辺が(q,a)(q,a)である唯一の遷移を探す。符号が決定性 TM の遷移表として正しいため、その遷移(q,a,q′,b,D)(q,a,q',b,D)は一意に存在する。VVは第2テープへbbを書き、DDに従って模倣ヘッドを動かし、第3テープの状態をq′q'へ更新する。以上の書込み、ヘッド移動、および状態更新によって、MMの一段の模倣が完了する。

ttに関する帰納法により、VVが模倣をtt回終えた時点の第2、第3テープは、M(w)M(w)のtt段後の配置を表す。基底は初期化から従う。帰納段階は、保存した遷移表から同じ遷移を一意に選び、同じ書込み、移動、および状態変更を行う構成から従う。したがって、MMが受理または拒否に到達する場合にはVVも同じ結論へ到達し、MMが停止状態へ到達しない場合にはVVも模倣を続ける。

最後に§E15.4 定理 2.2によってVVを単テープ決定性 TMUUへ変換する。同定理は受理、拒否、および停止を全て保存するので、UUは主張された三条件を満たす。▨

3 停止言語

定義 3.1. 停止言語 (halting language) を

HALTTM={⟨M,w⟩∈{0,1}∗:M が入力 w で有限時間に停止する}\mathsf{HALT}_{TM} =\{\langle M,w\rangle\in\{0,1\}^*:M\text{ が入力 }w\text{ で有限時間に停止する}\}

と定める。受理状態と拒否状態のどちらに到達した場合も停止に含め、不正な符号はHALTTM\mathsf{HALT}_{TM}に含めない。

命題 3.2.HALTTM\mathsf{HALT}_{TM}は認識可能である。

証明. 入力xxを有限時間で構文解析し、不正な符号なら拒否する。x=⟨M,w⟩x=\langle M,w\rangleならば、定理 2.1の万能機械によってM(w)M(w)を一段ずつ模倣する。M(w)M(w)が受理または拒否に到達した時点で受理する。M(w)M(w)が停止する場合には有限時間で受理し、停止しない場合には模倣も継続して受理しない。したがって、この機械はHALTTM\mathsf{HALT}_{TM}を認識する。▨

4 対角線論法

停止問題を決定する機械があると仮定し、その判定と反対の停止動作をする機械を構成する。その機械へ自身の符号を入力すると、停止することと停止しないことが同値になるため、仮定を棄却することができる。

定理 4.1.HALTTM\mathsf{HALT}_{TM}は決定可能ではない。

証明.HALTTM\mathsf{HALT}_{TM}の決定器HHが存在すると仮定する。HHは全ての文字列で停止し、入力が⟨M,w⟩\langle M,w\rangleという正しい符号である場合、

H(⟨M,w⟩) が受理する⟺M(w) が停止するH(\langle M,w\rangle)\text{ が受理する} \quad\Longleftrightarrow\quad M(w)\text{ が停止する}

を満たす。

HHを部品として TMDDを構成する。入力xxが TM の符号⟨M⟩\langle M\rangleでなければDDは直ちに停止する。正しい符号なら、DDはH(⟨M,x⟩)H(\langle M,x\rangle)を実行する。HHが受理した場合にはDDは永久に同じ二配置を往復して停止せず、HHが拒否した場合にはDDは受理して停止する。HHは決定器なので、DDのこの分岐は必ず有限時間で決まる。

DDも有限の遷移表をもつ TM なので、その符号d=⟨D⟩d=\langle D\rangleが存在する。DDへddを入力する。

  • H(⟨D,d⟩)H(\langle D,d\rangle)が受理するならば、HHの正しさによりD(d)D(d)は停止する。しかし、DDの構成により、HHが受理した場合のD(d)D(d)は停止しない。
  • H(⟨D,d⟩)H(\langle D,d\rangle)が拒否するならば、HHの正しさによりD(d)D(d)は停止しない。しかし、DDの構成により、HHが拒否した場合のD(d)D(d)は受理して停止する。

HHの二つの出力のどちらについても矛盾が生じる。したがって、そのような決定器HHは存在せず、HALTTM\mathsf{HALT}_{TM}は決定可能ではない。▨

決定不能性は、特定の入力について停止の証明が常に不可能であるという主張ではない。全ての⟨M,w⟩\langle M,w\rangleに対して正しく答え、しかも必ず停止する一つの TM が存在しないという主張である。

系 4.2.{0,1}∗∖HALTTM\{0,1\}^*\setminus\mathsf{HALT}_{TM}は認識可能ではない。したがって、HALTTM\mathsf{HALT}_{TM}は認識可能であるが余認識可能ではない。

証明.命題 3.2によりHALTTM\mathsf{HALT}_{TM}は認識可能である。もし{0,1}∗∖HALTTM\{0,1\}^*\setminus\mathsf{HALT}_{TM}も認識可能なら、定理 1.3によりHALTTM\mathsf{HALT}_{TM}は決定可能となる。停止言語が決定可能であるという結論は定理 4.1に反する。ゆえに{0,1}∗∖HALTTM\{0,1\}^*\setminus\mathsf{HALT}_{TM}は認識可能ではない。▨

5 演習

問題 5.1.

  1. LLの認識器RRの受理状態と拒否状態を交換するだけでは、一般にΣ∗∖L\Sigma^*\setminus Lの認識器を得られない理由を説明せよ。
  2. 定理 1.3の逆向きの証明で、R(w)R(w)を終了まで実行してからS(w)S(w)を実行する方法が正しくない理由を説明せよ。
  3. HALTTM\mathsf{HALT}_{TM}の認識器は、M(w)M(w)が拒否した場合にも入力⟨M,w⟩\langle M,w\rangleを受理する。この動作が必要である理由を定義から説明せよ。
  4. 対角線論法のDDについて、D(⟨M⟩)D(\langle M\rangle)が停止するための必要十分条件をM(⟨M⟩)M(\langle M\rangle)の停止性を用いて書け。
解答 (演習の要点).
  1. w∈Σ∗∖Lw\in\Sigma^*\setminus LでR(w)R(w)が停止しない場合、状態を交換してもその計算は停止せず、入力wwを受理しない。
  2. w∈Σ∗∖Lw\in\Sigma^*\setminus Lの場合にはR(w)R(w)が停止しない可能性があり、Σ∗∖L\Sigma^*\setminus Lを認識するS(w)S(w)の実行へ到達することができない。
  3. 停止言語は受理停止と拒否停止の両方を要素に含むためである。
  4. D(⟨M⟩)D(\langle M\rangle)が停止することとM(⟨M⟩)M(\langle M\rangle)が停止しないことが同値である。M=DM=Dと置くと矛盾が生じる。

▨

参考文献

  1. Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, Boston, 2013.決定可能性、停止問題、および対角線論法を参考にした。
  2. Hartley, Jr. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, originally published 1967.機械の符号化、万能機械、および計算不能性を参考にした。

前提記事