Turing次数(Turing degree)とは、自然数の集合 $B$ への問い合わせを何度でも使ってよい計算で $A$ を判定できるとき $A\le_{\mathrm T}B$ と定める Turing 還元について、互いに還元できる集合をまとめた同値類である。次数の全体は計算可能な集合の次数 $\mathbf 0$ を最小元とし、$A\oplus B$ の次数を最小上界とする上半束をなす。神託を使う停止問題であるジャンプ $A'$ は次数を真に上げ、$\emptyset'$ の次数 $\mathbf 0'$ は停止問題の次数である。可算個の次数には上界があるが、選択公理のもとで長さ $\omega_1$ の上界のない鎖があり、$\mathbf 0'$ の下には比較できない 2 つの次数がある。
Turing次数(Turing degree)は、自然数の集合を「どれだけ計算しにくいか」で分類する同値類である。集合 $B$ についての問い合わせ「$z\in B$ か」に何度でも答えてもらえるとき、それを使って $A$ を判定する手順があれば、$A$ は $B$ に Turing 還元可能 であるという。互いに Turing 還元できる集合をひとまとめにしたものが Turing 次数であり、決定不能性の次数(degree of unsolvability)ともよばれる。
多対一還元 では問い合わせは 1 回だけで、その答えをそのまま使う。Turing 還元は問い合わせの回数と答えの使い方を自由にした、計算で比べるもっとも一般的な還元である。たとえば自己停止集合 $K$ の補集合は $K$ に多対一還元できないが、Turing 還元はできる(答えを反転すればよい)。Post は、Turing の問い合わせの考え方からこの還元を取り出し、次数の比較を決定問題の理論の中心の問いとした(Pos44 pp. 289–290、§11 pp. 311–312)。
この記事では、Turing 還元と Turing 次数を定義し、次数の全体が最小元をもつ上半束であることを示す。次に、停止問題を相対化した ジャンプ が次数を真に上げることを証明し、可算個の次数には上界があるが長さ $\omega_1$ の鎖には上界がないこと、比較できない 2 つの次数が $0'$ の下にあることを証明する。
$\mathbb N=\{0,1,2,\dots\}$ とし、集合 $X\subseteq\mathbb N$ をその特性関数と同一視して $X(x)\in\{0,1\}$ と書く。部分関数の記号 $f(x)\!\downarrow$(定義される)、$f(x)\!\uparrow$(定義されない)、$\simeq$ は 計算可能性理論 の記事の「記法と前提」に従う。$\{0,1\}$ の有限列を 文字列 とよび、長さを $|\sigma|$ と書く。$X\restriction u$ は列 $X(0)X(1)\cdots X(u-1)$ を表す。
神託機械(oracle machine)とは、Turing機械 に、読むだけのテープ(神託テープ)を 1 本加えたものである。神託テープの $z$ 番目のマスには $X(z)$ が書かれていて、機械はこのテープの上でヘッドを動かして読むことができる。$X$ を 神託(oracle)という。神託機械を符号化して並べたものを $M_0,M_1,\dots$ とし、$M_e$ が神託 $X$ のもとで入力 $x$ に対して計算する部分関数を $\Phi_e^X$ と書く。
計算 $\Phi_e^X(x)$ が停止するとき、その途中で読んだ神託テープのマスの番号の最大値に $1$ を加えたもの(1 つも読まなければ $0$)を、この計算の 使用域(use)という。文字列 $\sigma$ について、$\Phi_{e,s}^\sigma(x)\!\downarrow$ は「$M_e$ が神託テープに $\sigma$ を書いた(その先は空白の)状態で入力 $x$ から始め、$s$ 歩以内に、番号 $|\sigma|$ 以上のマスを読まずに停止する」ことを表す。この関係は $(e,\sigma,x,s)$ について決定可能である($s$ 歩だけ動かせばよい)。
神託機械の全体については、神託のない場合と同じ構成で次の 2 つが成り立つ(万能Turing機械・s-m-n定理 の構成で、神託テープを 1 本加えたもの)。
$\Phi_e^X(x)\!\downarrow=y$ で、その使用域が $u$ とする。
機械の動きの各歩は、現在の状態と、各テープのヘッドの下の文字だけで決まる。停止する計算は有限歩で終わるので、読む神託テープのマスは有限個で、どれも番号が $u$ 未満である。$Y\restriction u=X\restriction u$ なら、$Y$ のもとでの計算は各歩で同じ文字を読むので、帰納法で各歩の様子が一致し、同じ歩数で同じ値 $y$ を出して停止する。これが 1 である。2 の前半は、$s$ を停止までの歩数とすれば、計算が番号 $u$ 以上のマスを読まないことと 1 と同じ議論による。後半も同様で、$\sigma$ のもとでの計算は番号 $|\sigma|$ 以上のマスを読まないので、各歩で $X$ のもとでの計算と同じ文字を読む。$\square$
$A,B\subseteq\mathbb N$ とする。ある $e$ について $\Phi_e^B$ が全域的で $\Phi_e^B=A$(特性関数として)となるとき、$A$ は $B$ に Turing 還元可能 であるといい、$A\le_{\mathrm T}B$ と書く。部分関数 $f$ が $\Phi_e^B$ の形に書けるとき、$f$ は $B$ で計算可能 であるという。$\operatorname{dom}\Phi_e^B$ の形の集合を $B$ で計算可能枚挙 な集合という。
$A\le_{\mathrm T}B$ かつ $B\le_{\mathrm T}A$ のとき $A\equiv_{\mathrm T}B$ と書く。これは同値関係であり(prop-td-basic の 1)、$A$ の同値類 $\deg(A)$ を $A$ の Turing 次数 という。次数の全体を $\mathcal D$ と書き、$\deg(A)\le\deg(B)\iff A\le_{\mathrm T}B$ で順序を入れる。計算可能な集合の次数を $\mathbf 0$ と書く。
次数は太字の小文字 $\mathbf a,\mathbf b,\dots$ で書く。$\mathbf a< \mathbf b$ は $\mathbf a\le\mathbf b$ かつ $\mathbf a\ne\mathbf b$ を、$\mathbf a\mid\mathbf b$ は $\mathbf a\not\le\mathbf b$ かつ $\mathbf b\not\le\mathbf a$(比較不能)を表す。$A\oplus B:=\{2x\mid x\in A\}\cup\{2x+1\mid x\in B\}$ とおく。
1:$A\le_{\mathrm T}A$ は、入力 $x$ に対して神託テープの $x$ 番目のマスを読んで写す機械による。$A=\Phi_i^B$、$B=\Phi_j^C$ とする。$M_i$ の動きを再現し、$M_i$ が神託テープの $z$ 番目のマスを読む場面では、代わりに神託 $C$ のもとで $\Phi_j^C(z)$ を計算してその値を読んだことにする機械を作る。$\Phi_j^C$ は全域的なのでこの置き換えは必ず終わり、再現した計算は $M_i$ の神託 $B$ のもとでの計算と同じ文字を読む。よって $A\le_{\mathrm T}C$。
2:$f$ が $A$ から $B$ への多対一還元なら、$f(x)$ を計算して神託テープの $f(x)$ 番目のマスを読めばよい。補集合は読んだ値を反転すればよい。
3:$A$ が計算可能なら、神託を読まずに $A$ を計算する機械がある。逆に $A\le_{\mathrm T}\emptyset$ なら、神託テープの各マスに $0$ を書いた機械として $A$ は計算可能である。
4:$A\le_{\mathrm T}A\oplus B$ は $2x$ 番目のマスを読むことによる。$B$ も同様。$A=\Phi_i^C$、$B=\Phi_j^C$ なら、入力 $2x$ には $\Phi_i^C(x)$、$2x+1$ には $\Phi_j^C(x)$ を返す機械で $A\oplus B\le_{\mathrm T}C$。1 により結論は代表の取り方によらない。
5:$A\le_{\mathrm T}B$ なら $A=\Phi_e^B$ となる番号 $e$ があるので、$B$ に還元できる集合は可算個である。$\deg(A)$ も $\deg(B)$ より下の次数も、そのような集合からなる。$\mathbb N$ の部分集合は $2^{\aleph_0}$ 個あり、それを可算集合に分けるので次数は $2^{\aleph_0}$ 個ある(可算個の可算集合の和は可算だから、次数が $2^{\aleph_0}$ 個未満なら部分集合も $2^{\aleph_0}$ 個未満になる。この比較は 選択公理 を使う)。$\square$
2 の逆は成り立たない。$\mathbb N\setminus K\le_{\mathrm T}K$ だが $\mathbb N\setminus K\not\le_{\mathrm m}K$ である(多対一還元 の命題「m 次数の基本構造」の 4)。多対一還元は半決定可能性を保つが、Turing 還元は保たない。
停止問題 は、計算可能な手順でどこまで判定できないかを示す最初の集合であった。神託 $A$ のもとでも同じ対角線論法が通り、$A$ で判定できない集合が得られる。
$A\subseteq\mathbb N$ について
$$
A':=\{e\in\mathbb N\mid\Phi_e^A(e)\!\downarrow\}
$$
を $A$ の ジャンプ(Turing jump)という。$A'' :=(A')'$ などと続け、$n$ 回のジャンプを $A^{(n)}$ と書く。
$A,B\subseteq\mathbb N$ とする。
1. (R1) の機械 $U$ を使い、入力 $e$ に対して神託 $A$ のもとで $U^A(\langle e,e\rangle)$ を計算する機械を考える。これが停止するのは $\Phi_e^A(e)\!\downarrow$ のとき、すなわち $e\in A'$ のときに限る。
2. $W=\operatorname{dom}\Phi_i^A$ とする。入力 $\langle a,y\rangle$ に対して $y$ を無視し、同じ神託のもとで $M_i$ を入力 $a$ で動かす神託機械の番号を $c$ とし、$f(a):=t(c,a)$ とおく($t$ は (R2) の関数)。$f$ は計算可能で、すべての $X$ と $y$ について $\Phi_{f(a)}^X(y)\simeq\Phi_i^X(a)$ である。$X=A$、$y=f(a)$ とおくと
$$
a\in W\iff\Phi_i^A(a)\!\downarrow\iff\Phi_{f(a)}^A(f(a))\!\downarrow\iff f(a)\in A'
$$
となるので、$f$ は $W$ から $A'$ への多対一還元である。$A$ は、入力 $x$ に対して神託テープの $x$ 番目のマスを読み、$1$ なら停止し $0$ なら止まらずに動き続ける機械の定義域なので、$A$ で計算可能枚挙であり、$A\le_{\mathrm m}A'$ を得る。
3. $A'\le_{\mathrm T}A$ と仮定し、$A'=\Phi_j^A$(全域的)とする。入力 $e$ に対して神託 $X$ のもとで $\Phi_j^X(e)$ を計算し、値が $1$ なら止まらずに動き続け、それ以外の値なら停止する神託機械 $M_d$ をとる。神託 $A$ のもとでは $\Phi_j^A(e)=A'(e)$ なので、
$$
d\in A'\iff\Phi_d^A(d)\!\downarrow\iff A'(d)\ne1\iff d\notin A'
$$
となり矛盾する。
4. $A=\Phi_i^B$ とする。入力 $\langle e,y\rangle$ に対して $y$ を無視し、$M_e$ を入力 $e$ で動かすが、$M_e$ が神託テープの $z$ 番目のマスを読む場面では代わりに $\Phi_i^X(z)$ を計算してその値を読んだことにする神託機械の番号を $c'$ とし、$g(e):=t(c',e)$ とおく。神託 $B$ のもとでは $\Phi_i^B=A$ は全域的なので、置き換えた計算は $M_e$ の神託 $A$ のもとでの計算と同じ文字を読み、同じときに停止する。したがって
$$
e\in A'\iff\Phi_e^A(e)\!\downarrow\iff\Phi_{g(e)}^B(g(e))\!\downarrow\iff g(e)\in B'
$$
であり、計算可能な $g$ が $A'$ から $B'$ への多対一還元になる。$\square$
4 と prop-td-basic の 2 から、$A\equiv_{\mathrm T}B$ なら $A'\equiv_{\mathrm T}B'$ である。よって次数のジャンプ $\deg(A)':=\deg(A')$ がうまく定まり、2 と 3 から $\mathbf a< \mathbf a'$、4 から $\mathbf a\le\mathbf b\Rightarrow\mathbf a'\le\mathbf b'$ である。とくに
$$
\mathbf 0< \mathbf 0'< \mathbf 0''< \cdots
$$
であり、$\mathcal D$ に極大元はない。
$\emptyset'\equiv_{\mathrm m}K$ である。したがって $\mathbf 0'=\deg(K)$ であり、計算可能枚挙なすべての集合の次数は $\mathbf 0'$ 以下である。
神託 $\emptyset$ のもとの神託機械は、神託テープの代わりにすべて $0$ のテープを持つ通常の Turing 機械として動くので、$\emptyset'$ は計算可能枚挙である。計算可能性理論 の定理「自己停止集合の完全性」により $\emptyset'\le_{\mathrm m}K$。逆に、$K$ は計算可能枚挙で、神託を読まない神託機械の定義域として $\emptyset$ で計算可能枚挙なので、thm-td-jump の 2 により $K\le_{\mathrm m}\emptyset'$。最後の主張も同じく thm-td-jump の 2 と prop-td-basic の 2 による。$\square$
1. $\mathbf a_n=\deg(A_n)$ とし、$C:=\{\langle n,x\rangle\mid x\in A_n\}$ とおく。入力 $x$ に対して神託テープの $\langle n,x\rangle$ 番目のマスを読む機械により $A_n\le_{\mathrm T}C$ なので、$\deg(C)$ はすべての $\mathbf a_n$ の上界である。
2. 超限帰納法で $\mathbf a_\alpha$ を定める。$\mathbf a_0:=\mathbf 0$、$\mathbf a_{\alpha+1}:=\mathbf a_\alpha'$ とする。$\lambda< \omega_1$ が極限順序数のとき、$\lambda$ より小さい順序数は可算個なので、それらを $\beta_0,\beta_1,\dots$ と並べ、1 の上界 $\deg(C)$ を $\mathbf a_\lambda$ とする(代表の集合と並べ方の選び方に選択公理を使う)。
$\beta< \alpha$ なら $\mathbf a_\beta< \mathbf a_\alpha$ であることを $\alpha$ についての帰納法で示す。後続の段では thm-td-jump から $\mathbf a_\alpha< \mathbf a_\alpha'$ である。極限 $\lambda$ では、$\beta< \lambda$ に対して $\beta+1< \lambda$ なので $\mathbf a_\beta< \mathbf a_{\beta+1}\le\mathbf a_\lambda$ である。
この列に上界 $\mathbf b=\deg(B)$ があったとする。$\alpha\mapsto\mathbf a_\alpha$ は単射なので、$\mathbf b$ より下に非可算個の次数があることになり、prop-td-basic の 5 に反する。$\square$
可算個の次数の上界は、1 の構成でいくらでも大きくとれる($\deg(C)$ が上界なら、thm-td-jump により $\deg(C)'$ はそれより真に大きい上界である)。2 は、各次数の下に可算個の次数しかない(prop-td-basic の 5)という、$\mathcal D$ の順序の局所的な可算性から来る。
prop-td-basic の 4 により、2 つの次数にはつねに最小上界がある。一方、次数は一列に並ばない。
$A,B\le_{\mathrm T}\emptyset'$ で $A\not\le_{\mathrm T}B$ かつ $B\not\le_{\mathrm T}A$ となる集合 $A,B$ がある。すなわち $\mathbf 0'$ の下に比較不能な 2 つの次数がある。
文字列 $\sigma_0\subseteq\sigma_1\subseteq\cdots$ と $\tau_0\subseteq\tau_1\subseteq\cdots$($\subseteq$ は先頭の部分であること)を段ごとに作り、$A,B$ をそれぞれの和(極限の無限列)とする。満たすべき要求は
$$
R_{2e}:\ A\ne\Phi_e^B,\qquad R_{2e+1}:\ B\ne\Phi_e^A\qquad(e\in\mathbb N)
$$
である。$\sigma_0=\tau_0$ を空の文字列とする。
段 $2e$ では、$x:=|\sigma_{2e}|$ とおき、次の問いを考える。
$\tau_{2e}\subseteq\tau$ となる文字列 $\tau$ と $s$ で、$\Phi_{e,s}^{\tau}(x)\!\downarrow$ となるものがあるか。
この問いの答えが「ある」となる $(e,x,\tau_{2e})$ の組の全体は、組 $(\tau,s)$ を順に調べれば止まる手順で確かめられるので計算可能枚挙であり、prop-td-zero-jump により $\emptyset'$ を神託として判定できる。
この定理は Kleene–Postの定理とよばれる。構成された $A,B$ は $\emptyset'$ で計算可能だが、計算可能枚挙とは限らない。計算可能枚挙な $A,B$ で同じ結論を得るのが Friedberg–Muchnikの定理 であり、そこでは $\emptyset'$ への問い合わせが使えないので、要求どうしの衝突を 優先順位 で整理する。
| 集合 | 次数 | 根拠 |
|---|---|---|
| 計算可能な集合 | $\mathbf 0$ | def-td-degree |
| 自己停止集合 $K$、$\emptyset'$ | $\mathbf 0'$ | prop-td-zero-jump |
| 自然数解をもつ整数係数の多項式方程式の符号の集合 | $\mathbf 0'$ | MRDPの定理 による $K$ からの多対一還元と、この集合が計算可能枚挙であること |
| 単純集合 | $\mathbf 0$ より大きく $\mathbf 0'$ 以下 | 帰納的可算集合 の定理「単純集合の存在」と prop-td-zero-jump |
| $\mathrm{Tot}$、$\mathrm{Fin}=\{e\mid W_e\text{ は有限}\}$、$\emptyset''$ | $\mathbf 0''$ | 下の折りたたみ |
| thm-td-kleene-post の $A,B$ | 互いに比較不能で $\mathbf 0'$ 以下 | thm-td-kleene-post |
| $A\oplus B$ | $\deg(A)$ と $\deg(B)$ の最小上界 | prop-td-basic の 4 |
3 行目の集合は Hilbertの第10問題 の記事の $D_{\mathbb N}$ で、その記事の定理「第 10 問題の決定不能性」の証明が $K\le_{\mathrm m}D_{\mathbb N}$ を与える。$W_e$ は 計算可能性理論 の記事の番号付けによる $\operatorname{dom}\varphi_e$ である。
算術的階層 の定理「完全な集合の例」により、$\mathrm{Tot}$ は $\Pi^0_2$ 完全、$\mathrm{Fin}$ は $\Sigma^0_2$ 完全、$\mathrm{Inf}=\mathbb N\setminus\mathrm{Fin}$ は $\Pi^0_2$ 完全である。よって $\mathrm{Tot}\equiv_{\mathrm m}\mathrm{Inf}$ で、prop-td-basic の 2 から $\mathrm{Tot}\equiv_{\mathrm T}\mathrm{Fin}$ である。
$\mathrm{Fin}\le_{\mathrm m}\emptyset''$:関係 $P(e,n)$「$m\ge n$ なら $m\notin W_e$」の否定は計算可能枚挙なので、$K$ に多対一還元でき、prop-td-zero-jump により $P$ は $\emptyset'$ で判定できる。$e\in\mathrm{Fin}$ は「ある $n$ で $P(e,n)$」なので、$n=0,1,\dots$ を $\emptyset'$ で順に調べる手順により $\mathrm{Fin}$ は $\emptyset'$ で計算可能枚挙であり、thm-td-jump の 2 を $A=\emptyset'$ に使えばよい。
$\emptyset''\le_{\mathrm m}\mathrm{Fin}$:lem-td-use により、$e\in\emptyset''$ は「ある文字列 $\sigma$ と $s$ で $\Phi_{e,s}^\sigma(e)\!\downarrow$ かつ、すべての $i< |\sigma|$ で $\sigma(i)=1\iff i\in\emptyset'$」と同値である。$i\in\emptyset'$ は $\Sigma^0_1$、$i\notin\emptyset'$ は $\Pi^0_1$ なので、算術的階層 の命題「論理演算と量化についての閉包性」により、この条件は $\Sigma^0_2$ である。$\mathrm{Fin}$ の $\Sigma^0_2$ 完全性から $\emptyset''\le_{\mathrm m}\mathrm{Fin}$。以上で $\emptyset''\equiv_{\mathrm T}\mathrm{Fin}\equiv_{\mathrm T}\mathrm{Tot}$ である。
| 主張 | 外す条件 | 例 | 成り立たなくなること |
|---|---|---|---|
| lem-td-use | 計算が停止する | 神託テープを $0,1,2,\dots$ と読み進め、$1$ を見つけたら停止する機械と、神託 $X=\emptyset$ | 停止するかどうかが神託の有限の部分で決まること |
| thm-td-jump の 2 | $W$ が $A$ で計算可能枚挙 | $A=\emptyset$、$W=\mathbb N\setminus\emptyset'$ | $W\le_{\mathrm m}A'$ |
| thm-td-chain の 1 | 次数が可算個 | thm-td-chain の 2 の列 | 上界があること |
| 多対一還元で下にある集合は半決定可能性を受け継ぐ | 還元が多対一還元 | $\mathbb N\setminus K\le_{\mathrm T}K$ | $K$ は半決定可能だが $\mathbb N\setminus K$ は半決定可能でない |
1 行目:$X=\emptyset$ のもとでは $1$ が見つからず停止しない。どの $u$ についても $Y:=\{u\}$ は $Y\restriction u=X\restriction u$ を満たすが、神託 $Y$ のもとでは $u$ 番目のマスで停止する。よって、停止しない計算については、神託のどの有限の部分を固定しても結論(停止しないこと)は保たれない。
2 行目:$\mathbb N\setminus\emptyset'\le_{\mathrm m}\emptyset'$ とすると、多対一還元は半決定可能性を保つので $\mathbb N\setminus\emptyset'$ が半決定可能になり、$\emptyset'$ と補集合がともに半決定可能だから $\emptyset'$ は決定可能になる(決定可能性 の命題「決定可能と半決定可能」)。これは thm-td-jump の 3($A=\emptyset$)に反する。
4 行目:$\mathbb N\setminus K\le_{\mathrm T}K$ は prop-td-basic の 2 による。$\mathbb N\setminus K$ が半決定可能でないことは 帰納的可算集合 の系「補集合が帰納的可算でない集合」による。
Post の問題.計算可能枚挙な集合の次数は $\mathbf 0'$ 以下にある(prop-td-zero-jump)。Post は、計算可能枚挙で決定可能でない集合がすべて $K$ と同じ次数をもつのか、$\mathbf 0$ と $\mathbf 0'$ の間に計算可能枚挙な集合の次数があるのかを問うた(Pos44 pp. 289–290)。単純集合は多対一還元では $K$ より真に下にある(多対一還元 の系「単純集合は完全でない」)が、Turing 還元での答えはそれだけでは決まらない。この問いは 1950 年代半ばに Friedberg と Muchnik が独立に、$\mathbf 0$ と $\mathbf 0'$ の真に間に計算可能枚挙な集合の次数があることを示して解いた(時期と 2 人の名は OLT26 §30.17、p. 463)。証明は Friedberg–Muchnikの定理 にある。
計算量との対応.多対一還元と Turing 還元に計算時間の制限を付けたものが、計算量理論 の多項式時間の多対一還元(Karp 還元)と Turing 還元(Cook 還元)である(OLT26 §30.16、p. 462)。
算術的階層との関係.prop-td-zero-jump と表の $\mathbf 0''$ の行は、$\Sigma^0_1$ 完全な集合の次数が $\mathbf 0'$、$\Sigma^0_2$ 完全な集合の次数が $\mathbf 0''$ であることを示している。ジャンプを重ねることは、算術的階層 を 1 段ずつ上ることに当たる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する