ブラムの加速定理

複雑性測度 ${\displaystyle (\varphi ,\Phi )}$ と2変数全域再帰的関数 ${\displaystyle f}$ を所与とする。このとき全域再帰的関数 ${\displaystyle g}$ （これはブール値関数にできる）が存在して、${\displaystyle g}$ の任意の指標 ${\displaystyle i}$ に対して、${\displaystyle g}$ の指標 ${\displaystyle j}$ が存在して、ほとんど全ての ${\displaystyle x}$ に対して次が成り立つ：

${\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x)}$

${\displaystyle f}$ は加速関数と呼ばれる。 これを必要なだけ急増加な関数とすれば、 プログラム ${\displaystyle i}$ を与える毎にそれよりも必要なだけ高速なプログラム ${\displaystyle j}$ が得られる。例えば ${\displaystyle f(x,y)=2^{y}}$ とすれば ${\displaystyle j}$ の複雑性は ${\displaystyle O(\log \Phi _{i}(x))}$ である。