K自明集合
計算可能性理論の文脈において、コスト関数とは計算可能関数で
c : N × N → Q ≥ 0 {\displaystyle c:\mathbb {N} \times \mathbb {N} \to \mathbb {Q} ^{\geq 0}}
を満たすものを言う。ある Δ 2 0 {\displaystyle \Delta _{2}^{0}} 集合Aの計算可能な近似 ⟨ A s ⟩ {\displaystyle \langle A_{s}\rangle } に対し、上記の関数はステージsでA(n)の近似を変化させるコストc(n,s)を測っている。最初のコスト関数の構成はクチェラとテルワインによる。彼らはc.e.集合でマルティンレーフランダム低だが計算可能ではないものを構成した。ここで、コスト関数は作られる Δ 2 0 {\displaystyle \Delta _{2}^{0}} 集合の計算可能な近似に依存している。c.e.だが計算可能ではないK自明集合のコスト関数に依る構成が初めて世に出たのはDowney et al.の論文による。
Δ 2 0 {\displaystyle \Delta _{2}^{0}} 集合Aがコスト関数cに従うとは、Aの計算可能な近似 ⟨ A s : s ∈ ω ⟩ {\displaystyle \langle A_{s}:s\in \omega \rangle } が存在して、 S = Σ x , s c ( x , s ) [ x < s ∧ x is the least s.