Undecidability of program optimization A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that:


  On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is equivalent to $M$.


If size-optimization is not computable, the above $M_1$ shouldn't exist. 


How do we prove this? 
Does this also mean a size-optimality decider can't exist?
How does this generalize to other kinds of optimization (speed-optimization, for example)?
In your example, you consider a size optimizer, that is a program that 


  takes a program $P$, and returns an equivalent program $P'$ such that there is no other program $P''$ also equivalent to $P$ but strictly smaller than $P'$.


With such a perfect size optimizer, you could build a decision procedure for this question


  Is an input program $P$ equivalent to any program of at most $33$ characters? 


But this is a non trivial property of program semantics. Rice Theorem says that such properties are undecidable.