K自明集合

数学においてある自然数の集合がK自明集合（Kじめいしゅうごう、）であるとは、
そのを2進文字列と見た時に記述しやすいことを言う。
すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。
は1975年に計算不可能なK自明集合の存在を示した。

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

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

 定義 

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

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

が成立することを言う。

ある集合がK自明集合であるとは、ある定数によりK自明であることを言うA. Nies (2009). Computability and Randomness, Oxford Science Publications, ISBN  978-0199230761Downey, Rodney G., Hirschfeldt, Denis R. (2010), "Algorithmic Randomness and Complexity", ISBN 978-0-387-68441-3。

 歴史と発展 

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

1976年のチャイティンの論文Gregory J. Chaitin (1976),
    "Information-Theoretic Characterizations of Recursive Infinite Strings",
    Theoretical Computer Science
Volume 2, Issue 1, June 1976, Pages 45–48では、ある自然数bに対して

が成立するような集合について研究されている。ここで、Cは単純コルモゴロフ複雑性である。そのような集合はC自明集合として知られている。
チャイティンはC自明集合の族が計算可能集合の族と一致することを示した。また、チャイティンはK自明集合が停止問題から計算可能であることも示した。この集合族は算術的階層におけるとして知られている。

計算不可能なK自明集合の構成に初めて成功したのはである。c.e.でのそのような集合は、、コールズCristian Calude, Richard J. Coles, Program-Size Complexity of Initial Segments and Domination Reducibility, (1999), proceeding of: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaaなどによる。未出版であれば、クンマー（Kummer）によるK自明集合の構成や、ムチニクJr.（Muchnik）によるK低集合の構成などがある。

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

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

を満たすものを言う。ある集合Aの計算可能な近似に対し、上記の関数はステージsでA(n)の近似を変化させるコストc(n,s)を測っている。最初のコスト関数の構成はクチェラとテルワインによるAntonin Kučera and Sebastiaan A. Terwijn (1999), "Lowness for the Class of Random Sets", The Journal of Symbolic Logic, Vol. 64, No. 4 (Dec., 1999), pp. 1396–1402。彼らはc.e.集合でマルティンレーフランダム低だが計算可能ではないものを構成した。ここで、コスト関数は作られる集合の計算可能な近似に依存している。c.e.だが計算可能ではないK自明集合のコスト関数に依る構成が初めて世に出たのはDowney et al.の論文によるRod G. Downey,
Denis R. Hirschfeldt,
Andr ́e Nies,
Frank Stephan, "Trivial Reals", Electronic Notes in Theoretical Computer Science 66 No. 1 (2002), URL: http://www.elsevier.nl/locate/entcs/volume66.html。

集合Aがコスト関数cに従うとは、Aの計算可能な近似が存在して、
を満たすことを言う。K自明集合は以下で定義される標準コスト関数に従う集合として特徴付けられるAndré Nies, (2005), "Lowness properties and randomness", Advances in Mathematics, Volume 197, Issue 1, 20 October 2005, Pages 274–305。

ここで、であり、はある固定した普遍接頭機械の計算可能近似におけるsステップである。

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

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

を満たしながら、コストを小さくするというものである。ただしコスト関数は以下の極限条件を満たす必要がある。

つまり、xが増えるにしたがって、sがステージを走るときのxのコストの上限が0に収束する。例えば、標準コスト関数はこの性質を満たす。構成の本質的なアイディアとしては、prompt simple集合を作る要求を満たすために、Aに数字を入れる前に、コストが十分小さくなるまで待つというものである。計算可能な枚挙を以下のように定義しよう。まず、。ステージにおいては、それぞれのにおいて、もし、が満たされておらず、かつを満たすようなが存在するなら、
xをに入れて、要求が満たされたと宣言する。構成は以上である。

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

であるからである。次に、それぞれの要求は満たされる。もし、が無限ならば、コスト関数が極限条件を満たすという事実から、ある数字がやがてはAに入り、要求が満たされるからである。

 同値な特徴付け 

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

 K低 

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

を満たすことを言う。ここで、は神託Aに相対化にされた接頭コルモゴロフ複雑性である。

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

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

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

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

K自明集合の特徴付けに関しては、更に多くのものが知られている。例えば、
 弱2ランダム低
 左c.e.差実数低（ここでは、ランダムの概念が使われていないことに注意。）
などである。

 2008年以降の発展 

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

ある集合Yが正密度点であるとは、すべてのYを含む実効的閉集合がYで正の下側ルベール密度を持つことを言う。Bienvenu, Hölzl, Miller, and NiesLaurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies, (2012),  "The Denjoy alternative for computable functions", Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International Proceedings in Informatics, pages 543–554. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.は、マルティンレーフランダムな点に対して、チューリング完全ではないことと正密度点であることの同値性を示した。Day and Miller (2012) J. Miller, A. Day. (2012) "Cupping with random sets", To appear in the Proceedings of the American Mathematical Societyらは、これを使って、ML-cupping問題に対して肯定的な解を与えた。:Miller and Nies, Randomness and computability: Open questions.   Bull. Symb. Logic. 12 no 3 (2006) 390-410すなわち、AがK自明集合であることと、が停止問題を計算するようなすべてのマルティンレーフランダムな点Zに対してZが停止問題を計算する、ということは同値。

Yが一密度点であるとは、すべてのYを含む実効的閉集合がYでルベーグ密度1を持つことを言う。一密度点でないようなどのマルティンレーフランダムな集合でも、すべてのK自明集合を計算する。Bienvenu et al.Bienvenu, Greenberg, Kucera, Nies and Turetsky, "K-Triviality, Oberwolfach Randomness, and Differentiability", 
Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach Preprints (OWP), ISSN 1864-7596
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 Computing K-trivial sets by incomplete random sets.   To appear in Bull. Symbolic Logic.などが参考になるであろう。K自明集合の変種も研究されている。例えば、Schnorr trivial setsは計算可能な測度を持つ機械によって定義される。strongly jump traceable setsはK自明集合族の真部分集合で低の性質を持つものである。

 脚注 

Category:乱数
Category:アルゴリズム的情報理論
Category:数学に関する記事