Kleene–Postの定理

同義語:Kleene–Post theorem

概要

Kleene–Postの定理(Kleene–Post theorem)とは、停止問題の次数 $\mathbf 0'$ 以下に、どちらの方向にも Turing 還元できない 2 つの集合 $A,B$ があるという定理である。証明は、神託の有限の部分を順に延ばし、各段で「計算を止める延長があるか」を停止問題に問い合わせて、還元の候補を 1 つずつ打ち消す有限の延長の方法による。同じ方法で、互いに独立な次数の列、計算可能な半順序の次数への埋め込み、計算可能でない各集合と比較できない集合の存在が示される。

$$\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次数, 計算可能性理論

Kleene–Postの定理(Kleene–Post theorem)は、停止問題の次数 $\mathbf 0'$ の下に、互いに比較できない 2 つの Turing次数 があることを述べる定理である。すなわち、$\emptyset'$ を神託とすれば計算できる集合 $A,B$ で、$A$ を使っても $B$ が計算できず、$B$ を使っても $A$ が計算できないものがある。決定不能性の次数は一列に並ばない。
証明は 有限拡大法(finite extension method)による。$A$ と $B$ の特性関数を有限の 0・1 列として少しずつ延ばし、各段で「$A$ は $B$ を神託とする $e$ 番目の機械の出力と違う」という要求を 1 つずつ満たしていく。各段で必要な判断は「ある有限の延長で計算が止まるか」という問いだけで、これは $\emptyset'$ で答えられる。この方法は、比較できない次数の無限列、計算可能な半順序の次数への埋め込み、$\mathbf 0$ 以外のどの次数にもそれと比較できない次数があることへと、そのまま広がる。

結果内容
lem-kp-force有限の延長で計算の停止・不停止を決める
thm-kp-mainKleene–Post の定理:$\mathbf 0'$ の下の比較不能な 2 次数
thm-kp-independent$\mathbf 0'$ の下の独立な次数の列
cor-kp-poset計算可能な半順序は $\mathbf 0'$ の下の次数に埋め込める
thm-kp-cone$\mathbf a\ne\mathbf 0$ なら $\mathbf a$ と比較できない次数が $\mathbf a'$ の下にある

記法

記法は Turing次数 の記事に従う。$\mathbb N=\{0,1,2,\dots\}$ の部分集合をその特性関数と同一視する。$\{0,1\}$ の有限列を 文字列 とよび、長さを $|\sigma|$ と書く。$\sigma\subseteq\tau$ は $\sigma$ が $\tau$ の先頭の部分であることを、$\sigma\subset X$ は $\sigma=X\restriction|\sigma|$($X$ の最初の $|\sigma|$ 個の値)であることを表す。$\Phi_e^X$ は神託 $X$ のもとで $e$ 番目の神託機械が計算する部分関数で、$\Phi_{e,s}^\sigma(x)\!\downarrow=y$ は「神託テープに $\sigma$ を書いた状態で入力 $x$ から始め、$s$ 歩以内に、番号 $|\sigma|$ 以上のマスを読まずに停止して値 $y$ を出す」ことを表す。この関係は $(e,\sigma,x,s,y)$ について決定可能である。
Turing次数 の記事の補題「使用域の原理」により、次の 2 つが成り立つ。

  • (U1) $\Phi_{e,s}^\sigma(x)\!\downarrow=y$ で $\sigma\subset X$ なら、$\Phi_e^X(x)\!\downarrow=y$ である。
  • (U2) $\Phi_e^X(x)\!\downarrow$ なら、ある $u$ があって、$v\ge u$ を満たすすべての $v$ について、ある $s$ で $\Phi_{e,s}^{X\restriction v}(x)\!\downarrow$ となる。
    $A\oplus B:=\{2x\mid x\in A\}\cup\{2x+1\mid x\in B\}$ とし、計算可能な全単射 $\langle\cdot,\cdot\rangle\colon\mathbb N^2\to\mathbb N$ を 1 つ固定する。$A$ で計算可能枚挙な集合($A$ を神託として、属する元を見つけると止まる手順で特徴づけられる集合)は、Turing次数 の記事の定理「ジャンプの基本定理」の 2 により $A'$ に多対一還元でき、したがって $A'$ で判定できる。とくに計算可能枚挙な集合は $\emptyset'$ で判定できる。

有限の延長による強制

有限の延長で停止を決める

$e,x$ と文字列 $\tau$ をとる。

  1. ある $\tau'\supseteq\tau$ と $s$ で $\Phi_{e,s}^{\tau'}(x)\!\downarrow=y$ なら、$\tau'\subset X$ を満たすすべての $X$ について $\Phi_e^X(x)=y$ である。
  2. そのような $\tau'$ と $s$ がないなら、$\tau\subset X$ を満たすすべての $X$ について $\Phi_e^X(x)\!\uparrow$ である。
  3. 1 の場合に当たる組 $(e,x,\tau)$ の全体は計算可能枚挙で、$\emptyset'$ で判定できる。

1 は (U1) である。2:$\tau\subset X$ で $\Phi_e^X(x)\!\downarrow$ とすると、(U2) の $u$ について $v:=\max(u,|\tau|)$ とおけば、ある $s$ で $\Phi_{e,s}^{X\restriction v}(x)\!\downarrow$ である。$\tau\subset X$ と $v\ge|\tau|$ から $\tau\subseteq X\restriction v$ なので、$\tau':=X\restriction v$ が 1 の場合の仮定を満たし、矛盾する。3:$\tau'\supseteq\tau$ と $s$ の組を順に調べ、$\Phi_{e,s}^{\tau'}(x)\!\downarrow$ となるものが見つかれば止まる手順が、この集合を特徴づける。最後の主張は「記法」の節の最後の段落による。$\square$

この補題は、神託の有限の部分 $\tau$ を決めた時点で、計算 $\Phi_e^X(x)$ の運命を「止まる値に決める」か「止まらないことに決める」かのどちらかを選べることを述べている。前者を選べる場合には実際に延長 $\tau'$ が見つかり、後者は何もしなくても成り立つ。

Kleene–Post の定理

Kleene–Post の定理

$A,B\le_{\mathrm T}\emptyset'$ で、$A\not\le_{\mathrm T}B$ かつ $B\not\le_{\mathrm T}A$ となる集合 $A,B\subseteq\mathbb N$ がある。すなわち $\mathbf 0'$ の下に、互いに比較できない 2 つの次数がある。

要求を 1 つずつ満たす

満たすべき要求は、すべての $e$ について
$$ R_{2e}:\ A\ne\Phi_e^B,\qquad R_{2e+1}:\ B\ne\Phi_e^A $$
である($A\ne\Phi_e^B$ は、$\Phi_e^B$ が全域的でないか、ある $x$ で $\Phi_e^B(x)\ne A(x)$ となることを意味する)。$R_n$ がすべて成り立てば、$A\le_{\mathrm T}B$ も $B\le_{\mathrm T}A$ も成り立たない。
文字列の列 $\sigma_0\subseteq\sigma_1\subseteq\cdots$ と $\tau_0\subseteq\tau_1\subseteq\cdots$ を作り、$A,B$ をそれぞれの和($\sigma_n\subset A$、$\tau_n\subset B$ となる集合)とする。$\sigma_0,\tau_0$ は空の文字列とする。
段 $2e$($R_{2e}$ を満たす). $x:=|\sigma_{2e}|$ とおく($A(x)$ はまだ決まっていない)。lem-kp-force の 3 により、「$\tau'\supseteq\tau_{2e}$ と $s$ で $\Phi_{e,s}^{\tau'}(x)\!\downarrow$ となるものがあるか」を $\emptyset'$ で判定する。

  • ある場合:組 $(\tau',s)$ を順に調べて最初に見つかるものをとり、$y:=\Phi_{e,s}^{\tau'}(x)$ とする。$\tau_{2e+1}:=\tau'$ に $0$ を 1 つ付け加えたもの、$\sigma_{2e+1}:=\sigma_{2e}$ に $1-y$($y\notin\{0,1\}$ なら $0$)を付け加えたものとする。
  • ない場合:$\tau_{2e+1}:=\tau_{2e}$、$\sigma_{2e+1}:=\sigma_{2e}$ にそれぞれ $0$ を 1 つ付け加えたものとする。

段 $2e+1$($R_{2e+1}$ を満たす). $\sigma$ と $\tau$ の役を入れ替えて同じことを行う。
各段で 2 つの文字列はどちらも真に長くなるので、$A,B$ は $\mathbb N$ 全体で定まる。各段の操作は、$\emptyset'$ への問い合わせ 1 回と、止まることが分かっている探索だけである。よって $A(x)$ を求めるには $|\sigma_n|>x$ となるまで段を進めればよく、$A,B\le_{\mathrm T}\emptyset'$ である。
$R_{2e}$ が成り立つこと. 「ある場合」なら、$\tau'\subseteq\tau_{2e+1}\subset B$ なので lem-kp-force の 1 により $\Phi_e^B(x)=y$ であり、$A(x)=\sigma_{2e+1}(x)\ne y$ である。「ない場合」なら、$\tau_{2e}\subset B$ なので lem-kp-force の 2 により $\Phi_e^B(x)\!\uparrow$ で、$\Phi_e^B$ は全域的でない。どちらでも $A\ne\Phi_e^B$ である。$R_{2e+1}$ も同様である。$\square$

構成した $A\oplus B$ も $\emptyset'$ で計算できるので、$\deg(A)$ と $\deg(B)$ の最小上界 $\deg(A\oplus B)$(Turing次数 の記事の命題「次数の基本性質」の 4)も $\mathbf 0'$ 以下にある。一方、$A,B$ は計算可能枚挙とは限らない。計算可能枚挙な集合で同じ結論を得るのが Friedberg–Muchnikの定理 であり、そこでは $\emptyset'$ への問い合わせが使えないので、要求どうしの衝突を優先順位で整理する。

独立な次数の列と半順序の埋め込み

同じ方法で、比較できない次数を無限個、しかも互いに「独立」に作れる。集合 $C\subseteq\mathbb N$ について、その 第 $i$ 列 を $C^{[i]}:=\{x\mid\langle i,x\rangle\in C\}$、第 $i$ 列を除いた部分を $C^{[\ne i]}:=\{\langle j,x\rangle\in C\mid j\ne i\}$ と書く。$C^{[\ne i]}$ は $j\ne i$ の列 $C^{[j]}$ をすべてまとめた集合である。

独立な次数の列

$C\le_{\mathrm T}\emptyset'$ で、すべての $i$ について $C^{[i]}\not\le_{\mathrm T}C^{[\ne i]}$ となる集合 $C$ がある。とくに $A_i:=C^{[i]}$ とおくと、$A_i\le_{\mathrm T}\emptyset'$ で、$i\ne j$ なら $A_i$ と $A_j$ は互いに比較できない。

1 つの集合の列ごとに要求を立てる

文字列 $\gamma$ について、$\gamma^{(i)}$ を、$\gamma$ の番号 $\langle i,x\rangle$ の位置の値をすべて $0$ に替えた同じ長さの文字列とする。$\gamma\subset C$ なら $\gamma^{(i)}\subset C^{[\ne i]}$ である。要求は $R_{\langle i,e\rangle}:\ C^{[i]}\ne\Phi_e^{C^{[\ne i]}}$ で、文字列 $\gamma_0\subseteq\gamma_1\subseteq\cdots$($\gamma_0$ は空)を作って $C$ をその和とする。
段 $k=\langle i,e\rangle$ では、$\langle i,x\rangle\ge|\gamma_k|$ となる最小の $x$ をとり、「$\gamma'\supseteq\gamma_k$ と $s$ で $\Phi_{e,s}^{\gamma'^{(i)}}(x)\!\downarrow$ となるものがあるか」を判定する。この問いは lem-kp-force の 3 と同じく計算可能枚挙な集合への所属なので、$\emptyset'$ で判定できる。

  • ある場合:最初に見つかる $(\gamma',s)$ と値 $y$ をとる。$\gamma'$ の後ろに $0$ を付け加えて長さ $\langle i,x\rangle+1$ 以上にし、位置 $\langle i,x\rangle$ の値を $1-y$($y\notin\{0,1\}$ なら $0$)に書き換えたものを $\gamma_{k+1}$ とする。位置 $\langle i,x\rangle$ は $|\gamma_k|$ 以上なので $\gamma_k\subseteq\gamma_{k+1}$ であり、書き換えたのは第 $i$ 列の位置だけなので $\gamma'^{(i)}\subseteq\gamma_{k+1}^{(i)}$ である。
  • ない場合:$\gamma_k$ の後ろに $0$ を付け加えて長さ $\langle i,x\rangle+1$ にしたものを $\gamma_{k+1}$ とする。
    prf-thm-kp-main と同じく、$C\le_{\mathrm T}\emptyset'$ である。$R_{\langle i,e\rangle}$ を確かめる。ある場合、$\gamma'^{(i)}\subseteq\gamma_{k+1}^{(i)}\subset C^{[\ne i]}$ なので lem-kp-force の 1 により $\Phi_e^{C^{[\ne i]}}(x)=y\ne C^{[i]}(x)$ である($C^{[i]}(x)$ は $1-y$、$y\notin\{0,1\}$ なら $0$)。ない場合、$\Phi_e^{C^{[\ne i]}}(x)\!\downarrow$ とすると、(U2) により $v\ge|\gamma_k|$ で $\Phi_{e,s}^{C^{[\ne i]}\restriction v}(x)\!\downarrow$ となる $v,s$ がある。$C^{[\ne i]}\restriction v=(C\restriction v)^{(i)}$ で $\gamma_k\subseteq C\restriction v$ なので、$\gamma':=C\restriction v$ が「ある場合」の条件を満たし、矛盾する。よって $\Phi_e^{C^{[\ne i]}}$ は全域的でない。
    最後の主張:$A_j\le_{\mathrm T}C^{[\ne i]}$($j\ne i$。$x\in A_j\iff\langle j,x\rangle\in C^{[\ne i]}$)なので、$A_i\le_{\mathrm T}A_j$ なら $A_i\le_{\mathrm T}C^{[\ne i]}$ となって矛盾する。$\square$

計算可能な半順序 とは、$\mathbb N$ の上の半順序 $\preceq$ で、関係 $p\preceq q$ が決定可能なものをいう。

半順序の埋め込み

$(\mathbb N,\preceq)$ を計算可能な半順序とする。写像 $p\mapsto\mathbf d_p$ で、すべての $p,q$ について $p\preceq q\iff\mathbf d_p\le\mathbf d_q$ となり、$\mathbf d_p\le\mathbf 0'$ となるものがある。とくに $\mathbf 0'$ の下に、互いに比較できない次数が可算無限個ある。

下にある列をまとめる

thm-kp-independent の $C$ をとり、$D_p:=\{\langle q,x\rangle\in C\mid q\preceq p\}$、$\mathbf d_p:=\deg(D_p)$ とおく。$\preceq$ は決定可能なので $D_p\le_{\mathrm T}C\le_{\mathrm T}\emptyset'$ である。
$p\preceq q$ なら、$\langle r,x\rangle\in D_p\iff r\preceq p$ かつ $\langle r,x\rangle\in D_q$(推移律)なので、$D_p\le_{\mathrm T}D_q$ である。
$p\not\preceq q$ とする。$x\in C^{[p]}\iff\langle p,x\rangle\in D_p$(反射律)なので $C^{[p]}\le_{\mathrm T}D_p$ である。一方 $D_q$ の元 $\langle r,x\rangle$ は $r\preceq q$ を満たし、$p\not\preceq q$ だから $r\ne p$ である。よって $\langle r,x\rangle\in D_q\iff r\preceq q$ かつ $\langle r,x\rangle\in C^{[\ne p]}$ で、$D_q\le_{\mathrm T}C^{[\ne p]}$ である。$D_p\le_{\mathrm T}D_q$ なら $C^{[p]}\le_{\mathrm T}C^{[\ne p]}$ となり、thm-kp-independent に反する。
最後の主張は、$\preceq$ を等号($p\preceq q\iff p=q$)とすればよい。$\square$

与えられた次数と比較できない次数

thm-kp-main は 2 つの集合を同時に作った。一方の集合 $A$ を先に与えても、それと比較できない集合を作れる。ただし $A$ が計算可能だと、すべての集合が $A$ の上にあるので、この仮定は外せない。

比較できない次数の存在

$A\subseteq\mathbb N$ が計算可能でなければ、$B\le_{\mathrm T}A'$ で、$A\not\le_{\mathrm T}B$ かつ $B\not\le_{\mathrm T}A$ となる集合 $B$ がある。

A のジャンプに問い合わせる

文字列 $\tau_0\subseteq\tau_1\subseteq\cdots$($\tau_0$ は空)を作り、$B$ をその和とする。要求は $R_{2e}:A\ne\Phi_e^B$ と $R_{2e+1}:B\ne\Phi_e^A$ である。以下の問いはどれも「$A$ で計算可能枚挙な集合に属するか」の形なので、「ジャンプの基本定理」の 2 により $A'$ で判定できる。
段 $2e+1$. $x:=|\tau_{2e+1}|$ とし、$\Phi_e^A(x)\!\downarrow$ かを判定する。止まるなら値 $y$ を($A\le_{\mathrm T}A'$ を使って)実際に計算し、$\tau_{2e+2}:=\tau_{2e+1}$ に $1-y$($y\notin\{0,1\}$ なら $0$)を付け加えたものとする。止まらないなら $0$ を付け加える。どちらでも $B(x)\ne\Phi_e^A(x)$ または $\Phi_e^A(x)\!\uparrow$ である。
段 $2e$. 「$\tau'\supseteq\tau_{2e}$、$x$、$s$ で $\Phi_{e,s}^{\tau'}(x)\!\downarrow$ かつ $\Phi_{e,s}^{\tau'}(x)\ne A(x)$ となるものがあるか」を判定する。

  • ある場合:最初に見つかる $\tau'$ に $0$ を付け加えたものを $\tau_{2e+1}$ とする。lem-kp-force の 1 により $\Phi_e^B(x)=\Phi_{e,s}^{\tau'}(x)\ne A(x)$ である。
  • ない場合:$\tau_{2e+1}:=\tau_{2e}$ に $0$ を付け加えたものとする。このとき $\Phi_e^B$ は全域的でない。実際、全域的だとすると、$A$ を次のように計算できる。$x$ が与えられたら、$\tau'\supseteq\tau_{2e}$ と $s$ で $\Phi_{e,s}^{\tau'}(x)\!\downarrow$ となる組を探し、見つかった値を出力する。$B$ の始切片が (U2) によりこの条件を満たすので探索は止まり、「ない場合」なので出力は $A(x)$ に等しい。これは $A$ が計算可能でないことに反する。
    各段は $A'$ への問い合わせと止まることが分かっている探索だけからなるので、$B\le_{\mathrm T}A'$ である。$\square$
すべての次数と比較できる次数

次数 $\mathbf a$ がすべての次数と比較できるのは、$\mathbf a=\mathbf 0$ のときに限る。

$\mathbf 0$ はすべての次数以下なので比較でき、$\mathbf a\ne\mathbf 0$ なら thm-kp-cone の $B$ の次数が $\mathbf a$ と比較できない。こうして、次数の半順序は全順序から最も遠い形をしている:最小元 $\mathbf 0$ を除くどの次数にも、比較できない相手がいる。

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

外す仮定例何が成り立たなくなるか
thm-kp-cone の「$A$ は計算可能でない」$A=\emptyset$主張そのもの:どの $B$ も $\emptyset\le_{\mathrm T}B$ を満たす
lem-kp-force の 2 の「$X$ は $\tau$ の延長」$\Phi_e^X(x)$ が「$X(0)=1$ なら止まる」機械、$\tau=0$主張そのもの:$\tau$ の延長では止まらないが $X=\mathbb N$ では止まる
thm-kp-independent で第 $i$ 列を除くこと$C^{[\ne i]}$ を $C$ に替える主張そのもの:$x\in C^{[i]}\iff\langle i,x\rangle\in C$ なので常に $C^{[i]}\le_{\mathrm T}C$
cor-kp-poset の反対称律(前順序にする)$p\preceq q$ かつ $q\preceq p$、$p\ne q$別のもの:同値 $p\preceq q\iff\mathbf d_p\le\mathbf d_q$ は保たれるが $\mathbf d_p=\mathbf d_q$ となり、写像が単射でなくなる
反例の確かめ

1 行目:$\emptyset$ はどの $B$ からも何も問い合わせずに計算できる。2 行目:$\tau=0$ の延長 $\tau'$ はすべて $\tau'(0)=0$ なので機械は止まらず、lem-kp-force の 1 の延長は見つからない。一方 $X=\mathbb N$ は $X(0)=1$ で止まる。2 の結論が成り立つのは $\tau$ を延長する $X$ に限る。3 行目:所属 $\langle i,x\rangle\in C$ を問い合わせるだけの還元である。4 行目:prf-cor-kp-poset で使ったのは反射律と推移律だけなので同値は保たれ、$p\preceq q\preceq p$ から $D_p\le_{\mathrm T}D_q\le_{\mathrm T}D_p$ となる。

補足:Post の問題との関係

Post は決定不能性の次数を考え、どちらの方向にも還元できない 2 つの集合の次数を「比較できない」と呼んだうえで、計算可能枚挙で決定可能でない集合の中に $\emptyset'$ より低い次数のものがあるのか、すべて $\emptyset'$ と同じ次数なのかを問うた(Pos44 pp. 289–290)。thm-kp-main の $A,B$ は $\mathbf 0'$ の下にあるので、どちらの次数も $\mathbf 0$ でも $\mathbf 0'$ でもない($\mathbf 0$ と $\mathbf 0'$ はどちらも $\mathbf 0'$ 以下のすべての次数と比較できる)。しかし $A,B$ は計算可能枚挙とは限らないので、Post の問いには答えていない。有限の延長の方法は、$\emptyset'$ に「延長があるか」を問い合わせる点で計算可能な手順を超える $\emptyset'$ の計算力を使っている。これを計算可能枚挙な集合の近似の範囲に収めるために、要求に優先順位を付けて、いったん満たした要求が後から満たされなくなっても有限回で回復させる方法(有限傷害優先法)が生まれ、Friedberg–Muchnikの定理 が Post の問題に肯定的に答えた。

名前と出典

thm-kp-main は S. C. Kleene と E. L. Post による 1954 年の論文の結果である。比較できない次数の定義は Pos44 p. 289 にある。thm-kp-independent・cor-kp-poset・thm-kp-cone は同じ方法の標準的な拡張で、この記事の証明は 1 つの集合の列を使う形と、$A'$ への問い合わせで「ない場合」に $A$ が計算可能になることを導く形にまとめた独自のものである。記法と使用域の原理は Turing次数 の記事に合わせた。

関連項目

参考文献

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