In Andrew W. Appel's book, *Modern Compiler Implementation in ML*, he says under chapter 17 that *Computability theory shows that it will always be possible to invent new optimizing transformations* and proceeds to prove that a *fully optimizing compiler* will solve the alting problem: A program *Q* that produces no output and never halts can easily be replaced by its optimal representation, *Opt(Q)*, being "L: goto L". So a fully optimizing compiler can solve the halting problem.

So my question is this: **Does a fully optimizing compiler exist for terminating programs?** My only thoughts are the following: Even though a program is guaranteed to terminate, it can still be arbitrarily complex, and for any concrete optimizing compiler, C, one could perhaps construct a program that takes C as input and somehow produces a worse program as some kind of corner case.

Also, **What are the implications of restricting ourselves to terminating programs?**