圧縮定理
いま部分計算可能関数のアクセプタブル・ナンバリング φ {\displaystyle \varphi } とブラム複雑性測度 Φ {\displaystyle \Phi } を所与とする。このとき上限 f {\displaystyle f} のもとでの複雑性クラスは次のように定義される:
C ( f ) := { φ i ∈ R ( 1 ) | ( ∀ ∞ x ) Φ i ( x ) ≤ f ( x ) } . {\displaystyle \mathrm {C} (f):=\{\varphi _{i}\in \mathbf {R} ^{(1)}|(\forall ^{\infty }x)\,\Phi _{i}(x)\leq f(x)\}.}
このとき全域計算可能関数 f {\displaystyle f} が存在して、任意の指標 i {\displaystyle i} に対して次が成り立つ:
D o m ( φ i ) = D o m ( φ f ( i ) ) , {\displaystyle \mathrm {Dom} (\varphi _{i})=\mathrm {Dom} (\varphi _{f(i)}),}
C ( φ i ) ⊊ C ( φ f ( i ) ) . {\displaystyle \mathrm {C} (\varphi _{i})\subsetneq \mathrm {C} (\varphi _{f(i)}).}