布卢姆加速定理

给定布卢姆复杂度衡量${\displaystyle (\varphi ,\Phi )}$ 和二元全可计算函数${\displaystyle f}$ ，必有全可计算谓词${\displaystyle g}$ （即输出只能为布尔值${\displaystyle 0,1}$ 的全可计算函数），使得对于${\displaystyle g}$ 的每个程序${\displaystyle i}$ ，都有${\displaystyle g}$ 的另一个程序${\displaystyle j}$ ，使得对几乎所有输入${\displaystyle x}$ ，都有

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

粗略而言，上式表明存在程序${\displaystyle j}$ ，使其复杂度${\displaystyle \Phi _{j}(x)}$ 比程序${\displaystyle i}$ 的复杂度${\displaystyle \Phi _{i}(x)}$ 更小，且可以远远更小（“远远”的含义由${\displaystyle f}$ 指定）。${\displaystyle f}$ 称为加速函数，它可以很大（只需可计算）。例如，若取${\displaystyle f(x,y)=2^{y}}$ ，则${\displaystyle j}$ 的复杂度很小，为${\displaystyle O(\log \Phi _{i}(x))}$ 。

• 哥德尔加速定理（英语：Gödel's speed-up theorem）

• Blum, Manuel. A Machine-Independent Theory of the Complexity of Recursive Functions (PDF). Journal of the ACM. 1967, 14 (2): 322–336 [2021-08-09]. doi:10.1145/321386.321395. （原始内容存档 (PDF)于2016-01-15）. 
• Van Emde Boas, Peter. Bečvář, Jiří , 编. Ten years of speedup. Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Mariánské Lázně, September 1-5, 1975. Lecture Notes in Computer Science (Springer-Verlag). 1975, 32: 13–29. doi:10.1007/3-540-07389-2_179. .

• 埃里克·韦斯坦因. Blum's Speed-Up Theorem. MathWorld.