Optimization is not only rearranging instructions. You can make a program of twice the size that runs twice as fast but does the same computation. There is no u

Optimization is not only rearranging instructions. You can make a program of twice the size that runs twice as fast but does the same computation. There is no upper bound. But even so, minimizing the program size is uncomputable as well. Given a Turing Machine M, create a program P(i) that simulates M for i steps and return true if the machine reaches an accepting state. If you provide an optimizing program OPT, then OPT(P) would be "return false;" if and only M does not halt. I.e. the optimizer would solve the halting problem which we know is not possible.