ブラムの加速定理
複雑性測度 ( φ , Φ ) {\displaystyle (\varphi ,\Phi )} と2変数全域再帰的関数 f {\displaystyle f} を所与とする。このとき全域再帰的関数 g {\displaystyle g} (これはブール値関数にできる)が存在して、 g {\displaystyle g} の任意の指標 i {\displaystyle i} に対して、 g {\displaystyle g} の指標 j {\displaystyle j} が存在して、ほとんど全ての x {\displaystyle x} に対して次が成り立つ:
f ( x , Φ j ( x ) ) ≤ Φ i ( x ) {\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x)}
f {\displaystyle f} は加速関数と呼ばれる。 これを必要なだけ急増加な関数とすれば、 プログラム i {\displaystyle i} を与える毎にそれよりも必要なだけ高速なプログラム j {\displaystyle j} が得られる。例えば f ( x , y ) = 2 y {\displaystyle f(x,y)=2^{y}} とすれば j {\displaystyle j} の複雑性は O ( log  Φ i ( x ) ) {\displaystyle O(\log \Phi _{i}(x))} である。