Kleeneの木(Kleene tree)とは、計算可能な無限の 2 分木で、計算可能な道を 1 本ももたないもので、弱Königの補題により道は存在するが計算では見つからない。道の全体は空でない $\Pi^0_1$ クラスで計算可能な元をもたないものとして特徴づけられ、孤立した道は計算可能なので、Kleeneの木の道は連続体濃度ある。道の全体の測度が $1/2$ 以上の Kleeneの木があり、また対角非計算的な関数の木の道は、どの計算可能な無限 2 分木の道も計算する。
Kleeneの木(Kleene tree)とは、計算可能な無限の 2 分木で、計算可能な道を 1 本ももたないもののことである。弱Königの補題 により無限の 2 分木には必ず道があるが、木そのものが計算可能でも、道を計算で見つけられるとは限らない。その記事では、計算可能に分離できない 2 つの集合からこのような木を 1 つ作った。
この記事では、Kleene の木の道の全体 $[T]$ がどのような集合かを調べる。まず道の全体として現れる集合を $\Pi^0_1$ クラスとして特徴づけ(prop-kt-pi01)、Kleene の木の道は連続体濃度あって孤立した道をもたないことを示す(cor-kt-perfect)。主定理は 2 つある。1 つは、道の全体の測度が $1/2$ 以上の Kleene の木があること(thm-kt-measure)、もう 1 つは、その道がどの計算可能な無限の 2 分木の道をも計算する「普遍的な」Kleene の木があること(thm-kt-universal)である。
記号は 弱Königの補題 にそろえる。$0,1$ の有限列の全体を $2^{<\omega}$、無限列の全体を $2^\omega$ と書き、$|\sigma|$ は列の長さ、$\sigma^\frown i$ は $\sigma$ の後ろに $i$ を付けた列、$\sigma\preceq\tau$ は $\sigma$ が $\tau$ の先頭部分であること、$x\restriction n$ は $x$ の最初の $n$ 項である。2 分木 $T\subseteq2^{<\omega}$ の道の全体を $[T]$ と書く。$\sigma\in2^{<\omega}$ について $[\sigma]:=\{x\in2^\omega\mid\sigma\preceq x\}$ とおく。
$\varphi_e$ は番号 $e$ の部分計算可能関数で、$\varphi_{e,s}(x)=y$ は「$\varphi_e(x)$ の計算が $s$ ステップ未満で止まり値 $y$ を出す」ことを表す。この関係は $(e,x,y,s)$ について決定可能である(計算可能関数)。$\varphi_{e,s}(x)\!\downarrow$ は値を問わず止まることを表す。$K:=\{e\mid\varphi_e(e)\!\downarrow\}$ は 停止問題 の集合である。
列を自然数で番号付けし、2 分木 $T\subseteq2^{<\omega}$ が番号の集合として決定可能なとき、$T$ を 計算可能な木 という。計算可能な無限の 2 分木 $T$ で、$[T]$ に計算可能な元がないものを Kleene の木 という。
$T$ が無限であることは $[T]\ne\emptyset$ と同値である(弱Königの補題)。
$P\subseteq2^\omega$ が $\Pi^0_1$ クラス であるとは、決定可能な集合 $S\subseteq2^{<\omega}$ があって
$$
P=\{x\in2^\omega\mid\text{すべての }n\text{ で }x\restriction n\in S\}
$$
となることをいう。空でなく計算可能な元をもたない $\Pi^0_1$ クラスを 特別な(special)クラスという。
この定義と「特別な」の語は JS72(p. 605)による。$[T]$ が特別なクラスであることと $T$ が Kleene の木であることは同じである。$\Pi^0_1$ の名は、「$x\in P$」が自然数の上の全称量化 $1$ つで書けることによる(算術的階層)。
$P\subseteq2^\omega$ について、次は同値である。
1⇒2. $S$ を定義の決定可能な集合とし、$T:=\{\sigma\mid\text{すべての }n\le|\sigma|\text{ で }\sigma\restriction n\in S\}$ とおく。判定は $|\sigma|+1$ 個の $S$ の判定なので $T$ は計算可能で、先頭部分で閉じているので 2 分木である。$x\in[T]$ と「すべての $n$ で $x\restriction n\in S$」は同じである。
2⇒3. $W:=2^{<\omega}\setminus T$ は決定可能なので帰納的可算である。$x\notin[T]$ はある $n$ で $x\restriction n\notin T$ となること、すなわち $x\in[x\restriction n]$ で $x\restriction n\in W$ となることである。
3⇒1. $W$ を数え上げる計算可能な手続きを固定し、$W_s$ を $s$ ステップまでに出た元の有限集合とする。$S:=\{\sigma\mid\tau\preceq\sigma\text{ となる }\tau\in W_{|\sigma|}\text{ がない}\}$ とおくと $S$ は決定可能である。$x\notin P$ なら、$\tau\preceq x$ となる $\tau\in W$ があり、$\tau\in W_s$ となる $s$ をとると $n\ge\max(s,|\tau|)$ で $x\restriction n\notin S$ である。逆に $x\restriction n\notin S$ なら $\tau\preceq x\restriction n\preceq x$ となる $\tau\in W$ があり $x\notin P$ である。$\square$
2 分木 $T$ の元 $\sigma$ が 延長できる とは、$[T]\cap[\sigma]\ne\emptyset$ となることをいう。弱Königの補題 を $\sigma$ より上の部分に当てると、$\sigma$ が延長できないことは「ある $n\ge\lvert\sigma\rvert$ で、$\sigma$ を先頭にもつ長さ $n$ の列が $T$ にない」ことと同値である。$T$ が計算可能なら括弧の中は有限個の判定なので、延長できない元の全体は帰納的可算である。
計算可能な 2 分木 $T$ の延長できる元の全体 $E(T)$ が決定可能で $E(T)\ne\emptyset$ なら、$T$ は計算可能な道をもつ。従って Kleene の木 $T$ では $E(T)$ は決定可能でない。
$\langle\rangle\in E(T)$ である。$\sigma\in E(T)$ なら $\sigma^\frown0,\sigma^\frown1$ の少なくとも一方は $E(T)$ に入る。$x\restriction(m+1)$ を、$(x\restriction m)^\frown0\in E(T)$ なら $(x\restriction m)^\frown0$、そうでなければ $(x\restriction m)^\frown1$ と定めると、$x$ は $E(T)$ の判定から計算でき、すべての $x\restriction m$ が $T$ に入るので $x\in[T]$ である。$\square$
$T$ を計算可能な 2 分木とし、$x\in[T]$ と $n$ について $[T]\cap[x\restriction n]=\{x\}$ とする。このとき $x$ は計算可能である。
有限個の値 $x\restriction n$ を固定する。$m\ge n$ で $\tau:=x\restriction m$ がわかったとする。$[T]\cap[\tau]=\{x\}$ なので、$\tau^\frown(1-x(m))$ は延長できず、$\tau^\frown x(m)$ は延長できる。前者はある長さで $T$ に延長をもたなくなり、後者はどの長さでも延長をもつ。そこで $k=m+1,m+2,\dots$ の順に「$\tau^\frown0$ を先頭にもつ長さ $k$ の元が $T$ にない」「$\tau^\frown1$ を先頭にもつ長さ $k$ の元が $T$ にない」を調べ、初めて成り立った側を $\tau^\frown i$ とすれば $x(m)=1-i$ である。この探索はつねに止まるので、$x$ は計算可能である。$\square$
$T$ が Kleene の木なら、$[T]$ は孤立点をもたない空でない閉集合であり、$[T]$ の濃度は $2^{\aleph_0}$ である。
$[T]$ は $2^\omega$ の閉集合で、$[T]\ne\emptyset$ である。$x\in[T]$ が孤立点なら prop-kt-isolated により $x$ は計算可能で、仮定に反する。
濃度を示す。$\sigma\in E(T)$ について、$[T]\cap[\sigma]$ は 2 点以上を含むので、$\sigma\preceq\rho$ で $\rho^\frown0,\rho^\frown1$ がともに $E(T)$ に入る $\rho$ がある(異なる 2 つの道が初めて分かれる所をとる)。これを使って、$2^{<\omega}$ から $E(T)$ への写像 $h$ を $h(\langle\rangle):=\langle\rangle$、$h(\sigma^\frown i):=\rho_\sigma{}^\frown i$($\rho_\sigma$ は $h(\sigma)$ から上で選んだ分岐点)と帰納的に定める。$\sigma\prec\tau$ なら $h(\sigma)\prec h(\tau)$ で、$\sigma,\tau$ が分かれれば $h(\sigma),h(\tau)$ も分かれる。$y\in2^\omega$ に、すべての $h(y\restriction m)$ を先頭部分にもつ無限列 $H(y)$ を対応させると、$H(y)\in[T]$ であり、$H$ は単射である。従って $[T]$ の濃度は $2^{\aleph_0}$ 以上で、$2^\omega$ の部分集合なので等しい。$\square$
この系は、Kleene の木の道が「見つからないほど少ない」のではなく、連続体濃度だけあるのに 1 本も計算できない、ということを述べている。計算可能な関数は可算個しかないので、濃度だけからは矛盾は生じない。
$2^\omega$ の上の一様な測度 $\mu$ を、各座標が独立に確率 $1/2$ で $0,1$ をとる直積の確率測度とする。$\mu([\sigma])=2^{-|\sigma|}$ であり、$\mu$ は可算劣加法的である。
Kleene の木 $T$ で $\mu([T])\ge1/2$ となるものがある。
各 $e$ について、$\varphi_e(0),\dots,\varphi_e(e+1)$ がすべて定義されて値が $0$ か $1$ のとき、長さ $e+2$ の列 $\sigma_e:=(\varphi_e(0),\dots,\varphi_e(e+1))$ をとる。そうでないとき $\sigma_e$ は定めない。$\sigma\in T$ を次で定める。
すべての $e< |\sigma|$ について、$\varphi_{e,|\sigma|}(0),\dots,\varphi_{e,|\sigma|}(e+1)$ がすべて定義されて値が $0$ か $1$ であるなら、$\sigma_e\not\preceq\sigma$ である。
条件は $e$、$|\sigma|$ を上限とする有限個の決定可能な判定なので、$T$ は計算可能である。$\tau\preceq\sigma$ で $\tau\notin T$ なら、$\tau$ を除いた $e< |\tau|$ は $|\sigma|$ ステップでも同じ $\sigma_e$ を与え、$\sigma_e\preceq\tau\preceq\sigma$ なので $\sigma\notin T$ である。従って $T$ は 2 分木である。
$x\in[T]$ と「$\sigma_e$ が定まるすべての $e$ で $\sigma_e\not\preceq x$」は同値である。実際、$\sigma_e\preceq x$ となる $e$ があれば、計算が $s$ ステップ未満で止まる $s$ をとり、$n>\max(e,s,e+2)$ とすると $x\restriction n\notin T$ である。逆に右辺が成り立てば、どの $x\restriction n$ も条件を満たす。従って
$$ 2^\omega\setminus[T]=\bigcup_{e}[\sigma_e],\qquad\mu\bigl(2^\omega\setminus[T]\bigr)\le\sum_{e=0}^\infty2^{-(e+2)}=\frac12 $$
であり、$\mu([T])\ge1/2$ である。とくに $[T]\ne\emptyset$ で、$T$ は無限である。
$x\in2^\omega$ が計算可能なら、$x=\varphi_e$ となる $e$ がある。この $e$ で $\sigma_e=x\restriction(e+2)\preceq x$ なので $x\notin[T]$ である。従って $[T]$ は計算可能な元をもたない。$\square$
証明の要点は、計算可能な列を番号 $e$ ごとに測度 $2^{-(e+2)}$ の円筒 $1$ つで除くことにある。同じ計算可能な列は無限に多くの番号をもつが、除くのは $1$ 回で足りる。これに対し 弱Königの補題 の木の道の全体は測度 $0$ である(ex-kt-measure-zero)。
$2^\omega$ から $[0,1]$ への写像 $x\mapsto\sum_ix(i)2^{-i-1}$ で円筒 $[\sigma]$ は長さ $2^{-|\sigma|}$ の閉区間に移る。これを使うと、Heine–Borelの定理 の計算可能版の反例が得られる。
有理数を端点とする開区間の計算可能な列 $(I_k)_{k}$ で、$[0,1]$ の計算可能な実数をすべて覆い、長さの和が $3/4$ 以下のものがある。
prf-kt-measure の $\sigma_e$ について、$[\sigma_e]$ の像の閉区間 $[a_e,a_e+2^{-(e+2)}]$ を、中心を同じにして長さ $\tfrac32\cdot2^{-(e+2)}$ の開区間 $J_e$ に広げる。$(e,s)$ を $1$ 列に並べ、$k$ 番目の組 $(e,s)$ で $\sigma_e$ が $s$ ステップまでに定まり、それより前の組では定まっていなければ $I_k:=J_e$、そうでなければ $I_k:=\emptyset$(空の開区間 $(0,0)$)とする。$(I_k)$ は計算可能な列で、各 $J_e$ は高々 $1$ 回現れるので、長さの和は $\sum_e\tfrac32\cdot2^{-(e+2)}=\tfrac34$ 以下である。
$r\in[0,1]$ を計算可能な実数とする。$r$ が 2 進有理数なら、$r$ を像にもつ列として、ある所から先が一定の列($r=1$ なら全部 $1$ の列)がとれ、これは計算可能である。そうでないなら、$r$ と 2 進有理数の大小は有限の精度で決まるので、2 進展開の各桁は計算できる。どちらの場合も $r$ の像となる計算可能な $x$ があり、prf-kt-measure により $x\in[\sigma_e]$ となる $e$ があるので、$r\in J_e$ である。$\square$
$[0,1]$ を覆う開区間の長さの和は $1$ 以上でなければならないので、計算可能な実数だけを点とみなす世界では、この列は「長さの和が $1$ 未満なのに $[0,1]$ を覆う」列に見える。Sim06 の Example I.8.6(pp. 30–31)は、計算可能な実数を覆うが $[0,1]$ を覆わない区間の列を、計算可能に分離できない集合から作っている。cor-kt-cover は長さの和まで評価した形である。
関数 $f:\mathbb N\to\{0,1\}$ が 対角非計算的(diagonally noncomputable)であるとは、$\varphi_e(e)$ が定義されるすべての $e$ で $f(e)\ne\varphi_e(e)$ となることをいう。
$$
T_D:=\{\sigma\in2^{<\omega}\mid\text{すべての }e< |\sigma|\text{ で、}\varphi_{e,|\sigma|}(e)=y\text{ なら }\sigma(e)\ne y\}
$$
とおく。
$T_D$ は計算可能な 2 分木で、$[T_D]$ はちょうど $\{0,1\}$ に値をとる対角非計算的な関数の全体である(prf-kt-measure の前半と同じ確かめ方による)。$T_D$ は無限である。長さ $n$ の列 $\sigma$ を、$\varphi_{e,n}(e)=0$ なら $\sigma(e)=1$、それ以外は $\sigma(e)=0$ と定めれば $\sigma\in T_D$ だからである。$T_D$ は 弱Königの補題 の記事で計算可能に分離できない集合 $\{e\mid\varphi_e(e)=0\}$、$\{e\mid\varphi_e(e)=1\}$ から作った木と同じ条件で定まる。ここでは別の向きから、$T_D$ が Kleene の木であることを直接確かめる。$f\in[T_D]$ が計算可能なら $f=\varphi_e$ となる $e$ があり、$\varphi_e(e)=f(e)$ は定義されるので $f(e)\ne\varphi_e(e)$ に反する。
次の定理は、$T_D$ の道が Kleene の木の道の中で最も強いことを述べる。
$f\in[T_D]$ とし、$T$ を計算可能な無限の 2 分木とする。このとき、$f$ から計算できる $T$ の道がある。さらに、$T$ の決定の手順を固定すると、道は $f$ から一様に計算できる。
$\sigma\in2^{<\omega}$ について、部分計算可能関数 $\psi(\sigma)$ を次の手続きで定める。$k=\lvert\sigma\rvert+1,\lvert\sigma\rvert+2,\dots$ の順に、「$\sigma^\frown0$ を先頭にもつ長さ $k$ の元が $T$ にない」を調べ、成り立てば $0$ を出して止まる。成り立たなければ「$\sigma^\frown1$ を先頭にもつ長さ $k$ の元が $T$ にない」を調べ、成り立てば $1$ を出して止まる。どちらも成り立たなければ次の $k$ へ進む。
s-m-n定理 により、計算可能な関数 $g$ で、すべての $\sigma$ と $z$ について $\varphi_{g(\sigma)}(z)\simeq\psi(\sigma)$(両辺が同時に定義され、定義されれば等しい)となるものがある。$x\in2^\omega$ を
$$
x\restriction0:=\langle\rangle,\qquad x\restriction(m+1):=(x\restriction m)^\frown f\bigl(g(x\restriction m)\bigr)
$$
で定める。$x$ は $f$ から計算でき、手続きは $T$ の手順と $f$ だけに依る。
すべての $m$ で $x\restriction m$ が $T$ で延長できることを $m$ の帰納法で示す。$m=0$ では $T$ が無限なので $[T]\ne\emptyset$ である。$\sigma:=x\restriction m$ が延長できるとすると、$\sigma^\frown0,\sigma^\frown1$ の少なくとも一方は延長できる。
$\{0,1\}$ に値をとる対角非計算的な関数を計算できる Turing次数 は、Peano 算術の完全な拡大と結びつく。
算術の文に番号を付け、$\sigma\in2^{<\omega}$ を「番号 $i< |\sigma|$ の文を $\sigma(i)=1$ なら採り、$0$ なら否定を採る」と読む。Peano算術 にこれらを加えた理論の矛盾の証明で、番号が $|\sigma|$ 未満のものがない $\sigma$ の全体を $T_{\mathrm{PA}}$ とすると、$T_{\mathrm{PA}}$ は計算可能な 2 分木で、その道は PA の完全な無矛盾拡大を与え、すべての完全な無矛盾拡大はこうして得られる。thm-kt-universal により、$[T_D]$ の元はどれも PA の完全な無矛盾拡大を計算する。逆に、PA の完全な拡大は、空でない $\Pi^0_1$ クラスのどれにも元を計算することが Scott により観察されている(JS72 pp. 612–613 の Remark と Scott の観察。ここでは証明しない)。従って、$[T_D]$ の元を計算できる次数と、PA の完全な無矛盾拡大を計算できる次数は同じである。Gödelの不完全性定理 により $T_{\mathrm{PA}}$ 自身も Kleene の木である(計算可能な完全な無矛盾拡大はない)。
道を計算できなくても、停止問題 $K$ を使えば計算できる。
$T$ を計算可能な無限の 2 分木とし、$x_L$ を $[T]$ の辞書式順序で最小の元とする。このとき $x_L$ は $K$ から計算できる。
$x_L$ は prf-kt-extendible の手順(延長できるなら $0$ の側へ進む)で得られる道である。実際、各段で $0$ の側が延長できるなら、$0$ の側を通る道が $[T]$ にあるので、最小の元はそちらを通る。「$\sigma$ が延長できない」は「ある $n\ge\lvert\sigma\rvert$ で、$\sigma$ を先頭にもつ長さ $n$ の元が $T$ にない」と同値で、括弧の中は決定可能なので、この問いは $\sigma$ について一様に $K$ から答えられる($n$ を探し続ける機械の番号を $\sigma$ から計算し、その番号が $K$ に属すかを問えばよい)。$\square$
JS72 の Theorem 3(p. 610)は、さらに $x_L$ がある帰納的可算集合と同じ Turing 次数をもつことを示している($x_L$ より左にある $T$ の元の全体が帰納的可算になる)。一方、$K$ より真に易しい道も必ずある。弱Königの補題 の記事の低基底定理により、計算可能な無限の 2 分木には $X'\le_TK$ となる道 $X$ がある。Kleene の木に当てはめると、計算可能でないが $K$ を計算しない道が得られる。
道の次数がどこまで下げられるかには制限もある。JS72 の Theorem 4(p. 611)は、空でない $\Pi^0_1$ クラス $P$(計算可能な関数で値が抑えられる関数のクラスとして述べられ、p. 606 の注意で $2^\omega$ のクラスに移せる)で、$P$ の元が帰納的可算な次数 $\mathbf b$ から計算できるなら $\mathbf b$ が $K$ の次数に等しくなるものを作っている。同じ論文の Corollary 4.4(p. 613)は Scott と Tennenbaum による、次数が $K$ の次数に等しい PA の完全な拡大の存在である。
def-kt-dnc の $T_D$ について $\mu([T_D])=0$ である。
$\varphi_e(e)=0$ となる $e$ は無限にある(たとえば値がつねに $0$ の定数関数の番号は無限にある)。そのような $e_0< e_1< \dots< e_{k-1}$ を選ぶと、$[T_D]$ の元は各 $e_j$ で値 $\varphi_{e_j}(e_j)$ をとらないので、$[T_D]$ は $k$ 個の座標の値を $1$ 通りに固定した集合に含まれ、その測度は $2^{-k}$ である。$k$ は任意なので $\mu([T_D])=0$ である。$\square$
thm-kt-measure の木と比べると、Kleene の木の道の全体は、測度 $0$ のことも正のこともある。
$\mathbb N$ の有限列の全体を $\mathbb N^{<\omega}$ とし、$\sigma\in T$ を、すべての $e< |\sigma|$ で次が成り立つことと定める。
条件は $|\sigma|$ を上限とする判定なので $T$ は計算可能で、$\tau\preceq\sigma\in T$ なら $\tau\in T$ である($|\sigma|$ ステップで止まらなければ $|\tau|$ ステップでも止まらない)。$f\in[T]$ とする。$f(e)=s+1$ なら計算はちょうど $s$ ステップで止まる。$f(e)=0$ なら、すべての $n>e$ で $\varphi_{e,n}(e)\!\downarrow$ でないので $e\notin K$ である。従って $f=f_K$ である。逆に $f_K\restriction n$ はどの $n$ でも条件を満たす。$\square$
prop-kt-isolated では、2 分木であることを、延長できない側が有限の段で死ぬことを確かめるのに使った。ex-kt-omega の木では $f_K$ は孤立した道だが、各頂点の子が無限にあるので、「ほかの子がすべて死ぬ」ことは有限の段では決まらない。
| 主張 | 反例 | 満たされない条件 |
|---|---|---|
| 計算可能な木の孤立した道は計算可能である | ex-kt-omega | 木が 2 分木であること(分岐の数が有限で上から抑えられること) |
| 計算可能な無限の 2 分木には計算可能な道がある | def-kt-dnc の $T_D$ | 道を計算で選べること(弱Königの補題 は道の存在だけを述べる) |
| Kleene の木の道の全体は測度 $0$ である | thm-kt-measure の木 | $[T_D]$ のように、無限に多くの座標の値が禁じられていること(ex-kt-measure-zero) |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する