§E18.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も模倣を続ける。

最後に§E18.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. 例 1.2の認識器RRの受理状態と拒否状態を交換した機械をRswapR_{\mathrm{swap}}とする。RswapR_{\mathrm{swap}}が受理する言語を求め、それがΣ∗∖L\Sigma^*\setminus Lと異なることを示せ。
  2. 例 1.2のLLについて、LLの認識器を同例のRR、Σ∗∖L\Sigma^*\setminus Lの認識器を同例のDDの受理状態と拒否状態を交換した機械SSとする。入力wwに対してR(w)R(w)を停止するまで模倣し、停止したら次にS(w)S(w)を模倣して、R(w)R(w)が受理すれば受理し、S(w)S(w)が受理すれば拒否する機械D′D'を考える。D′D'がLLの決定器でないことを、具体的な入力を挙げて示せ。
  3. ATM={⟨M,w⟩:M が入力 w を受理する}\mathsf{A}_{TM}=\{\langle M,w\rangle:M\text{ が入力 }w\text{ を受理する}\}とする。ATM\mathsf{A}_{TM}が認識可能であることを示せ。また、ATM\mathsf{A}_{TM}の決定器からHALTTM\mathsf{HALT}_{TM}の決定器を構成し、ATM\mathsf{A}_{TM}が決定可能でないことを示せ。
  4. K′={⟨M⟩:M は入力 ⟨M⟩ を受理しない}K'=\{\langle M\rangle:M\text{ は入力 }\langle M\rangle\text{ を受理しない}\}が認識可能でないことを、対角線論法により示せ。
解答 (演習の要点).

  1. RRは11を読むと受理し、00または空白を読むと右へ動くだけであり、拒否状態へ移る遷移をもたない。RswapR_{\mathrm{swap}}は同じ遷移をたどり、RRが受理する時点で拒否する。wwが11を含むならばRswap(w)R_{\mathrm{swap}}(w)は拒否して停止し、wwが11を含まないならば、RRと同じく右へ動き続けて停止しない。RRは拒否状態へ到達しないので、RswapR_{\mathrm{swap}}は受理状態へ到達しない。よってRswapR_{\mathrm{swap}}の受理言語は∅\varnothingである。一方Σ∗∖L\Sigma^*\setminus Lはε\varepsilonを含むので空でなく、二つの言語は異なる。

  2. 入力0000を考える。0000は11を含まないので00∉L00\notin Lであり、同例によりR(00)R(00)は右へ動き続けて停止しない。したがってD′(00)D'(00)はR(00)R(00)の模倣を終えることがなく、S(00)S(00)の模倣へ進まないので停止しない。決定器は全入力で停止しなければならないので、D′D'はLLの決定器でない。一方S(00)S(00)はD(00)D(00)と同じく高々三回の読取りで停止して受理するので、定理 1.3の証明のように二つの模倣を交互に進めれば、入力0000でも有限時間で拒否する。

  3. 入力xxを構文解析し、不正な符号なら拒否する。x=⟨M,w⟩x=\langle M,w\rangleならば定理 2.1の万能機械UUをxxで実行し、UUが受理すれば受理し、拒否すれば拒否する。U(⟨M,w⟩)U(\langle M,w\rangle)はM(w)M(w)が受理する場合に限って受理するので、この機械はATM\mathsf{A}_{TM}を認識する。

    ATM\mathsf{A}_{TM}の決定器HAH_Aが存在すると仮定する。TM の符号⟨M⟩\langle M\rangleから、遷移表で拒否状態qrejq_{\mathrm{rej}}へ移る遷移の行き先をすべて受理状態qaccq_{\mathrm{acc}}へ書き換えた機械M′M'の符号⟨M′⟩\langle M'\rangleを、遷移表の有限回の走査で計算することができる。M′(w)M'(w)はM(w)M(w)と同じ配置をたどり、M(w)M(w)が受理または拒否で停止するときに受理し、M(w)M(w)が停止しないときに停止しない。よってM(w)M(w)が停止することとM′(w)M'(w)が受理することは同値である。入力xxが不正な符号なら拒否し、x=⟨M,w⟩x=\langle M,w\rangleならば⟨M′,w⟩\langle M',w\rangleを作ってHAH_Aを実行し、その結論を出力する機械は全入力で停止し、HALTTM\mathsf{HALT}_{TM}を決定する。これは定理 4.1に反する。よってATM\mathsf{A}_{TM}は決定可能でない。

  4. K′K'を認識する TMRRが存在すると仮定し、r=⟨R⟩r=\langle R\rangleとおく。r∈K′r\in K'であることは、K′K'の定義によりRRが入力rrを受理しないことと同値である。一方、RRはK′K'を認識するので、r∈K′r\in K'であることはRRが入力rrを受理することと同値である。二つを合わせると、RRがrrを受理することとそれを受理しないことが同値になり、矛盾する。よってK′K'は認識可能でない。この議論は停止の判定を仮定せず、受理の有無だけを対角線上で反転している。

▨

参考文献

  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.機械の符号化、万能機械、および計算不能性を参考にした。

前提記事