K自明集合のソースを表示

[[数学]]においてある自然数の集合が'''K自明集合'''（Kじめいしゅうごう、{{lang-en-short|K-trivial set}}）であるとは、
その{{日本語版にない記事リンク|始片|en|initial segment|label=始切片}}を2進文字列と見た時に記述しやすいことを言う。
すなわち、その[[コルモゴロフ複雑性|接頭コルモゴロフ複雑性]]が可能な限り低く，[[計算可能関数|計算可能集合]]のそれに近いことを言う。
{{日本語版にない記事リンク|ソロベイ|en|Robert_M._Solovay}}は1975年に計算不可能なK自明集合の存在を示した。

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

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

== 定義 ==

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

[[自然数の集合]]''A''が自然数の定数''b''により'''K自明集合'''であるとは、
:<math>\forall n K(A\upharpoonright n)\leq K(n)+b </math>
が成立することを言う。

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

== 歴史と発展 ==

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

1976年の[[グレゴリー・チャイティン|チャイティン]]の論文<ref>Gregory J. Chaitin (1976),
    "Information-Theoretic Characterizations of Recursive Infinite Strings",
    Theoretical Computer Science
Volume 2, Issue 1, June 1976, Pages 45–48</ref>では、ある自然数''b''に対して
:<math> \forall n C(A\upharpoonright n)\leq C(n)+b</math>
が成立するような集合について研究されている。ここで、''C''は[[コルモゴロフ複雑性|単純コルモゴロフ複雑性]]である。そのような集合は'''C自明集合'''として知られている。
チャイティンはC自明集合の族が計算可能集合の族と一致することを示した。また、チャイティンはK自明集合が[[停止問題]]から計算可能であることも示した。この集合族は[[算術的階層]]における<math>\Delta_2^0</math>として知られている。

計算不可能なK自明集合の構成に初めて成功したのは{{日本語版にない記事リンク|ソロベイ|en|Robert_M._Solovay}}である。[[帰納的可算集合|c.e.]]でのそのような集合は、{{日本語版にない記事リンク|カルーデ|en|Cristian S. Calude}}、コールズ<ref>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</ref>などによる。未出版であれば、クンマー（Kummer）によるK自明集合の構成や、ムチニクJr.（Muchnik）による''K''低集合の構成などがある。

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

計算可能性理論の文脈において、'''コスト関数'''とは計算可能関数で
:<math>c: \mathbb{N}\times\mathbb{N}\to \mathbb{Q}^{\geq 0}</math>
を満たすものを言う。ある<math>\Delta_2^0</math>集合''A''の計算可能な近似<math>\langle A_s \rangle</math>に対し、上記の関数はステージ''s''で''A(n)''の近似を変化させるコスト''c(n,s)''を測っている。最初の[[コスト関数]]の構成はクチェラとテルワインによる<ref name=Antonin>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</ref>。彼らは[[帰納的可算集合|c.e.]]集合で[[アルゴリズム的ランダムな無限列|マルティンレーフランダム]]低だが計算可能ではないものを構成した。ここで、コスト関数は作られる<math>\Delta_2^0</math>集合の計算可能な近似に依存している。[[帰納的可算集合|c.e.]]だが計算可能ではないK自明集合のコスト関数に依る構成が初めて世に出たのはDowney et al.の論文による<ref>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
</ref>。

<math>\Delta_2^0</math>集合''A''がコスト関数''c''に'''従う'''とは、''A''の計算可能な近似<math>\langle A_s: s\in \omega\rangle</math>が存在して、<math>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</math>
を満たすことを言う。K自明集合は以下で定義される標準コスト関数に従う集合として特徴付けられる<ref name="AndreNies">André Nies, (2005), "Lowness properties and randomness", ''Advances in Mathematics'', Volume 197, Issue 1, 20 October 2005, Pages 274–305</ref>。
:<math>c_K (x,s)=\Sigma_{x < y\leq s} 2^{-K_s(x)}</math>
ここで、<math>K_s(x)=\min \{|\sigma|: \mathbb{U}_s(\sigma)=x\}</math>であり、<math>\mathbb{U}_s</math>はある固定した普遍接頭機械<math>\mathbb{U}</math>の計算可能近似における''s''ステップである。

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

実は、その集合は[[promptly simple]]に取ることもできる。証明のアイディアは[[prompt simple]]集合を作る際の要求
:<math>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]</math>
を満たしながら、コストを小さくするというものである。ただしコスト関数は以下の'''極限条件'''を満たす必要がある。
:<math>\lim_x \sup_{s>x}c(x,s)=0</math>
つまり、''x''が増えるにしたがって、''s''がステージを走るときの''x''のコストの上限が''0''に収束する。例えば、標準コスト関数はこの性質を満たす。構成の本質的なアイディアとしては、[[prompt simple]]集合を作る要求を満たすために、''A''に数字を入れる前に、コストが十分小さくなるまで待つというものである。計算可能な枚挙<math>\langle A_s: s\in\omega\rangle</math>を以下のように定義しよう。まず、<math>A_0=\emptyset</math>。ステージ<math>s>0</math>においては、それぞれの<math>e<s</math>において、もし、<math>PS_e</math>が満たされておらず、<math>x\in W_{e,s}\backslash W_{e,s-1}</math>かつ<math>c(x,s)\leq 2^{-e}</math>を満たすような<math>x\ge 2e</math>が存在するなら、
''x''を<math>A_s</math>に入れて、要求<math>PS_e</math>が満たされたと宣言する。構成は以上である。

この構成が実際にうまくいくことを確認しよう。まず、''A''はコスト関数に従う。なぜなら、それぞれの要求があるので''A''に入る数字は高々1つであって、合計''S''は高々
:<math>\Sigma_e 2^{-e} < \infty</math>
であるからである。次に、それぞれの要求は満たされる。もし、<math>W_e</math>が無限ならば、コスト関数が極限条件を満たすという事実から、ある数字がやがては''A''に入り、要求が満たされるからである。

==== 同値な特徴付け ====

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

===== ''K''低 =====

''A''が'''''K''低'''とは、ある自然数''b''が存在して、
:<math>   \forall n K^A(n)+b \geq K(n) </math>
を満たすことを言う。ここで、<math> K^A</math>は神託''A''に相対化にされた接頭コルモゴロフ複雑性である。

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

''A''が'''マルティンレーフランダム低'''<ref name=Antonin/>であるとは、''Z''が[[アルゴリズム的ランダムな無限列|マルティンレーフランダム]]であれば、''A''から相対的にもマルティンレーフランダムであることを言う。

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

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

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

=== 2008年以降の発展 ===

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

ある集合''Y''が'''正密度点'''であるとは、すべての''Y''を含む実効的閉集合が''Y''で正の下側ルベール密度を持つことを言う。Bienvenu, Hölzl, Miller, and Nies<ref>Laurent 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.
</ref>は、マルティンレーフランダムな点に対して、チューリング完全ではないことと正密度点であることの同値性を示した。Day and Miller (2012) <ref>J. Miller, A. Day. (2012) "Cupping with random sets", To appear in the Proceedings of the American Mathematical Society</ref>らは、これを使って、ML-cupping問題に対して肯定的な解を与えた。:<ref name=Miller>Miller and Nies, Randomness and computability: Open questions.   Bull. Symb. Logic. 12 no 3 (2006) 390-410</ref>すなわち、''A''が''K''自明集合であることと、<math>A\oplus Z</math>が停止問題を計算するようなすべてのマルティンレーフランダムな点''Z''に対して''Z''が停止問題を計算する、ということは同値。

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

== 脚注 ==
{{reflist}}

{{デフォルトソート:Kけいしめいしゆうこう}}
[[Category:乱数]]
[[Category:アルゴリズム的情報理論]]
[[Category:数学に関する記事]]