20
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It is hard to even find the optimal instruction sequence for a single block of code with no control flow at all. The superoptimization article on Wikipedia gives a good intro (with citations.) $\endgroup$
    – Wandering Logic
    Commented Jul 17, 2013 at 12:38
  • $\begingroup$ The Wikipedia article mentions that superoptimization looks at loop-free sequences of instructions. Having no loops, I suppose, is another way of saying that it terminates. From looking briefly at the available references, it appears to be possible but extremely expensive. $\endgroup$
    – sshine
    Commented Jul 17, 2013 at 13:52
  • 3
    $\begingroup$ What is the meaning of "optimise" here? Smaller runtime? If so, which: worst-case, average-case, every-case, some-case, ...? $\endgroup$
    – Raphael
    Commented Jul 17, 2013 at 14:22

1 Answer 1

Reset to default
19
$\begingroup$

I assume you are interested in optimisation of runtime. As I've written in my comment, that does not sufficiently specify the goal: does an optimisation reduce runtime on any input, every input, all worst-case inputs or even on average?

I will show that all of them are impossible. The proof extends to optimising the length of the program.

Recall that the following problem is not computable:

Given a context-free grammar $G$ with terminal alphabet $\Sigma$, decide whether $\mathcal{L}(G) = \Sigma^*$.

Note furthermore that given a context-free grammar $G$, we can hardcode, say, the CYK algorithm for that one grammar; denote this algorithm by $\mathrm{CYK}_G$. We observe that $\mathrm{CYK}_G$ terminates for all inputs (from $\Sigma^*$).

Now assume that there is an optimiser $\operatorname{Opt}$ which, given an always terminating algorithm $A$, outputs a result-equivalent algorithm which is optimal with respect to runtime. Clearly,

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'} \iff \mathcal{L}(G) = \Sigma^*$

and we have thus constructed a decider for an uncomputable problem, contradicting the assumption.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for this argument. A few clarifying questions: What is $\Sigma*$? I assume $\mathcal{L}(G)$ is the language generated by grammar $G$. $\endgroup$
    – sshine
    Commented Jul 18, 2013 at 16:24
  • 6
    $\begingroup$ @Simon: $\Sigma^{\ast}$ is the set of all words. Raphael: Nice proof. In fact you do not need context-free grammars; instead, given a Turing machine $M$ you can create a program $\mathrm{P}_M(i)$ that simulates $M$ for $i$ steps and returns true if the machine reaches an accepting state. Then $\operatorname{OPT}(\mathrm{P}_M)$ would be $\text{'}\mathtt{return\ false;}\text{'}$ iff $M$ does not halt. $\endgroup$
    – sdcvvc
    Commented Jul 18, 2013 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.