§E15.6計算可能帰着

最終更新

問題AAから問題BBへの many-one 帰着は、AAの各入力をBBの一つの入力へ計算可能に変換し、所属の真偽を保つ。複数の入力が同じ一つの入力へ写ってもよいことが many-one という名の由来である。BBを解く手続きがあれば、その手続きの前に変換を置くことでAAを解くことができる。決定不能性を証明するときには、この含意の対偶を使い、既知の決定不能問題から対象問題へ帰着する。本記事の終わりでは、個別の帰着を一般化し、認識可能言語の非自明な意味的性質が全て決定不能であることを Rice の定理として証明する。

1 many-one 帰着

定義 1.1. 言語A⊆Σ∗A\subseteq\Sigma^*、B⊆Γ∗B\subseteq\Gamma^*に対し、全計算可能関数f ⁣:Σ∗→Γ∗f\colon\Sigma^*\to\Gamma^*が

任意の x∈Σ∗ についてx∈A⟺f(x)∈B\text{任意の }x\in\Sigma^*\text{ について}\qquad x\in A\quad\Longleftrightarrow\quad f(x)\in B

を満たすとする。このとき、AAはBBに many-one 帰着 (many-one reduction) するといい、A≤mBA\le_m Bと書く。関数ffを帰着関数という。

「全計算可能」という条件は、x∉Ax\notin Aの場合を含む全ての入力でf(x)f(x)の値を有限時間で得られることを要求する。入力によって変換が停止しない部分関数では、帰着先の判定器を呼び出す前に計算が止まるため、帰着にならない。

例 1.2 (偶数長の言語から奇数長の言語への帰着).Σ={0,1}\Sigma=\{0,1\}上の言語を

A={x∈Σ∗:∣x∣ は偶数},B={x∈Σ∗:∣x∣ は奇数}A=\{x\in\Sigma^*:|x|\text{ は偶数}\},\qquad B=\{x\in\Sigma^*:|x|\text{ は奇数}\}

とし、f(x)=x1f(x)=x1と定める。∣f(x)∣=∣x∣+1|f(x)|=|x|+1なので、∣x∣|x|が偶数であることと∣f(x)∣|f(x)|が奇数であることは同値であり、任意のx∈Σ∗x\in\Sigma^*についてx∈A⟺f(x)∈Bx\in A\Longleftrightarrow f(x)\in Bが成り立つ。ffは、入力の右端の直後にある最初の空白へ11を書き、ヘッドを位置00へ戻して停止する TM によって計算され、全ての入力で高々2(∣x∣+1)2(|x|+1)段で停止する。したがってffは全計算可能であり、A≤mBA\le_m Bである。

例えばx=01x=01はAAに属し、f(01)=011f(01)=011はBBに属する。x=0x=0はAAに属さず、f(0)=01f(0)=01もBBに属さない。AAもBBも長さの偶奇を数えるだけで決定することができるため、この帰着は決定不能性を導く道具にはならないが、定義の三つの要素（変換の全域性、計算可能性、および所属の同値）を有限の手順で確かめることができる。

命題 1.3.A≤mBA\le_m BかつBBが決定可能ならば、AAは決定可能である。

証明.ffをAAからBBへの帰着関数、DBD_BをBBの決定器とする。入力xxに対し、最初にf(x)f(x)を計算し、次にDB(f(x))D_B(f(x))を実行して同じ受理または拒否を返す機械DAD_Aを構成する。ffは全計算可能であり、DBD_Bは全入力で停止するため、DAD_Aも全入力で停止する。さらに、

DA(x) が受理する⟺f(x)∈B⟺x∈AD_A(x)\text{ が受理する} \Longleftrightarrow f(x)\in B \Longleftrightarrow x\in A

である。したがってDAD_AはAAの決定器である。▨

命題 1.4.A≤mBA\le_m BかつBBが認識可能ならば、AAは認識可能である。

証明.ffを帰着関数、RBR_BをBBの認識器とする。入力xxから有限時間でf(x)f(x)を計算し、RB(f(x))R_B(f(x))を模倣する機械RAR_Aを構成する。x∈Ax\in Aならばf(x)∈Bf(x)\in BなのでRBR_Bは有限時間で受理し、RAR_Aも受理する。x∉Ax\notin Aならばf(x)∉Bf(x)\notin BなのでRBR_Bは受理せず、RAR_Aも受理しない。後者の場合にRAR_Aが拒否するか停止しないかは、認識器の定義の範囲内である。ゆえにRAR_AはAAを認識する。▨

系 1.5.A≤mBA\le_m Bのとき、次の二条件が成り立つ。

  1. AAが決定可能でなければ、BBは決定可能でない。
  2. AAが認識可能でなければ、BBは認識可能でない。

証明.(1)は命題 1.3の対偶であり、(2)は命題 1.4の対偶である。▨

帰着の矢印を逆にすると、これらの結論は得られない。A≤mBA\le_m Bは、BBを決定する手続きからAAを決定する手続きを得ることができるという向きを表す。したがって、決定不能性を証明するときは、決定可能でないことが既知の問題をAAに、決定可能でないことを示したい対象をBBに置く。

2 受理言語の非空性への帰着

定義 2.1 (空性言語と非空性言語). TMMMが受理する言語をL(M)L(M)とする。正しい機械符号だけを対象として

EMPTYTM={⟨M⟩:L(M)=∅},NONEMPTYTM={⟨M⟩:L(M)≠∅}\begin{aligned} \mathsf{EMPTY}_{TM} &=\{\langle M\rangle:L(M)=\varnothing\},\\ \mathsf{NONEMPTY}_{TM} &=\{\langle M\rangle:L(M)\ne\varnothing\} \end{aligned}

と定める。これらをそれぞれ 空性言語 (emptiness language) および 非空性言語 (nonemptiness language) という。不正な符号はどちらの言語にも含めない。

停止問題の入力⟨M,w⟩\langle M,w\rangleから、入力を無視してM(w)M(w)を模倣する新しい機械NM,wN_{M,w}を作る。M(w)M(w)が停止した場合には全ての入力を受理し、停止しない場合には一つも受理しないように構成すると、停止性がL(NM,w)L(N_{M,w})の非空性へ変換される。

定理 2.2.

HALTTM≤mNONEMPTYTM\mathsf{HALT}_{TM}\le_m\mathsf{NONEMPTY}_{TM}

である。したがって、NONEMPTYTM\mathsf{NONEMPTY}_{TM}は決定可能ではない。

証明. 帰着関数ffを構成する。入力xxが正しい組符号でない場合には、どの入力も拒否する固定 TMN∅N_\varnothingの符号を出力する。N∅N_\varnothingの入力アルファベットは{0,1}\{0,1\}とする。正しい組符号x=⟨M,w⟩x=\langle M,w\rangleの場合には、入力アルファベットを{0,1}\{0,1\}に固定した、次の動作をする TMNM,wN_{M,w}の符号を出力する。

入力y∈{0,1}∗y\in\{0,1\}^*を受け取る。yyの内容を使用せず、万能機械によってM(w)M(w)を模倣する。M(w)M(w)が受理または拒否で停止した時点で受理する。

有限文字列⟨M,w⟩\langle M,w\rangleをNM,wN_{M,w}の遷移表に埋め込み、固定された万能機械の遷移表と組み合わせる操作は、有限文字列に対する機械的な構文変換である。具体的には、万能機械の固定部分を複写し、符号⟨M,w⟩\langle M,w\rangleを書き出す有限個の初期化状態をその前に付ければよい。この変換は入力符号の長さに比例する有限回の複写で終了する。不正な符号の場合の出力も固定されている。したがって、ffは全入力で停止する全計算可能関数である。

x=⟨M,w⟩x=\langle M,w\rangleが正しい符号である場合を考える。M(w)M(w)が停止すれば、NM,wN_{M,w}は任意の入力yyでその停止を確認して受理する。したがってL(NM,w)={0,1}∗L(N_{M,w})=\{0,1\}^*であり、特に非空である。M(w)M(w)が停止しなければ、NM,wN_{M,w}は全ての入力で模倣を続け、一つも受理しない。したがってL(NM,w)=∅L(N_{M,w})=\varnothingである。不正なxxは停止言語に属さず、f(x)=⟨N∅⟩f(x)=\langle N_\varnothing\rangleも非空性言語に属さない。ゆえに全ての文字列xxについて

x∈HALTTM⟺f(x)∈NONEMPTYTMx\in\mathsf{HALT}_{TM} \quad\Longleftrightarrow\quad f(x)\in\mathsf{NONEMPTY}_{TM}

が成り立つ。

§E15.5 定理 4.1によりHALTTM\mathsf{HALT}_{TM}は決定可能ではない。上の帰着と系 1.5により、NONEMPTYTM\mathsf{NONEMPTY}_{TM}も決定可能ではない。▨

命題 2.3.NONEMPTYTM\mathsf{NONEMPTY}_{TM}は認識可能である。

証明. 入力が正しい機械符号⟨M⟩\langle M\rangleでなければ拒否する。正しい場合には、全ての文字列をs0,s1,…s_0,s_1,\ldotsと長さ優先順に並べ、段階ttでM(s0),…,M(st)M(s_0),\ldots,M(s_t)をそれぞれtt段まで模倣する。いずれかの計算が受理状態へ到達したら受理する。

L(M)≠∅L(M)\ne\varnothingならば、あるsis_iと有限段数rrが存在してM(si)M(s_i)はrr段で受理する。t≥max⁡{i,r}t\ge\max\{i,r\}の段階でその受理が発見される。L(M)=∅L(M)=\varnothingならばどの模倣も受理に到達しないため、この認識器も受理しない。したがってNONEMPTYTM\mathsf{NONEMPTY}_{TM}は認識可能である。▨

定理 2.4.EMPTYTM\mathsf{EMPTY}_{TM}は決定可能ではない。

証明.EMPTYTM\mathsf{EMPTY}_{TM}の決定器DED_Eが存在すると仮定する。NONEMPTYTM\mathsf{NONEMPTY}_{TM}の決定器DND_Nを次のように構成する。入力xxが正しい TM の符号でなければ拒否する。正しい符号ならDE(x)D_E(x)を実行し、DED_Eが受理した場合には拒否し、拒否した場合には受理する。構文検査とDED_Eはともに停止するのでDND_Nは全入力で停止し、正しい符号⟨M⟩\langle M\rangleについてL(M)≠∅L(M)\ne\varnothingの場合に限って受理する。構成した機械DND_NはNONEMPTYTM\mathsf{NONEMPTY}_{TM}の決定器であり、定理 2.2による非空性の決定不能性に反する。したがってEMPTYTM\mathsf{EMPTY}_{TM}は決定可能ではない。▨

この例では、帰着関数はM(w)M(w)を実際に実行して停止性を調べているのではない。M(w)M(w)を後で実行する機械の記述を有限時間で生成している。この「実行結果を求めること」と「実行を組み込んだプログラムを生成すること」の違いが、帰着関数の全域性を保証する。

3 Rice の定理

NONEMPTYTM\mathsf{NONEMPTY}_{TM}とEMPTYTM\mathsf{EMPTY}_{TM}の決定不能性は、どちらも機械の記述ではなく受理言語L(M)L(M)だけに関する問いである。この形の問いが個別の事情によらず決定不能になることを、一般の定理として証明する。

定義 3.1. 認識可能言語だけからなる言語のクラスP\mathcal Pを、認識可能言語の意味的性質 (semantic property) という。正しい機械符号のうち、受理言語がP\mathcal Pに属するものの全体を

LP={⟨M⟩:L(M)∈P}L_{\mathcal P}=\{\langle M\rangle:L(M)\in\mathcal P\}

と書く。不正な符号はLPL_{\mathcal P}に含めない。P\mathcal Pが非自明 (nontrivial) であるとは、P\mathcal Pに属する認識可能言語と、P\mathcal Pに属さない認識可能言語の両方が存在することをいう。

P\mathcal Pが自明である場合、LPL_{\mathcal P}は正しい符号の全体または空集合であり、どちらも有限の構文検査によって決定することができる。したがって、決定不能性の主張には非自明性の仮定が要る。

定理 3.2 (Rice の定理).P\mathcal Pを認識可能言語の非自明な意味的性質とする。このとき、LPL_{\mathcal P}は決定可能ではない。

証明. まず∅∉P\varnothing\notin\mathcal Pの場合を考える。非自明性によりL1∈PL_1\in\mathcal Pとなる認識可能言語L1L_1が存在するので、その認識器M1M_1を一つ固定する。HALTTM≤mLP\mathsf{HALT}_{TM}\le_m L_{\mathcal P}を示す帰着関数ffを構成する。

入力xxが正しい組符号でない場合には、どの入力も拒否する固定 TMN∅N_\varnothingの符号を出力する。正しい組符号x=⟨M,w⟩x=\langle M,w\rangleの場合には、M1M_1と同じ入力アルファベットをもち、次の動作をする TMNM,wN_{M,w}の符号を出力する。

入力yyを受け取り、区切り記号の右側の作業領域へ退避する。作業領域で、万能機械によってM(w)M(w)を模倣する。M(w)M(w)が受理または拒否で停止した場合には、作業領域を消去してyyを左端へ戻し、固定したM1M_1をyyの上で模倣し、M1(y)M_1(y)が受理した場合に限り受理する。

定理 2.2の証明と同じく、この符号の生成は、万能機械とM1M_1の固定した遷移表を複写し、定数文字列⟨M,w⟩\langle M,w\rangleを書き出す有限個の初期化状態を付け加える構文変換である。したがってffは全入力で停止する全計算可能関数である。

正しい符号x=⟨M,w⟩x=\langle M,w\rangleについて所属の同値を確かめる。M(w)M(w)が停止する場合には、NM,wN_{M,w}は任意の入力yyで有限時間後に模倣を終え、以後はM1(y)M_1(y)と同じ受理の判断をする。したがってL(NM,w)=L(M1)=L1∈PL(N_{M,w})=L(M_1)=L_1\in\mathcal Pであり、f(x)∈LPf(x)\in L_{\mathcal P}である。M(w)M(w)が停止しない場合には、NM,wN_{M,w}はどの入力でも模倣局面から先へ進まず、一つも受理しない。したがってL(NM,w)=∅∉PL(N_{M,w})=\varnothing\notin\mathcal Pであり、f(x)∉LPf(x)\notin L_{\mathcal P}である。不正なxxはHALTTM\mathsf{HALT}_{TM}に属さず、L(N∅)=∅∉PL(N_\varnothing)=\varnothing\notin\mathcal Pなのでf(x)=⟨N∅⟩∉LPf(x)=\langle N_\varnothing\rangle\notin L_{\mathcal P}である。ゆえに全ての文字列xxについて

x∈HALTTM⟺f(x)∈LPx\in\mathsf{HALT}_{TM} \quad\Longleftrightarrow\quad f(x)\in L_{\mathcal P}

が成り立ち、HALTTM≤mLP\mathsf{HALT}_{TM}\le_m L_{\mathcal P}である。§E15.5 定理 4.1と系 1.5により、LPL_{\mathcal P}は決定可能ではない。

次に∅∈P\varnothing\in\mathcal Pの場合を考える。認識可能言語のうちP\mathcal Pに属さないもの全体をP′\mathcal P'とする。P\mathcal Pの非自明性からP′\mathcal P'も非自明な意味的性質であり、∅∈P\varnothing\in\mathcal Pから∅∉P′\varnothing\notin\mathcal P'である。前段によりLP′L_{\mathcal P'}は決定可能ではない。ここでLPL_{\mathcal P}の決定器DDが存在すると仮定する。入力xxが正しい機械符号でなければ拒否し、正しい符号ならD(x)D(x)を実行して受理と拒否を交換する機械D′D'を構成する。構文検査とDDは全入力で停止するので、D′D'も全入力で停止する。正しい符号⟨M⟩\langle M\rangleについては、L(M)L(M)が認識可能であるため、L(M)∈P′L(M)\in\mathcal P'であることとL(M)∉PL(M)\notin\mathcal Pであることは同値である。したがってD′D'はLP′L_{\mathcal P'}の決定器になり、前段の結論に反する。ゆえにこの場合にもLPL_{\mathcal P}は決定可能ではない。▨

系 3.3.NONEMPTYTM\mathsf{NONEMPTY}_{TM}とEMPTYTM\mathsf{EMPTY}_{TM}の決定不能性（定理 2.2と定理 2.4）は、定理 3.2 (Rice の定理)の特別な場合として従う。

証明. 空でない認識可能言語の全体をP≠∅\mathcal P_{\ne\varnothing}とする。全入力を受理する TM が存在するため{0,1}∗∈P≠∅\{0,1\}^*\in\mathcal P_{\ne\varnothing}であり、どの入力も拒否する TM が存在するため∅\varnothingは認識可能かつP≠∅\mathcal P_{\ne\varnothing}に属さない。したがってP≠∅\mathcal P_{\ne\varnothing}は非自明な意味的性質であり、その定義からLP≠∅=NONEMPTYTML_{\mathcal P_{\ne\varnothing}}=\mathsf{NONEMPTY}_{TM}である。定理 3.2によりNONEMPTYTM\mathsf{NONEMPTY}_{TM}は決定可能ではない。同様に、P=∅={∅}\mathcal P_{=\varnothing}=\{\varnothing\}も非自明な意味的性質であり、LP=∅=EMPTYTML_{\mathcal P_{=\varnothing}}=\mathsf{EMPTY}_{TM}である。ゆえにEMPTYTM\mathsf{EMPTY}_{TM}も決定可能ではない。▨

定理 3.2 (Rice の定理)の証明は、定理 2.2の機械NM,wN_{M,w}の「停止を確認したら全ての入力を受理する」という動作を、「停止を確認したら固定した認識器M1M_1に従う」へ置き換えたものである。個別の帰着で用いた構成が、そのまま一般の定理の証明になる。

注意 3.4 (意味的性質と構文的性質).定理 3.2 (Rice の定理)が対象とするのは、符号⟨M⟩\langle M\rangleの所属が受理言語L(M)L(M)だけで決まる言語である。機械の記述に関する構文的性質はこの形にならない。例えば{⟨M⟩:M の状態数が 5 以下}\{\langle M\rangle:M\text{ の状態数が }5\text{ 以下}\}は、符号を構文解析して状態数を数えることで決定することができる。使用されない状態を加えても受理言語は変わらないため、同じ言語を認識する状態数66以上の機械が存在する。ゆえに、状態数が55以下であるかどうかはL(M)L(M)だけからは定まらず、この言語はどの意味的性質P\mathcal PのLPL_{\mathcal P}とも一致しない。

4 演習

問題 4.1.

  1. A≤mBA\le_m BかつAAが決定可能であるという二条件だけから、BBが決定可能であるという結論を得ることができない理由を説明せよ。
  2. 定理 2.2のNM,wN_{M,w}を「M(w)M(w)が受理した場合だけ受理する」と変更すると、どの言語からの帰着になるかを答えよ。
  3. 帰着関数ffがM(w)M(w)の停止を待ってから二種類の固定機械の一方を出力する方法では、 many-one 帰着にならない理由を説明せよ。
  4. 言語A⊆Σ∗A\subseteq\Sigma^*、B⊆Γ∗B\subseteq\Gamma^*についてA≤mBA\le_m Bならば、Σ∗∖A≤mΓ∗∖B\Sigma^*\setminus A\le_m\Gamma^*\setminus Bであることを、同じ帰着関数を用いて証明せよ。
  5. 空語を受理言語に含む認識可能言語の全体Pε={L:L は認識可能かつ ε∈L}\mathcal P_\varepsilon=\{L:L\text{ は認識可能かつ }\varepsilon\in L\}に定理 3.2を適用し、{⟨M⟩:ε∈L(M)}\{\langle M\rangle:\varepsilon\in L(M)\}が決定可能でないことを導け。
解答 (演習の要点).
  1. 保存則は帰着先BBの解法を帰着元AAへ戻すものであり、AAの解法からBBの全入力を判定する方法は与えない。
  2. M(w)M(w)の受理性を問う言語ATM={⟨M,w⟩:M が w を受理する}\mathsf{A}_{TM}=\{\langle M,w\rangle:M\text{ が }w\text{ を受理する}\}からNONEMPTYTM\mathsf{NONEMPTY}_{TM}への帰着になる。
  3. M(w)M(w)が停止しない入力でff自身も停止せず、帰着関数に必要な全域性を失う。
  4. 任意のx∈Σ∗x\in\Sigma^*についてx∈Σ∗∖A⟺x∉A⟺f(x)∉B⟺f(x)∈Γ∗∖Bx\in\Sigma^*\setminus A\Longleftrightarrow x\notin A \Longleftrightarrow f(x)\notin B\Longleftrightarrow f(x)\in\Gamma^*\setminus Bである。
  5. {0,1}∗\{0,1\}^*は空語を含む認識可能言語であり、∅\varnothingは空語を含まない認識可能言語であるから、Pε\mathcal P_\varepsilonは非自明な意味的性質である。したがってLPε={⟨M⟩:ε∈L(M)}L_{\mathcal P_\varepsilon}=\{\langle M\rangle:\varepsilon\in L(M)\}は決定可能ではない。

▨

参考文献

  1. Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, Boston, 2013.写像帰着と Turing 機械に関する決定不能問題を参考にした。
  2. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2007.決定不能性の証明と帰着の向きを参考にした。

前提記事