K自明集合
Kを接頭コルモゴロフ複雑性とする、 すなわち、ある文字列xに対して、K(x)を接頭普遍機械のもとでxを出力する入力の最小の長さとする。 そのような機械は、直感的には、普遍的なプログラム言語で、有効なプログラムにさらに文字列を付け加えたものは有効でないようなものを表している。 Kに関する背景としては、例えばチャイティンの定数などがある。
自然数の集合Aが自然数の定数bによりK自明集合であるとは、
∀ n K ( A ↾ n ) ≤ K ( n ) + b {\displaystyle \forall nK(A\upharpoonright n)\leq K(n)+b}
が成立することを言う。
ある集合がK自明集合であるとは、ある定数によりK自明であることを言う。