K自明集合
t. A s − 1 ( x ) ≠ A s ( x ) ] < ∞ {\displaystyle 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 } を満たすことを言う。K自明集合は以下で定義される標準コスト関数に従う集合として特徴付けられる。
c K ( x , s ) = Σ x < y ≤ s 2 − K s ( x ) {\displaystyle c_{K}(x,s)=\Sigma _{x<y\leq s}2^{-K_{s}(x)}}
ここで、 K s ( x ) = min { | σ | : U s ( σ ) = x } {\displaystyle K_{s}(x)=\min\{|\sigma |:\mathbb {U} _{s}(\sigma )=x\}} であり、 U s {\displaystyle \mathbb {U} _{s}} はある固定した普遍接頭機械 U {\displaystyle \mathbb {U} } の計算可能近似におけるsステップである。