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?

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 halting 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?