Blum's Speedup Theorem

Blum's Speedup Theorem, stated by Manuel Blum in 1967, shows that for any abstract measure of computational complexity there exists a computable function with no single optimal program: for every program computing the function, another program exists computing it with markedly lower complexity, and this speedup can be made arbitrarily large, for example quadratically or exponentially smaller. The theorem means that, unlike for many specific problems, no definitive complexity can be assigned to an arbitrary computable function, since a still-faster program can always in principle be found.