K自明集合
2009年から解析の概念が使われるようになり、よく知られた問題を解くのに一役を担った。
ある集合Yが正密度点であるとは、すべてのYを含む実効的閉集合がYで正の下側ルベール密度を持つことを言う。Bienvenu, Hölzl, Miller, and Niesは、マルティンレーフランダムな点に対して、チューリング完全ではないことと正密度点であることの同値性を示した。Day and Miller (2012) らは、これを使って、ML-cupping問題に対して肯定的な解を与えた。:すなわち、AがK自明集合であることと、 A ⊕ Z {\displaystyle A\oplus Z} が停止問題を計算するようなすべてのマルティンレーフランダムな点Zに対してZが停止問題を計算する、ということは同値。
Yが一密度点であるとは、すべてのYを含む実効的閉集合がYでルベーグ密度1を持つことを言う。一密度点でないようなどのマルティンレーフランダムな集合でも、すべてのK自明集合を計算する。
数学においてある自然数の集合がK自明集合(Kじめいしゅうごう、英: K-trivial set)であるとは、 その始切片(英語: initial segment)を2進文字列と見た時に記述しやすいことを言う。 すなわち、その接頭コルモゴロフ複雑性が可能な限り低く,計算可能集合のそれに近いことを言う。 ソロベイ(英語: Robert_M._Solovay)は1975年に計算不可能なK自明集合の存在を示した。
シュノール・レビンの定理(英語: Schnorr-Levin theorem)によれば、ランダムな集合の始切片は高い複雑性を持つ。 つまり、K自明集合はランダムからかけ離れているということである。 そのため、ランダムネスの理論で研究されており、 計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。
K自明集合は計算可能に近いという性質ももつ。 例えば、それらはすべて超低(英語: superlow)である、つまり、そのチューリングジャンプが停止問題に真理表還元可能である。 また、チューリングイデアル(英語: Turing ideal)を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。