K自明集合

数学においてある自然数の集合がK自明集合︵Kじめいしゅうごう、英: K-trivial set︶であるとは、 その始切片︵英語: initial segment︶を2進文字列と見た時に記述しやすいことを言う。 すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。 ソロベイ︵英語: Robert_M._Solovay︶は1975年に計算不可能なK自明集合の存在を示した。

シュノール・レビンの定理︵英語: Schnorr-Levin theorem︶によれば、ランダムな集合の始切片は高い複雑性を持つ。 つまり、K自明集合はランダムからかけ離れているということである。 そのため、ランダムネスの理論で研究されており、 計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。

K自明集合は計算可能に近いという性質ももつ。 例えば、それらはすべて超低︵英語: superlow︶である、つまり、そのチューリングジャンプが停止問題に真理表還元可能である。 また、チューリングイデアル︵英語: Turing ideal︶を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。

定義

Kを接頭コルモゴロフ複雑性とする、 すなわち、ある文字列xに対して、K(x)を接頭普遍機械のもとでxを出力する入力の最小の長さとする。 そのような機械は、直感的には、普遍的なプログラム言語で、有効なプログラムにさらに文字列を付け加えたものは有効でないようなものを表している。 Kに関する背景としては、例えばチャイティンの定数などがある。

自然数の集合Aが自然数の定数bによりK自明集合であるとは、

${\displaystyle \forall nK(A\upharpoonright n)\leq K($n)+b} $\forall nK(A\upharpoonright n)\leq K(n)+b$
が成立することを言う。

ある集合がK自明集合であるとは、ある定数によりK自明であることを言う。

歴史と発展

K自明集合の初期の研究は、主にK自明集合と計算可能集合との分離に焦点が置かれていた。

1976年のチャイティンの論文では、ある自然数bに対して

${\displaystyle \forall nC(A\upharpoonright n)\leq C($n)+b} $\forall nC(A\upharpoonright n)\leq C(n)+b$
が成立するような集合について研究されている。ここで、Cは単純コルモゴロフ複雑性である。そのような集合はC自明集合として知られている。 チャイティンはC自明集合の族が計算可能集合の族と一致することを示した。また、チャイティンはK自明集合が停止問題から計算可能であることも示した。この集合族は算術的階層における$\Delta _{2}^{0}$$\Delta _{2}^{0}$として知られている。

計算不可能なK自明集合の構成に初めて成功したのはソロベイ︵英語: Robert_M._Solovay︶である。c.e.でのそのような集合は、カルーデ︵英語: Cristian S. Calude︶、コールズなどによる。未出版であれば、クンマー︵Kummer︶によるK自明集合の構成や、ムチニクJr.︵Muchnik︶によるK低集合の構成などがある。

1999年から2008年における発展

計算可能性理論の文脈において、コスト関数とは計算可能関数で

$c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}$$c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}$
を満たすものを言う。ある$\Delta _{2}^{0}$$\Delta _{2}^{0}$集合Aの計算可能な近似$\langle A_{s}\rangle$$\langle A_{s}\rangle$に対し、上記の関数はステージsでA(n)の近似を変化させるコストc(n,s)を測っている。最初のコスト関数の構成はクチェラとテルワインによる。彼らはc.e.集合でマルティンレーフランダム低だが計算可能ではないものを構成した。ここで、コスト関数は作られる$\Delta _{2}^{0}$$\Delta _{2}^{0}$集合の計算可能な近似に依存している。c.e.だが計算可能ではないK自明集合のコスト関数に依る構成が初めて世に出たのはDowney et al.の論文による。

$\Delta _{2}^{0}$$\Delta _{2}^{0}$集合Aがコスト関数cに従うとは、Aの計算可能な近似$\langle A_{s}:s\in \omega \rangle$$\langle A_{s}:s\in \omega \rangle$が存在して、${\displaystyle S=\Sigma _{x,s}c(x,s)[x<s\wedge {\text{x is the least s.t. }}A_{s-1}($x)\neq A_{s}(x)]<\infty } $S=\Sigma _{x,s}c(x,s)[x<s\wedge {\text{x is the least s.t. }}A_{s-1}(x)\neq A_{s}(x)]<\infty$ を満たすことを言う。K自明集合は以下で定義される標準コスト関数に従う集合として特徴付けられる。

${\displaystyle c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}($x)}} $c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}$
ここで、${\displaystyle K_{s}($x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}} $K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}$であり、$\mathbb {U} _{s}$$\mathbb {U} _{s}$はある固定した普遍接頭機械$\mathbb {U}$$\mathbb {U}$の計算可能近似におけるsステップである。

計算不可能なK自明集合の構成の概略

実は、その集合はpromptly simpleに取ることもできる。証明のアイディアはprompt simple集合を作る際の要求

$PS_{e}:|W_{e}|=\infty \Rightarrow \exists s\exists x[x\in W_{e,s}\backslash W_{e,s-1}\wedge x\in A_{s}]$$PS_{e}:|W_{e}|=\infty \Rightarrow \exists s\exists x[x\in W_{e,s}\backslash W_{e,s-1}\wedge x\in A_{s}]$
を満たしながら、コストを小さくするというものである。ただしコスト関数は以下の極限条件を満たす必要がある。

$\lim _{x}\sup _{s>x}c(x,s)=0$$\lim _{x}\sup _{s>x}c(x,s)=0$
つまり、xが増えるにしたがって、sがステージを走るときのxのコストの上限が0に収束する。例えば、標準コスト関数はこの性質を満たす。構成の本質的なアイディアとしては、prompt simple集合を作る要求を満たすために、Aに数字を入れる前に、コストが十分小さくなるまで待つというものである。計算可能な枚挙$\langle A_{s}:s\in \omega \rangle$$\langle A_{s}:s\in \omega \rangle$を以下のように定義しよう。まず、$A_{0}=\emptyset$$A_{0}=\emptyset$。ステージ$s>0$$s>0$においては、それぞれの$e<s$$e<s$において、もし、$PS_{e}$$PS_{e}$が満たされておらず、$x\in W_{e,s}\backslash W_{e,s-1}$$x\in W_{e,s}\backslash W_{e,s-1}$かつ$c(x,s)\leq 2^{-e}$$c(x,s)\leq 2^{-e}$を満たすような$x\geq 2e$$x\geq 2e$が存在するなら、 xを$A_{s}$$A_{s}$に入れて、要求$PS_{e}$$PS_{e}$が満たされたと宣言する。構成は以上である。

この構成が実際にうまくいくことを確認しよう。まず、Aはコスト関数に従う。なぜなら、それぞれの要求があるのでAに入る数字は高々1つであって、合計Sは高々

$\Sigma _{e}2^{-e}<\infty$$\Sigma _{e}2^{-e}<\infty$
であるからである。次に、それぞれの要求は満たされる。もし、$W_{e}$$W_{e}$が無限ならば、コスト関数が極限条件を満たすという事実から、ある数字がやがてはAに入り、要求が満たされるからである。

同値な特徴付け

K自明集合は実はいくつかの計算的な低の概念と一致する、つまり計算可能に近い。以下の概念はすべて同じ集合族となる。

K低

AがK低とは、ある自然数bが存在して、

${\displaystyle \forall nK^{A}($n)+b\geq K(n)} $\forall nK^{A}(n)+b\geq K(n)$
を満たすことを言う。ここで、$K^{A}$$K^{A}$は神託Aに相対化にされた接頭コルモゴロフ複雑性である。

マルティンレーフランダム低

Aがマルティンレーフランダム低であるとは、Zがマルティンレーフランダムであれば、Aから相対的にもマルティンレーフランダムであることを言う。

マルティンレーフランダム底

Aがマルティンレーフランダム底であるとは、AがAから見てマルティンレーフランダムな列Zに対して、チューリング還元可能であることを言う。

K自明集合の特徴付けに関しては、更に多くのものが知られている。例えば、

(一)弱2ランダム低

(二)左c.e.差実数低︵ここでは、ランダムの概念が使われていないことに注意。︶

などである。

2008年以降の発展

2009年から解析の概念が使われるようになり、よく知られた問題を解くのに一役を担った。

ある集合Yが正密度点であるとは、すべてのYを含む実効的閉集合がYで正の下側ルベール密度を持つことを言う。Bienvenu, Hölzl, Miller, and Niesは、マルティンレーフランダムな点に対して、チューリング完全ではないことと正密度点であることの同値性を示した。Day and Miller (2012) らは、これを使って、ML-cupping問題に対して肯定的な解を与えた。:すなわち、AがK自明集合であることと、$A\oplus Z$$A\oplus Z$が停止問題を計算するようなすべてのマルティンレーフランダムな点Zに対してZが停止問題を計算する、ということは同値。

Yが一密度点であるとは、すべてのYを含む実効的閉集合がYでルベーグ密度1を持つことを言う。一密度点でないようなどのマルティンレーフランダムな集合でも、すべてのK自明集合を計算する。Bienvenu et al. Day and Miller (2012)は正密度点ではあるが一密度点ではないマルティンレーフランダムな集合が存在することを示した。 なので、非完全なマルティンレーフランダムな集合ですべてのK自明集合を計算するものが存在する。 これはMiller and Nies. に載っているStephanによって最初に問われた問題、covering問題に対して肯定的な答えを与える。この分野の概要は、L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies, and D. Turetsky などが参考になるであろう。K自明集合の変種も研究されている。例えば、Schnorr trivial setsは計算可能な測度を持つ機械によって定義される。strongly jump traceable setsはK自明集合族の真部分集合で低の性質を持つものである。