Sacksの分割定理(Sacks splitting theorem)とは、計算可能枚挙な集合 $A$ と計算可能でない計算可能枚挙な集合 $C$ に対し、$A$ を互いに素な計算可能枚挙集合 $A_0,A_1$ の和に分け、$A_i\le_{\mathrm T}A$ かつ $C$ がどちらにも Turing 還元できないようにできるという定理である。$C=A$ とすると、計算可能でない計算可能枚挙集合の次数は、それより真に低く互いに比較不能な 2 つの計算可能枚挙次数の最小上界になり、$\mathbf 0$ より大きい極小の計算可能枚挙次数がないことが従う。証明は有限損傷の優先論法で、一致の長さが伸びた計算の使用域より下の元を反対側の半分へ回すことで、各要求が有限回の損傷で満たされる。
前提知識: Turing次数, 帰納的可算集合, Friedberg–Muchnikの定理
Sacksの分割定理(Sacks splitting theorem)は、計算可能枚挙な集合を、計算可能枚挙な 2 つの互いに素な集合に分け、どちらの半分も指定した計算不能な計算可能枚挙集合 $C$ を計算できないようにできる、という定理である。$C$ として分ける集合 $A$ 自身をとると、計算不能な計算可能枚挙集合 $A$ は、$A$ より Turing 次数が真に低い 2 つの計算可能枚挙集合の互いに素な和になる。とくに、計算可能枚挙な集合の Turing次数 には、$\mathbf 0$ のすぐ上にある極小の次数がない。Sacks が 1963 年に示した(Sac63)。
証明は Friedberg–Muchnikの定理 と同じ 有限損傷の優先論法 による。違いは、Friedberg–Muchnik の構成では元を入れるかどうかを自分で決められたのに対し、ここでは $A$ の元は必ずどちらかの半分に入れなければならず、選べるのは どちらに入れるか だけだという点である。各要求は「自分が見ている計算を変えない側へ元を回す」ことで満たされる。どの程度の計算を守るかを測るのが、一致の長さ という量である。
この記事では、定理を完全に証明し、系として次数の分割と極小次数の非存在を導く。次に、素朴な分け方が失敗する例と、構成の部品を外すと結論が成り立たなくなる反例を挙げる。
神託機械の番号付け $\Phi_e^X$、計算の使用域(use)、Turing 還元 $\le_{\mathrm T}$、$A\oplus B$、次数の記号は Turing次数 の記事の「定義」に従う。段ごとの計算 $\Phi_{e,s}^X(x)\!\downarrow=y$($x< s$ で、$s$ 歩以内に値 $y$ を出して停止すること)と、計算可能枚挙集合の段ごとの近似は Friedberg–Muchnikの定理 の節「前提と記法」のものを使う。とくに同じ記事の補題「近似による計算」を次の形で使う。
$A$ を計算可能枚挙な集合、$C$ を計算可能でない計算可能枚挙な集合とする。このとき、計算可能枚挙な集合 $A_0,A_1$ で
$$
A=A_0\cup A_1,\qquad A_0\cap A_1=\emptyset,\qquad A_0\le_{\mathrm T}A,\quad A_1\le_{\mathrm T}A,\qquad C\not\le_{\mathrm T}A_0,\quad C\not\le_{\mathrm T}A_1
$$
となるものが存在する(証明は節「証明」で、lem-sacks-main を使って与える)。
$A$ を計算可能でない計算可能枚挙な集合とする。$A$ は互いに素な計算可能枚挙集合 $A_0,A_1$ の和に分けられ、$\mathbf a_i:=\deg(A_i)$、$\mathbf a:=\deg(A)$ について次が成り立つ。
thm-sacks-splitting を $C:=A$ に使う。$A_i\le_{\mathrm T}A$ かつ $A\not\le_{\mathrm T}A_i$ なので $\mathbf a_i< \mathbf a$ である。$x\in A\iff x\in A_0\lor x\in A_1$ なので $A\le_{\mathrm T}A_0\oplus A_1$ であり、逆に $A_0\oplus A_1\le_{\mathrm T}A$ なので、$\mathbf a=\mathbf a_0\vee\mathbf a_1$(Turing次数 の命題「次数の基本性質」の 4)で 3 が成り立つ。$A_0\le_{\mathrm T}A_1$ なら $A\le_{\mathrm T}A_0\oplus A_1\le_{\mathrm T}A_1$ となって $A\not\le_{\mathrm T}A_1$ に反するので $A_0\not\le_{\mathrm T}A_1$ であり、同様に $A_1\not\le_{\mathrm T}A_0$ で 2 が成り立つ。$A_0$ が計算可能なら $A_0\le_{\mathrm T}A_1$ となって 2 に反するので $\mathbf 0< \mathbf a_0$ であり、$\mathbf a_1$ も同様である。$\square$
1 は cor-sacks-degrees の 1 である。2 は 1 を $\mathbf b_1$、$\mathbf b_2$、… に繰り返し使えばよい。3 は、計算可能でない計算可能枚挙集合(たとえば停止問題 $K$)に cor-sacks-degrees の 2 を使えばよい。$\square$
3 は Friedberg–Muchnik の定理の別証明になっている。ただし構成の複雑さはほぼ同じで、どちらも有限損傷の優先論法である。
$A$ が有限なら、$A_0:=A$、$A_1:=\emptyset$ とすればよい。どちらも計算可能なので $C$ を計算できない(計算可能な集合に還元できる集合は計算可能である)。以下、$A$ は無限とする。$A$ の段ごとの近似から、新しく現れた元を現れた順に(同じ段で現れたものは小さい順に)並べると、$A$ の元を重複なく並べる計算可能な列 $a_0,a_1,a_2,\dots$ が得られる($A$ が無限なので、次の元を探す手順は必ず止まる)。
段 $s$ までに $A_0,A_1$ に入れた元の集合を $A_{0,s},A_{1,s}$ とする($A_{0,0}=A_{1,0}=\emptyset$)。要求を
$$
R_{2e+i}:\ \Phi_e^{A_i}\ne C\qquad(e\in\mathbb N,\ i\in\{0,1\})
$$
とし、番号の小さい方を優先順位が高いとする。$\Phi_e^{A_i}\ne C$ は「$\Phi_e^{A_i}$ が全域的でないか、ある $y$ で値が $C(y)$ と異なる」ことである。$n=2e+i$ と段 $s$ について、一致の長さ を
$$
\ell(n,s):=\max\bigl\{x\le s\ \big|\ \text{すべての }y< x\text{ で }\Phi_{e,s}^{A_{i,s}}(y)\!\downarrow=C_s(y)\bigr\}
$$
とし($x=0$ は条件を満たすので最大値はある)、制限 を
$$
r(n,s):=\max\bigl(\{0\}\cup\{\text{計算 }\Phi_{e,s}^{A_{i,s}}(y)\text{ の使用域}\mid y\le\ell(n,s),\ \Phi_{e,s}^{A_{i,s}}(y)\!\downarrow\}\bigr)
$$
とする。$y=\ell(n,s)$ の計算(一致が初めて成り立たなくなる所の計算)も、停止していれば制限に含めることが証明で効く。
段 $s=0,1,2,\dots$ で、元 $a_s$ を $A_0$ か $A_1$ のちょうど一方に入れる。$n\le s$ で $a_s< r(n,s)$ となる $n$ があれば、その最小のものを $n=2e+i$ として $a_s$ を $A_{1-i}$ に入れる。なければ $a_s$ を $A_0$ に入れる。
$a_s< r(n,s)$ であり $a_s$ が $R_n$ の側の集合 $A_i$ に入ったとき、$R_n$ は段 $s$ で 損傷を受ける という。構成の規則から、$n\le s$ のとき $R_n$ が段 $s$ で損傷を受けるのは、$a_s< r(n',s)$ となる $n'< n$ があり、その最小のものが $A_i$ の反対側を守るときに限る。
各段の判定は、有限個の $n\le s$ について有限集合を神託とする $s$ 歩の計算と $C_s$ を調べるだけなので、構成は計算可能な手順であり、$A_0,A_1$ は計算可能枚挙である。各 $a_s$ はちょうど一方に入るので、$A=A_0\cup A_1$、$A_0\cap A_1=\emptyset$ である。
$A_0\le_{\mathrm T}A$ かつ $A_1\le_{\mathrm T}A$ である。
$x$ が与えられたら、神託 $A$ に $x\in A$ かを問う。$x\notin A$ なら $x\notin A_i$ である。$x\in A$ なら $a_s=x$ となる $s$ を列を順に計算して探し(必ず見つかる)、構成を段 $s$ まで動かして $x$ がどちらに入ったかを見ればよい。$\square$
各 $n=2e+i$ について、次が成り立つ。
$n'< n$ について 3 が成り立つとし、その極限値の最大値を $\rho$ とする($n=0$ なら $\rho=0$)。$A$ の元で $\rho$ 未満のものは有限個で、$a_s$ は重複しないので、段 $s_0\ge n$ を、$s\ge s_0$ では $r(n',s)\le\rho$($n'< n$)かつ $a_s\ge\rho$ となるようにとれる。
1 の証明. $s\ge s_0$ で $a_s< r(n,s)$ とする。$n'< n$ では $a_s\ge\rho\ge r(n',s)$ なので、$a_s< r(\cdot,s)$ となる最小の番号は $n$ であり、$a_s$ は $A_{1-i}$ に入る。よって $s_0$ 以降 $R_n$ は損傷を受けない。言い換えると、$s\ge s_0$ では $A_i$ に $r(n,s)$ 未満の元は入らない。
保存の原理. $s\ge s_0$ で、$\Phi_{e,s}^{A_{i,s}}(y)$($y\in Y$)がすべて停止しているとする($Y$ は有限集合)。各段 $t\ge s$ で、これらの計算が $A_{i,t}$ のもとでも有効(神託が使用域より下で $A_{i,s}$ と一致する)であり、かつその使用域がすべて $r(n,t)$ 以下なら、段 $t$ で $A_i$ に入る元は $r(n,t)$ 以上なので、これらの計算は $A_{i,t+1}$ のもとでも有効である。これを段ごとの帰納法に使う。
2 の証明. $\Phi_e^{A_i}=C$ と仮定して、$C$ が計算可能になることを示す。
まず、任意の $y$ について $\ell(n,s)> y$ となる $s\ge s_0$ がある。実際、$y'\le y$ について (P2) により十分大きい $s$ で $\Phi_{e,s}^{A_{i,s}}(y')\!\downarrow=C(y')$ となり、$C_s(y')=C(y')$ となるので、$s> y$ なら $\ell(n,s)\ge y+1$ である。
$y$ を与えたら、$\ell(n,s)> y$ となる $s\ge s_0$ を探し(見つかる)、$C_s(y)$ を出力する。これが $C(y)$ に等しいことを示す。そうでないとし、$y^*$ を $C_s(y')\ne C(y')$ となる最小の $y'\le y$ とする。$y''< y^*$ では $C_s(y'')=C(y'')$ なので、すべての $t\ge s$ で $C_t(y'')=C_s(y'')$ である。段 $s$ の計算 $\Phi_{e,s}^{A_{i,s}}(y'')$($y''\le y^*$)は $\ell(n,s)> y\ge y^*$ によりすべて停止している。$t\ge s$ についての帰納法で、これらの計算が段 $t$ で有効であることを示す。$t=s$ では明らかである。段 $t$ で有効なら、(P1) により $\Phi_{e,t}^{A_{i,t}}(y'')\!\downarrow=C_s(y'')$ であり、$y''< y^*$ では $C_s(y'')=C_t(y'')$ なので $\ell(n,t)\ge y^*$ である。よって $y''\le y^*\le\ell(n,t)$ の計算はすべて $r(n,t)$ に数えられ、保存の原理により段 $t+1$ でも有効である。こうしてこれらの計算は永久に有効で、$A_i$ は使用域より下で $A_{i,s}$ と一致するので、(P1) により $\Phi_e^{A_i}(y^*)=C_s(y^*)\ne C(y^*)$ となる。これは $\Phi_e^{A_i}=C$ に反する。よって $C(y)=C_s(y)$ であり、この手順は $C$ を計算する。$C$ は計算可能でないので矛盾し、$\Phi_e^{A_i}\ne C$ である。
3 の証明. 2 により、$\Phi_e^{A_i}(p)$ が定義されないか $C(p)$ と異なる最小の $p$ がある。$y< p$ では $\Phi_e^{A_i}(y)\!\downarrow=C(y)$ なので、(P2) により段 $s_1\ge\max(s_0,p+1)$ を、$s\ge s_1$ ではすべての $y< p$ について段 $s$ の計算 $\Phi_{e,s}^{A_{i,s}}(y)$ が神託 $A_i$ のもとの計算と同じ(値 $C(y)$、同じ使用域)で、$C_s(y)=C(y)$ となるようにとれる。$s\ge s_1$ では $\ell(n,s)\ge p$ である。
場合 1:$\Phi_e^{A_i}(p)\!\downarrow\ne C(p)$。 さらに大きい段 $s_2$ から先、$p$ の計算も神託 $A_i$ のもとの計算と同じになり $C_s(p)=C(p)$ となるので、$\ell(n,s)=p$ であり、$r(n,s)$ は $y\le p$ の神託 $A_i$ のもとの計算の使用域の最大値で一定である。
場合 2:$\Phi_e^{A_i}(p)\!\uparrow$。 ある $t\ge s_1$ で $\Phi_{e,t}^{A_{i,t}}(p)\!\downarrow$ になったとする。$t'\ge t$ について、$y< p$ の計算は神託 $A_i$ のもとの計算なので有効のままで $\ell(n,t')\ge p$ であり、$p$ の計算が段 $t'$ で有効なら、その使用域は $r(n,t')$ に数えられる。保存の原理による帰納法で、$p$ の計算は永久に有効になり、(P1) により $\Phi_e^{A_i}(p)\!\downarrow$ となって仮定に反する。よって $s\ge s_1$ で $\Phi_{e,s}^{A_{i,s}}(p)\!\uparrow$ であり、$\ell(n,s)=p$、$r(n,s)$ は $y< p$ の計算の使用域の最大値で一定である。
以上で $R_n$ について 1〜3 が成り立ち、帰納法が進む。$\square$
定理の証明の完了. $A_0,A_1$ は計算可能枚挙で、$A$ の互いに素な分割であり、lem-sacks-reducible により $A_i\le_{\mathrm T}A$ である。lem-sacks-main の 2 により、すべての $e$ と $i$ で $\Phi_e^{A_i}\ne C$、すなわち $C\not\le_{\mathrm T}A_i$ である。これで thm-sacks-splitting が示された。$\square$
$C$ が計算可能枚挙であることの使い方. 証明で $C$ について使ったのは、計算可能な近似 $C_s$ が各点で $C$ に収束することと、2 の証明の「$y''< y^*$ では $C_t(y'')=C_s(y'')$」(増加列なので、両端が等しければ間も等しい)だけである。
損傷の回数. 1 の証明が示すように、$R_n$ が損傷を受けるのは、優先順位の高い要求の制限がまだ動いている間だけである。高い要求の制限はどれも有限の値に落ち着くので、$R_n$ の損傷は有限回で終わる。一方、その段 $s_0$ を構成から計算で求めることはできない。制限が落ち着くかどうかは、$\Phi_e^{A_i}$ が $C$ とどこで食い違うかという、一般には決定できない問いで決まるからである。
制限による振り分けがなぜ要るかを、2 つの素朴な分け方で見る。停止問題 $K$ について
$$
A:=\{2x\mid x\in K\}\cup\{2x+1\mid x\in K\}
$$
とおく。$x\in K\iff 2x\in A$ なので $K\le_{\mathrm T}A$、逆に $z\in A\iff\lfloor z/2\rfloor\in K$ なので $A\le_{\mathrm T}K$ で、$A$ は計算不能な計算可能枚挙集合である。$K$ の元が現れるたびに $2x,2x+1$ をこの順に続けて並べると、$A$ の元を重複なく並べる計算可能な列 $a_0,a_1,\dots$ が得られる。
| 外したもの | 例 | 成り立たなくなる結論 |
|---|---|---|
| $C$ が計算可能でないこと | $C=\emptyset$ | thm-sacks-splitting の $C\not\le_{\mathrm T}A_i$ |
| $A$ が計算可能でないこと | $A=\emptyset$ | cor-sacks-degrees の $\mathbf 0< \mathbf a_i$ |
| 構成の制限($a_s$ をいつも $A_0$ に入れる) | 計算不能な計算可能枚挙集合 $A$、$C=A$ | thm-sacks-splitting の $C\not\le_{\mathrm T}A_0$ |
| 構成の制限($a_s$ を $A_{s\bmod2}$ に入れる) | ex-sacks-naive の $A$ と列、$C=A$ | thm-sacks-splitting の $C\not\le_{\mathrm T}A_0$ |
1 行目:$\emptyset$ はどの集合にも Turing 還元できる(Turing次数 の命題「次数の基本性質」の 3)ので、$\emptyset\le_{\mathrm T}A_i$ である。2 行目:$A=\emptyset$ なら $A_0=A_1=\emptyset$ で、次数は $\mathbf 0$ である。3 行目:$A_0=A$ なので $A\le_{\mathrm T}A_0$ である。4 行目:ex-sacks-naive の 2 により $A\le_{\mathrm T}A_0$ である。3・4 行目では $A$ を互いに素な計算可能枚挙集合に分けるという部分は成り立っており、成り立たないのは $C$ を避ける部分だけである。
$C$ を避けることの意味. thm-sacks-splitting は、$A$ の次数の下で $C$ の次数より上の部分($C$ の上の 錐)を避けて分割できることを述べている。たとえば $C=K$ とすると、どの計算可能枚挙集合 $A$ も、停止問題を計算できない 2 つの計算可能枚挙集合に分けられる。$A=K$ にとれば、$\mathbf 0'$ は $\mathbf 0'$ より真に低い 2 つの計算可能枚挙次数の最小上界である。
次数の構造. cor-sacks-no-minimal は、計算可能枚挙な集合の次数の全体に、$\mathbf 0$ の直後の次数がないことを示す。Sacks はさらに、計算可能枚挙な集合の次数が稠密であること、すなわち $\mathbf a< \mathbf b$ となる計算可能枚挙次数の間に必ず別の計算可能枚挙次数があることを示した(Sac64)。cor-sacks-no-minimal の 1 は、稠密性のうち $\mathbf a=\mathbf 0$ の場合($\mathbf 0$ と $\mathbf b$ の間)にあたる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する