K自明集合

数学においてある自然数の集合がK自明集合（Kじめいしゅうごう、）であるとは、
そのを2進文字列と見た時に記述しやすいことを言う。
すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。
は1975年に計算不可能なK自明集合の存在を示した。
によれば、ランダムな集合の始切片は高い複雑性を持つ。
つまり、K自明集合はランダムからかけ離れているということである。
そのため、ランダムネスの理論で研究されており、
計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。
K自明集合は計算可能に近いという性質ももつ。
例えば、それらはすべてである、つまり、そのチューリングジャンプが停止問題に真理表還元可能である。
また、を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。
定義.
"K"を接頭コルモゴロフ複雑性とする、
すなわち、ある文字列"x"に対して、"K(x)"を接頭普遍機械のもとで"x"を出力する入力の最小の長さとする。
そのような機械は、直感的には、普遍的なプログラム言語で、有効なプログラムにさらに文字列を付け加えたものは有効でないようなものを表している。
"K"に関する背景としては、例えばチャイティンの定数などがある。
自然数の集合"A"が自然数の定数"b"によりK自明集合であるとは、
が成立することを言う。
ある集合がK自明集合であるとは、ある定数によりK自明であることを言う。
歴史と発展.
K自明集合の初期の研究は、主にK自明集合と計算可能集合との分離に焦点が置かれていた。
1976年のチャイティンの論文では、ある自然数"b"に対して
が成立するような集合について研究されている。ここで、"C"は単純コルモゴロフ複雑性である。そのような集合はC自明集合として知られている。
チャイティンはC自明集合の族が計算可能集合の族と一致することを示した。また、チャイティンはK自明集合が停止問題から計算可能であることも示した。この集合族は算術的階層におけるformula_3として知られている。
計算不可能なK自明集合の構成に初めて成功したのはである。c.e.でのそのような集合は、、コールズなどによる。未出版であれば、クンマー（Kummer）によるK自明集合の構成や、ムチニクJr.（Muchnik）による"K"低集合の構成などがある。
1999年から2008年における発展.
計算可能性理論の文脈において、コスト関数とは計算可能関数で
を満たすものを言う。あるformula_3集合"A"の計算可能な近似formula_6に対し、上記の関数はステージ"s"で"A(n)"の近似を変化させるコスト"c(n,s)"を測っている。最初のコスト関数の構成はクチェラとテルワインによる。彼らはc.e.集合でマルティンレーフランダム低だが計算可能ではないものを構成した。ここで、コスト関数は作られるformula_3集合の計算可能な近似に依存している。c.e.だが計算可能ではないK自明集合のコスト関数に依る構成が初めて世に出たのはDowney et al.の論文による。
formula_3集合"A"がコスト関数"c"に従うとは、"A"の計算可能な近似formula_9が存在して、formula_10
ここで、formula_11であり、formula_12はある固定した普遍接頭機械formula_13の計算可能近似における"s"ステップである。
計算不可能な"K"自明集合の構成の概略.
実は、その集合はpromptly simpleに取ることもできる。証明のアイディアはprompt simple集合を作る際の要求
を満たしながら、コストを小さくするというものである。ただしコスト関数は以下の極限条件を満たす必要がある。
つまり、"x"が増えるにしたがって、"s"がステージを走るときの"x"のコストの上限が"0"に収束する。例えば、標準コスト関数はこの性質を満たす。構成の本質的なアイディアとしては、prompt simple集合を作る要求を満たすために、"A"に数字を入れる前に、コストが十分小さくなるまで待つというものである。計算可能な枚挙formula_16を以下のように定義しよう。まず、formula_17。ステージformula_18においては、それぞれのformula_19が満たされておらず、formula_20かつformula_21を満たすようなformula_22が存在するなら、
"x"をformula_23に入れて、要求formula_24が満たされたと宣言する。構成は以上である。
この構成が実際にうまくいくことを確認しよう。まず、"A"はコスト関数に従う。なぜなら、それぞれの要求があるので"A"に入る数字は高々1つであって、合計"S"は高々
であるからである。次に、それぞれの要求は満たされる。もし、formula_26が無限ならば、コスト関数が極限条件を満たすという事実から、ある数字がやがては"A"に入り、要求が満たされるからである。
同値な特徴付け.
"K"自明集合は実はいくつかの計算的な低の概念と一致する、つまり計算可能に近い。以下の概念はすべて同じ集合族となる。
"K"低.
"A"が"K"低とは、ある自然数"b"が存在して、
を満たすことを言う。ここで、formula_28は神託"A"に相対化にされた接頭コルモゴロフ複雑性である。
マルティンレーフランダム低.
"A"がマルティンレーフランダム低であるとは、"Z"がマルティンレーフランダムであれば、"A"から相対的にもマルティンレーフランダムであることを言う。
マルティンレーフランダム底.
"A"がマルティンレーフランダム底であるとは、"A"が"A"から見てマルティンレーフランダムな列"Z"に対して、チューリング還元可能であることを言う。
"K"自明集合の特徴付けに関しては、更に多くのものが知られている。例えば、
などである。
2008年以降の発展.
2009年から解析の概念が使われるようになり、よく知られた問題を解くのに一役を担った。
ある集合"Y"が正密度点であるとは、すべての"Y"を含む実効的閉集合が"Y"で正の下側ルベール密度を持つことを言う。Bienvenu, Hölzl, Miller, and Niesは、マルティンレーフランダムな点に対して、チューリング完全ではないことと正密度点であることの同値性を示した。Day and Miller (2012) らは、これを使って、ML-cupping問題に対して肯定的な解を与えた。:すなわち、"A"が"K"自明集合であることと、formula_29が停止問題を計算するようなすべてのマルティンレーフランダムな点"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"自明集合族の真部分集合で低の性質を持つものである。