K自明集合
ステージ s > 0 {\displaystyle s>0} においては、それぞれの e < s {\displaystyle e<s} において、もし、 P S e {\displaystyle PS_{e}} が満たされておらず、 x ∈ W e , s ∖ W e , s − 1 {\displaystyle x\in W_{e,s}\backslash W_{e,s-1}} かつ c ( x , s ) ≤ 2 − e {\displaystyle c(x,s)\leq 2^{-e}} を満たすような x ≥ 2 e {\displaystyle x\geq 2e} が存在するなら、 xを A s {\displaystyle A_{s}} に入れて、要求 P S e {\displaystyle PS_{e}} が満たされたと宣言する。構成は以上である。
この構成が実際にうまくいくことを確認しよう。まず、Aはコスト関数に従う。なぜなら、それぞれの要求があるのでAに入る数字は高々1つであって、合計Sは高々
Σ e 2 − e < ∞ {\displaystyle \Sigma _{e}2^{-e}<\infty }
であるからである。次に、それぞれの要求は満たされる。もし、 W e {\displaystyle W_{e}} が無限ならば、コスト関数が極限条件を満たすという事実から、ある数字がやがてはAに入り、要求が満たされるからである。
K自明集合の初期の研究は、主にK自明集合と計算可能集合との分離に焦点が置かれていた。
1976年のチャイティンの論文では、ある自然数bに対して
∀ n C ( A ↾ n ) ≤ C ( n ) + b {\displaystyle \forall nC(A\upharpoonright n)\leq C(n)+b}
が成立するような集合について研究されている。ここで、Cは単純コルモゴロフ複雑性である。そのような集合はC自明集合として知られている。 チャイティンはC自明集合の族が計算可能集合の族と一致することを示した。また、チャイティンはK自明集合が停止問題から計算可能であることも示した。この集合族は算術的階層における Δ 2 0 {\displaystyle \Delta _{2}^{0}} として知られている。
計算不可能なK自明集合の構成に初めて成功したのはソロベイ(英語: Robert_M._Solovay)である。c.e.でのそのような集合は、カルーデ(英語: Cristian S. Calude)、コールズなどによる。未出版であれば、クンマー(Kummer)によるK自明集合の構成や、ムチニクJr.(Muchnik)によるK低集合の構成などがある。