決定可能性

同義語:decidability

概要

決定可能性(decidability)とは、語の集合 $L$ で表した問いのすべての場合に、必ず停止して $L$ に属するかどうかを正しく答える Turing 機械があるかどうかという性質であり、そのような機械があるとき $L$ は決定可能、ないとき決定不能であるという。$L$ が決定可能であることは、$L$ と補集合がともに半決定可能であることと同値である。計算可能な写像による還元で決定不能性は引き継がれ、対角線論法で示される停止問題の決定不能性から、Rice の定理、文字列の書き換えの到達問題や Post 対応問題の決定不能性が導かれる。一方、有限オートマトンの空性や Presburger 算術などは決定可能である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Turing機械, 帰納的可算集合

決定可能性(decidability)は、ある種類の問いのすべての場合に、有限の手順で必ず「はい」か「いいえ」を答える 1 つの機械的な方法があるかどうかを表す性質である。そのような方法がある問題を 決定可能(decidable)、ない問題を 決定不能(undecidable)という。
決定可能性は 1 つ 1 つの問いではなく、無限に多くの問いの族についての性質である。「この機械はこの入力で停止するか」の個々の問いには必ず答えがあるが、すべての機械と入力に一様に答える手順はない。この差を正確に扱うために、問題を有限の文字列の集合として表し、手順を Turing機械 で表す。
この記事では、決定可能性の定義と還元による比較を述べ、停止問題が決定不能であることを証明する。次に、停止問題からの還元で、文字列の書き換えの到達問題と Post 対応問題が決定不能であることを証明し、決定可能な問題と決定不能な問題を比べる。

定義

決定問題と Turing 機械

$\Sigma$ を有限集合(アルファベット)とし、$\Sigma$ の文字の有限列(語)の全体を $\Sigma^*$ と書く。空の語を $\varepsilon$、語 $w$ の長さを $|w|$ と書く。

決定問題

決定問題 とは、アルファベット $\Sigma$ と部分集合 $L\subseteq\Sigma^*$ の組である。$L$ に属する語を はい の場合、属さない語を いいえ の場合 という。

数・グラフ・機械・論理式などを対象とする問いは、対象を語で書き表す方法(符号化)を固定して決定問題とみなす。たとえば自然数は 2 進法で、有限グラフは頂点数と辺の一覧で書く。互いに機械的に変換できる 2 つの符号化では、次の定義の意味で決定可能かどうかは変わらない(変換の手順を判定の手順の前に付ければよい)。対象 $X$ の符号を $\langle X\rangle$ と書き、組の符号を $\langle X,Y\rangle$ と書く。
Turing 機械は次の規約で考える。$M$ は有限の状態集合 $Q$、初期状態 $q_0\in Q$、停止状態の集合 $F\subseteq Q$、空白 $\square$ を含むテープの文字の有限集合 $\Gamma\supseteq\Sigma\cup\{\square\}$($\square\notin\Sigma$)と遷移関数
$$ \delta:(Q\setminus F)\times\Gamma\to Q\times\Gamma\times\{\mathsf L,\mathsf R\} $$
をもつ。テープは両方向に無限で、入力 $w$ を書いた位置の先頭にヘッドを置き、状態 $q_0$ から始める。$\delta(q,a)=(p,a',\mathsf D)$ は「状態 $q$ で $a$ を読んだら $a'$ を書き、ヘッドを $\mathsf D$ の向きに 1 つ動かして状態 $p$ に移る」ことを表す。$\delta$ は $Q\setminus F$ の上で全域に定義されているので、$M$ が 停止する のは $F$ の状態に入ったとき、かつそのときに限る。

決定可能

$L\subseteq\Sigma^*$ とする。

  1. Turing 機械 $M$ が $L$ を 決定する とは、$F=\{q_{\mathrm{yes}},q_{\mathrm{no}}\}$ であり、$M$ がすべての入力 $w\in\Sigma^*$ で停止し、$w\in L$ なら $q_{\mathrm{yes}}$ で、$w\notin L$ なら $q_{\mathrm{no}}$ で停止することをいう。$L$ を決定する機械があるとき、$L$ は 決定可能 であるといい、ないとき 決定不能 であるという。
  2. $L$ が 半決定可能 であるとは、ある Turing 機械 $M$ について、$M$ が入力 $w$ で停止することと $w\in L$ が同値になることをいう。

決定可能な集合は 計算可能性理論 では計算可能集合・再帰的集合ともよばれ、半決定可能な集合は 帰納的可算集合 にあたる(OLT26 Definition 30.8 と Theorem 30.9、p. 455。決定可能性との関係は Theorem 30.14、p. 460)。決定可能とは、Church–Turingのテーゼ のもとで「必ず止まって正しく答える手順がある」ことを Turing 機械で言い表したものである。
定義の 1 では、手順が存在することだけを求め、その手順を具体的に書けることは求めない。たとえば有限集合 $L$ はつねに決定可能である($L$ の語を全部覚えた機械が決定する)。$L$ の中身を誰も知らなくても、この結論は変わらない。

還元

計算可能な写像による還元

$A\subseteq\Sigma^*$、$B\subseteq\Delta^*$ とする。すべての入力で停止し、入力 $w$ に対して語 $g(w)\in\Delta^*$ をテープに残す Turing 機械があるとき、写像 $g:\Sigma^*\to\Delta^*$ は 計算可能 であるという。計算可能な $g$ で
$$ w\in A\iff g(w)\in B\qquad(w\in\Sigma^*) $$
を満たすものがあるとき、$A$ は $B$ に 多対一還元可能 であるといい、$A\le_{\mathrm m}B$ と書く。

還元は決定可能性を引き戻す

$A\le_{\mathrm m}B$ とする。$B$ が決定可能なら $A$ も決定可能であり、$B$ が半決定可能なら $A$ も半決定可能である。対偶をとると、$A$ が決定不能なら $B$ も決定不能である。

還元の後に判定する
証明を開く

$g$ を還元とし、$g$ を計算する機械を $M_g$、$B$ を決定する機械を $M_B$ とする。入力 $w$ に対して、$M_g$ を動かしてテープに $g(w)$ を作り、ヘッドをその先頭に戻してから $M_B$ を動かす機械 $M_A$ を作る($M_g$ の停止状態を $M_B$ の初期状態へつなぐ)。$M_g$ は必ず停止するので、$M_A$ は $M_B$ と同じく必ず停止し、$q_{\mathrm{yes}}$ で停止するのは $g(w)\in B$、すなわち $w\in A$ のときに限る。半決定可能の場合も同じ合成で、$M_A$ が停止することと $g(w)\in B$ が同値になる。$\square$

lem-dec-reduction により、決定不能であることがわかった 1 つの問題から、還元をたどって次々に決定不能な問題が得られる。一般論は 多対一還元 にある。

決定可能と半決定可能

$L\subseteq\Sigma^*$ が決定可能であることと、$L$ と補集合 $\Sigma^*\setminus L$ がともに半決定可能であることは同値である。決定可能な集合の補集合・和集合・共通部分は決定可能である。

2 つの機械を交互に動かす
証明を開く

$L$ を決定する機械 $M$ から、$q_{\mathrm{no}}$ に入ったら止まらずに同じ動きを繰り返す状態へ移る機械を作れば、停止することが $w\in L$ と同値になる。$q_{\mathrm{yes}}$ と $q_{\mathrm{no}}$ の役を入れ替えれば補集合についても同じで、補集合は決定可能であり、とくに $L$ と補集合は半決定可能である。

逆に、$L$ を半決定する機械 $M_1$ と補集合を半決定する機械 $M_2$ があるとする。入力 $w$ に対して、$M_1$ と $M_2$ を 1 歩ずつ交互に動かす機械を作る(テープを 2 本に分けて使う)。$w$ は $L$ か補集合のどちらかに属するので、どちらかの機械はいつか停止する。$M_1$ が先に停止したら $q_{\mathrm{yes}}$、$M_2$ が先なら $q_{\mathrm{no}}$ に移る。両方が同時に停止することはない。この機械は $L$ を決定する。

和集合と共通部分は、$L_1$ と $L_2$ を決定する機械を順に動かして答えを組み合わせればよい。$\square$

停止問題の決定不能性

Turing 機械 $M$ を語 $\langle M\rangle$ に符号化し、
$$ H=\{\langle M,w\rangle : M \text{ は入力 } w \text{ で停止する}\} $$
とおく。$H$ が決定可能かどうかを問う決定問題が 停止問題 である。

停止問題の決定不能性

$H$ は半決定可能であるが、決定可能ではない。したがって、補集合 $\{\langle M,w\rangle : M \text{ は } w \text{ で停止しない}\}$ は半決定可能でない。

自分自身についての問い

半決定可能であること。 入力 $\langle M,w\rangle$ を読み、$M$ の遷移表に従って $M$ の動きを 1 歩ずつ再現する機械 $U$ がある(万能Turing機械)。$U$ は、再現した $M$ が停止状態に入ったときに限り停止するように作る。すると $U$ が $\langle M,w\rangle$ で停止することと $\langle M,w\rangle\in H$ は同値である。
決定可能でないこと。 $H$ を決定する機械 $D$ があったとして矛盾を導く。次の機械 $N$ を作る。

  1. 入力 $x$ を受け取り、テープの $x$ の後に区切りと $x$ の写しを書いて、$\langle x,x\rangle$ を作る。
  2. $D$ を $\langle x,x\rangle$ の上で動かす($D$ は必ず停止する)。
  3. $D$ が $q_{\mathrm{yes}}$ で停止したら、止まらずに同じ動きを繰り返す。$q_{\mathrm{no}}$ で停止したら、停止する。
    $x=\langle M\rangle$ のとき、$N$ が入力 $\langle M\rangle$ で停止するのは、$D$ が $\langle M,\langle M\rangle\rangle$ で $q_{\mathrm{no}}$ を出すとき、すなわち $M$ が入力 $\langle M\rangle$ で停止しないときに限る。$M$ として $N$ 自身をとると、
    $N$ は入力 $\langle N\rangle$ で停止する $\iff$ $N$ は入力 $\langle N\rangle$ で停止しない
    となり、矛盾する。よって $D$ は存在しない。

補集合について。 補集合が半決定可能なら、$H$ は半決定可能でもあるので prop-dec-complement により決定可能になり、いま示したことに反する。$\square$

同じ主張と証明は OLT26 Theorem 32.8(p. 502)にあり、計算可能関数の言葉では Theorem 30.6(p. 452)にある。
停止問題からの還元で得られる最も一般的な結論が、Rice の定理である。Turing 機械 $M$ について、$M$ が停止する入力 $w$ に $M$ の停止後のテープの語を対応させる部分関数を $\varphi_M$ と書く。

計算する関数の性質の決定不能性

$\mathcal C$ を、ある Turing 機械の $\varphi_M$ として表せる部分関数の集合とし、$\mathcal C$ は空でなく、そのような部分関数の全体でもないとする。このとき $\{\langle M\rangle:\varphi_M\in\mathcal C\}$ は決定不能である。

停止問題を埋め込む
証明を開く

どこでも定義されない部分関数を $\emptyset$ と書く。$\emptyset\notin\mathcal C$ の場合を示せば十分である($\emptyset\in\mathcal C$ なら、補集合 $\mathcal C'$ について示し、prop-dec-complement で補集合へ移す。機械の符号である語の全体は決定可能なので、補集合と共通部分をとれば $\{\langle M\rangle:\varphi_M\in\mathcal C'\}$ に戻る)。$\mathcal C$ は空でないので、$\varphi_{M_1}\in\mathcal C$ となる $M_1$ がとれる。

入力 $\langle M,w\rangle$ から、次の機械 $M'$ の符号を作る:「入力 $z$ を脇に置き、$M$ を $w$ の上で動かす。それが停止したら、$z$ を戻して $M_1$ を $z$ の上で動かす。」$\langle M,w\rangle$ から $\langle M'\rangle$ を作る写像は計算可能である。$M$ が $w$ で停止するなら $\varphi_{M'}=\varphi_{M_1}\in\mathcal C$、停止しないなら $\varphi_{M'}=\emptyset\notin\mathcal C$ である。よって $H\le_{\mathrm m}\{\langle M\rangle:\varphi_M\in\mathcal C\}$ で、lem-dec-reduction と thm-dec-halting から右辺は決定不能である。$\square$

OLT26 Theorem 30.23(p. 465)は計算可能関数の番号で同じ主張を述べる。証明の詳しい形と、半決定可能性についての Rice–Shapiro の定理は Riceの定理 にある。Rice の定理は、機械の 振る舞い(計算する部分関数)だけで決まる性質は、自明なものを除いてどれも決定不能だと言っている。たとえば「全域で定義されるか」「定数関数か」「値に $17$ をとるか」はどれも決定不能である(OLT26 Corollary 30.24、p. 467)。

書き換えの到達問題

機械の言葉を離れた問題でも、停止問題を埋め込めば決定不能性がわかる。最も直接の例が、文字列の書き換えである。

書き換え規則の系

アルファベット $\Sigma$ 上の 書き換え規則の系(semi-Thue 系)とは、空でない語の組 $u\to v$($u,v\in\Sigma^*\setminus\{\varepsilon\}$)の有限集合 $\mathcal R$ である。語 $x,y$ について、$x=pu q$、$y=pvq$($p,q\in\Sigma^*$、$u\to v\in\mathcal R$)と書けるとき $x\Rightarrow y$ と書き、$\Rightarrow$ を $0$ 回以上つないだ関係を $\Rightarrow^*$ と書く。到達問題 とは、$\mathcal R$ と $x,y$ が与えられたとき $x\Rightarrow^*y$ かどうかを問う決定問題である。

書き換えの到達問題の決定不能性

到達問題は決定不能である。すなわち、入力 $\langle\mathcal R,x,y\rangle$ に対して $x\Rightarrow^*_{\mathcal R}y$ かどうかを決定する Turing 機械は存在しない。

機械の様子を語で書く

$H\le_{\mathrm m}(\text{到達問題})$ を示せば、lem-dec-reduction と thm-dec-halting から結論が出る。
様子の語。 Turing 機械 $M$ に対して、新しい文字 $\triangleright,\triangleleft,h$ をとり、$\Sigma_M=\Gamma\cup Q\cup\{\triangleright,\triangleleft,h\}$(互いに交わらない和)とおく。$u,v\in\Gamma^*$、$q\in Q$ について、語 $\triangleright u\,q\,v\triangleleft$ は「テープの空白でない部分が $uv$ の中にあり、状態が $q$ で、ヘッドが $v$ の最初の文字($v=\varepsilon$ なら $v$ の右隣の空白)を読んでいる」という様子を表す。これを 様子の語 という。
規則。 $q\in Q\setminus F$ と $a\in\Gamma$ について $\delta(q,a)=(p,a',\mathsf D)$ とし、次の規則を $\mathcal R_M$ に入れる。

$\mathsf D$規則$a=\square$ のとき追加する規則
$\mathsf R$$qa\to a'p$$q\triangleleft\to a'p\triangleleft$
$\mathsf L$$cqa\to pca'$(各 $c\in\Gamma$)と $\triangleright qa\to\triangleright p\square a'$$cq\triangleleft\to pca'\triangleleft$(各 $c\in\Gamma$)と $\triangleright q\triangleleft\to\triangleright p\square a'\triangleleft$

さらに、$f\in F$ について $f\to h$ を、$a\in\Gamma$ について $ha\to h$ と $ah\to h$ を入れる。左辺も右辺も空でない。
1 歩の対応。 $q\notin F$ の様子の語 $X=\triangleright uqv\triangleleft$ を考える。すべての規則の左辺は $Q\cup\{h\}$ の文字をちょうど 1 つ含み、$X$ の $Q\cup\{h\}$ の文字は $q$ だけなので、規則は $q$ を含む部分にしか当たらない。$q$ の右隣の文字を $a$(右隣が $\triangleleft$ なら $a=\square$)とすると、当たりうる規則は $\delta(q,a)$ から作ったものだけで、その中で左辺が $X$ に現れるのは、右隣が文字か $\triangleleft$ か、左隣が文字 $c$ か $\triangleright$ かで決まるちょうど 1 つである。書き換えた結果は、$M$ が 1 歩動いた後の様子の語である(左端で左へ動くときは空白を 1 つ書き足す)。
同値性。 $x=\triangleright q_0w\triangleleft$、$y=\triangleright h\triangleleft$ とおく。

  • $M$ が $w$ で停止するなら、$x$ から 1 歩ずつ書き換えて停止状態 $f$ の様子の語 $\triangleright ufv\triangleleft$ に着き、$f\to h$ と $ha\to h$、$ah\to h$ を繰り返して $y$ に着く。
  • $M$ が $w$ で停止しないなら、上の 1 歩の対応から、$x$ から書き換えて得られる語は、$M$ の計算に現れる $F$ に属さない状態の様子の語だけである(帰納法:各段の語に当たる規則は 1 つだけで、次の様子の語に移る)。これらは文字 $h$ を含まないので、$y$ に着かない。
    よって $\langle M,w\rangle\in H\iff x\Rightarrow^*_{\mathcal R_M}y$ である。$\langle M,w\rangle$ から $\langle\mathcal R_M,x,y\rangle$ を作る写像は、遷移表を読んで有限個の規則を書き出すだけなので計算可能である。$\square$

$M$ を 万能Turing機械 にとると、規則の系 $\mathcal R_M$ は 1 つに固定したまま、到達問題が決定不能になる($\langle M',w\rangle$ を $U$ に与える入力を $x$ の側に書けばよい)。
規則を逆向きにも使ってよいとした関係(Thue 系、つまり有限表示の半群の語の問題)では、上の証明の「1 歩の対応」は成り立たない。逆向きの書き換えで計算をさかのぼると、別の計算の枝に移れるからである。それでも半群の語の問題は決定不能であり、Markov と Post が 1947 年に示した(BS12 Recent Developments and Open Problems §3 (c)、p. 252。この記事では証明しない)。群についての類似が 語の問題(群論) である。

Post 対応問題

Post 対応問題

Post 対応問題(PCP)の入力は、アルファベット $\Sigma$ 上の空でない語の組の有限列 $(\alpha_1,\beta_1),\dots,(\alpha_m,\beta_m)$ である。添字の空でない列 $i_1,\dots,i_k$ で
$$ \alpha_{i_1}\alpha_{i_2}\cdots\alpha_{i_k}=\beta_{i_1}\beta_{i_2}\cdots\beta_{i_k} $$
となるもの(解)があるかどうかを問う。同じ添字は何度使ってもよい。解の最初の添字を $i_1=1$ に限ったものを 修正 Post 対応問題(MPCP)という。

組 $(\alpha_i,\beta_i)$ を、上に $\alpha_i$、下に $\beta_i$ を書いた札と思うと、札を並べて上の段と下の段の語を一致させる遊びになる。

Post 対応問題の決定不能性

Post 対応問題は決定不能である。

到達問題を札の列に写す

2 段に分ける。到達問題(thm-dec-semithue)$\le_{\mathrm m}$ MPCP $\le_{\mathrm m}$ PCP を示せば、lem-dec-reduction から結論が出る。
段 1:到達問題から MPCP へ。 $\Sigma$ 上の規則の系 $\mathcal R$ と空でない語 $x,y$ をとる(prf-dec-semithue で作る入力は $x,y$ が空でない)。新しい文字 $*$、$\#$ をとり、次の札を並べる(1 番目を最初に置く札とする)。

札上下
始め(1 番目)$*$$*x*$
写し($a\in\Sigma$ ごと)$a$$a$
規則($u\to v\in\mathcal R$ ごと)$u$$v$
区切り$*$$*$
終わり$y*\#$$\#$

下の段が 1 語ぶん先を進み、上の段がそれを写しながら追いかける仕組みである。
解の構成。 $x\Rightarrow^*y$ なら解がある。 $x=x_0\Rightarrow x_1\Rightarrow\cdots\Rightarrow x_n=y$ とし、$x_j=pu q$、$x_{j+1}=pvq$ とする。始めの札の後に、各 $j$ について $p$ の文字の写し、規則 $u\to v$ の札、$q$ の文字の写し、区切りを置き、最後に終わりの札を置く。上の段は $*x_0*x_1*\cdots*x_{n-1}*y*\#$、下の段は $*x_0*x_1*\cdots*x_n*\#$ で、$x_n=y$ なので一致する。
解からの復元。 解があれば $x\Rightarrow^*y$ である。 解をとる。$\#$ は終わりの札にしかなく、上下とも札の末尾に 1 つずつある。最初に終わりの札が現れる所で列を切ると、上下の語はどちらも共通の語の最初の $\#$ までの部分になるので、切った列も解である。そこで終わりの札は最後に 1 回だけとしてよい。$*$ の個数を上下で数えると、始めの札は上に 1 つ・下に 2 つ、区切りは 1 つずつ、終わりは上に 1 つ・下に 0 で、ほかの札にはない。始めの札を $r$ 回、終わりの札を $e$ 回使うと上下の差は $r-e$ なので、$e=1$ から始めの札は最初の 1 回だけである(終わりの札がない列は $e=0$ で、解にならない)。
始めと終わりの間の札を、区切りの札で $s+1$ 個の区画に分け、区画 $j$ の上の段の語を $\tau_j$、下の段の語を $\sigma_j$ とする($0\le j\le s$)。区画は写しと規則の札だけからなるので、規則の札の位置で 1 つずつ書き換えれば $\tau_j\Rightarrow^*\sigma_j$ である。上下が一致するので
$$ *\,\tau_0*\tau_1*\cdots*\tau_s\,y*\#=*x*\sigma_0*\sigma_1*\cdots*\sigma_s\# $$
となり、$*$ で区切られた部分を順に比べると $\tau_0=x$、$\tau_j=\sigma_{j-1}$($1\le j\le s-1$)、$\tau_sy=\sigma_{s-1}$、$\sigma_s=\varepsilon$ を得る($s=0$ のときは $\tau_0y=x$、$\sigma_0=\varepsilon$)。札の語は空でないので $\sigma_s=\varepsilon$ から区画 $s$ は空で、$\tau_s=\varepsilon$ である。よって
$$ x=\tau_0\Rightarrow^*\sigma_0=\tau_1\Rightarrow^*\sigma_1=\cdots\Rightarrow^*\sigma_{s-1}=y $$
であり($s=0$ なら $x=y$)、$x\Rightarrow^*y$ が成り立つ。
段 2:MPCP から PCP へ。 アルファベット $\Delta$ 上の MPCP の入力 $(\alpha_i,\beta_i)$($1\le i\le m$、語は空でない)をとる。新しい文字 $\diamond$、$\bullet$ をとり、語 $w=w_1\cdots w_r$ に対して $\overleftarrow w=\diamond w_1\diamond w_2\cdots\diamond w_r$(各文字の前に $\diamond$)、$\overrightarrow w=w_1\diamond w_2\diamond\cdots w_r\diamond$(各文字の後に $\diamond$)とおく。PCP の入力として、札
$$ (\diamond\overrightarrow{\alpha_1},\ \overleftarrow{\beta_1}),\quad(\overrightarrow{\alpha_i},\ \overleftarrow{\beta_i})\ (1\le i\le m),\quad(\bullet,\ \diamond\bullet) $$
をとる。最初の札を始め、最後の札を終わりとよぶ。
MPCP の解 $1,i_2,\dots,i_k$ があり、共通の語が $w$ なら、始め・$i_2,\dots,i_k$ の札・終わりと並べると、上下とも $\diamond\overrightarrow w\bullet=\overleftarrow w\diamond\bullet$ になる。
逆に PCP の解をとる。最初の札は始めでなければならない(ほかの札は上の段の最初が $\Delta$ の文字か $\bullet$、下の段の最初が $\diamond$ である)。$\bullet$ は終わりの札にしかないので、段 1 と同じく、終わりの札は最後に 1 回だけとしてよい。下の段は $\diamond$ が 2 つ続かない($\beta_i$ は空でない)が、始めの札が 2 回目に現れると上の段に $\diamond\diamond$ ができるので、始めの札は最初の 1 回だけである。よって解は、始め・$(\overrightarrow{\alpha_{i_j}},\overleftarrow{\beta_{i_j}})$($2\le j\le k$)・終わりの形で、$\alpha=\alpha_1\alpha_{i_2}\cdots\alpha_{i_k}$、$\beta=\beta_1\beta_{i_2}\cdots\beta_{i_k}$ について $\diamond\overrightarrow{\alpha}\bullet=\overleftarrow{\beta}\diamond\bullet$ となる。両辺から $\diamond$ と $\bullet$ を消すと $\alpha=\beta$ で、$1,i_2,\dots,i_k$ は MPCP の解である。
2 つの変換はどちらも札を書き出すだけなので計算可能である。$\square$

文字の数は 2 つまで減らせる。$\Sigma=\{a_1,\dots,a_n\}$ のとき $a_j\mapsto 01^j$ で語を $\{0,1\}^*$ に写すと、像の語は $0$ の位置で切れば元に戻るので単射であり、解の有無を変えない。一方、文字が 1 つなら決定可能である(ex-dec-unary)。

例

小さな機械の書き換え

$\Gamma=\{1,\square\}$、$Q=\{q_0,f\}$、$F=\{f\}$ で、$\delta(q_0,1)=(q_0,1,\mathsf R)$、$\delta(q_0,\square)=(f,\square,\mathsf R)$ とする。この機械は $1$ の列を右へ読み、空白に着くと停止する。prf-dec-semithue の規則は $q_01\to1q_0$、$q_0\square\to\square f$、$q_0\triangleleft\to\square f\triangleleft$ と $f\to h$、$h1\to h$、$h\square\to h$、$1h\to h$、$\square h\to h$ である。入力 $11$ では
$$ \triangleright q_011\triangleleft\Rightarrow\triangleright1q_01\triangleleft\Rightarrow\triangleright11q_0\triangleleft\Rightarrow\triangleright11\square f\triangleleft\Rightarrow\triangleright11\square h\triangleleft\Rightarrow\triangleright11h\triangleleft\Rightarrow\triangleright1h\triangleleft\Rightarrow\triangleright h\triangleleft $$
の 7 歩で $y$ に着く。

解のある Post 対応問題

$\Sigma=\{a,b\}$ で、札を $(\alpha_1,\beta_1)=(a,b)$、$(\alpha_2,\beta_2)=(a,aa)$、$(\alpha_3,\beta_3)=(abb,a)$ とする。添字の列 $3,1,1,2,2$ では上が $abb\cdot a\cdot a\cdot a\cdot a=abbaaaa$、下が $a\cdot b\cdot b\cdot aa\cdot aa=abbaaaa$ で一致する。長さ 4 以下の列($3+3^2+3^3+3^4=120$ 通り)には解がないことが、1 つずつ調べるとわかる。上の段が先に進む札 3 の 2 文字の貯金を、札 1 で $b$ に合わせて使い、下の段が先に進む札 2 で取り戻している。

文字が 1 つの Post 対応問題

$\Sigma=\{a\}$ のとき、語は長さで決まるので、解は $\sum_j(|\alpha_{i_j}|-|\beta_{i_j}|)=0$ となる空でない列である。$d_i=|\alpha_i|-|\beta_i|$ とおくと、解があるのは「ある $i$ で $d_i=0$」か「$d_i>0$ と $d_{i'}< 0$ の $i,i'$ がある」ときに限る。前者なら $i$ の 1 枚が解で、後者なら $i$ を $-d_{i'}$ 回、$i'$ を $d_i$ 回並べれば和が $0$ になる。どちらでもなければ $d_i$ はすべて同じ符号で $0$ でないので、和は $0$ にならない。この条件は有限回の比較で確かめられるので、文字が 1 つの PCP は決定可能である。たとえば $(aaa,a)$、$(a,aa)$ では $d=(2,-1)$ で、1 番目を 1 回、2 番目を 2 回並べた $aaaaa=a\cdot aa\cdot aa$ が解である。

決定可能な問題と決定不能な問題

問題結論所在
有限オートマトンが受理する語があるか決定可能状態のグラフの到達可能性で判定(有限オートマトン)
加法だけの自然数の理論の文の真偽決定可能Presburger算術
実数の順序体の 1 階の文の真偽決定可能Tarski–Seidenbergの定理
長さを増やさない規則の系の到達問題決定可能下の反例の表の 4 行目
文字が 1 つの PCP決定可能ex-dec-unary
停止問題決定不能thm-dec-halting
計算する関数の自明でない性質決定不能thm-dec-rice
1 階述語論理の文が恒真か決定不能Churchの定理(一階論理の決定不能性)、OLT26 Theorem 32.16(p. 511)
1 階の文が有限モデルをもつか決定不能Trakhtenbrotの定理、OLT26 Theorem 32.21(p. 514)
整数係数の多項式方程式が整数解をもつか決定不能MRDPの定理
環の理論・群の理論の文の真偽決定不能BS12 Theorem 5.8(p. 239)、Theorem 5.12(p. 242)
書き換えの到達問題・PCP決定不能thm-dec-semithue、thm-dec-pcp
有限表示の群の語の問題決定不能語の問題(群論)

1 階の理論が決定可能かどうかは 決定可能な理論 でまとめて扱う。

反例:仮定を外すと成り立たないこと

次の表の各行は、この記事で示した正しい主張から仮定を 1 つだけ外すと、結論が成り立たなくなる例である。

主張外す仮定例成り立たなくなること
lem-dec-reduction還元 $g$ が計算可能$H$ の特性関数 $g(w)=1$($w\in H$)、$g(w)=0$($w\notin H$)による $H\to\{1\}$$w\in H\iff g(w)\in\{1\}$ で $\{1\}$ は決定可能だが、$H$ は決定不能
prop-dec-complement補集合も半決定可能$H$$H$ は半決定可能だが決定不能
thm-dec-rice性質が計算する関数だけで決まる「状態が 10 個以下」自明でない性質だが、符号を読めば決定できる
長さを増やさない系の到達問題は決定可能すべての規則で $\lvert v\rvert\le\lvert u\rvert$prf-dec-semithue の $\mathcal R_M$($qa\to a'p$ は長さを保つが $q\triangleleft\to a'p\triangleleft$ は増やす)到達問題が決定不能
ex-dec-unary文字が 1 つ2 文字の PCP決定不能(thm-dec-pcp と 2 文字への写し)
表の確かめを開く

1 行目:$g$ は写像としては還元の条件を満たすが、$g$ を計算する機械があれば $H$ が決定可能になるので、$g$ は計算可能でない。3 行目:「状態が 10 個以下の機械がある」「ない」の両方があるので自明でないが、同じ部分関数を計算する機械でも状態の数は違いうるので、関数だけで決まる性質ではない。4 行目の決定可能性:$|v|\le|u|$ なら書き換えで長さは増えないので、$x$ から得られる語は長さ $|x|$ 以下の有限個に限られる。$x$ から到達できる語を、新しい語が出なくなるまで順に書き出せば、$y$ が含まれるかどうかが有限時間で決まる。4 行目の外した場合は thm-dec-semithue による。

補足

決定不能な問題も、制限すれば決定可能になることが多い。PCP は文字が 1 つなら決定可能で、書き換えは長さを増やさなければ決定可能である。逆に、決定可能な問題の中でも判定にかかる手間には大きな差があり、それを比べるのが 計算量理論 である。
還元で比べる考え方は、多対一還元より弱い Turing 還元(判定を何度でも問い合わせてよい比較)にも広げられ、決定不能な問題どうしの難しさの階層が 計算可能性理論 で調べられている。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する