Speed-up theorems

That there exist computations that are arbitrarily computationally reducible was noted in work on the theory of computation in the mid-1960s.