# Is there any language for which a perfect optimization is decidable?

Is there a programming language L where it is possible to write an optimizer O, that, receiving a program in L and a set of cost for every low-level operation in L, returns the equivalent program with the least total cost possible?

Practical example:

(optimize '(* a a) [['* 2] ['pow 1]])


Should return:

(pow a)


For a hypothetical language where '*' and 'sqrt' are the only primitive operations, as the cost of the 'sqrt' operation (1) is lower than the cost of the '*' operation (2).

• Do you want the programming language to be Turing-complete? If so, the answer is clearly "no" (the problem is undecidable). If not, then I'm sure we can come up with trivial examples. Are there any requirements on the expressiveness of L, to make this non-trivial?
– D.W.
Commented Sep 2, 2013 at 6:10
• No. While some trivial examples are easy to come by, I'm interested in useful languages, but it is hard to come by with a good definition of 'usefulness'. Being able to encode most practical programs - as COQ can, despite being not turing-complete - is a good starter. Commented Sep 2, 2013 at 6:24
• Why is it obviously undecidable? Note that there is no requirement that equivalent programs be optimized to the same program, only to programs that run equally fast. Commented Sep 2, 2013 at 7:20
• A trivial note: "in theory" a real computer has a finite amount of memory so every programs (in any programming language) that runs on a fixed reasoanable real hardware is perfectly optimizable ... although a real optimizer would still be running when humanity has already disappeared ... :-) Commented Sep 2, 2013 at 10:27
• @Viclib a suitable language for your purpose might be given by the class of primitive recursive functions. There exist syntactical characterizations, of P and Linspace for example, which use primitive recursion. A starting point would be "A NEW RECURSION-THEORETIC CHARACTERIZATION OF THE POLYTIME FUNCTIONS" by Bellatoni and Cook. Commented Sep 2, 2013 at 14:09

Certainly not for a Turing-complete programming language, following up on D.W. and David's comments. Consider a program in this language that simulates a Turing Machine $M$ (where $M$ is hardcoded into the program) and outputs zero if $M$ halts.

When your optimizer receives such a program where $M$ halts, it must output some least-cost program that always returns zero (because the original program always returns zero). If $M$ doesn't halt, then your optimizer can output any program that runs forever (as the original program always runs forever).

OK, now let's show that your optimizer would allow us to solve the halting problem. Suppose that the statement "return zero" has cost $C$. (Thus, we know that any least-cost program that always returns zero has cost at most $C$.) Given a Turing Machine $M$, construct the program that simulates $M$ and outputs zero if $M$ halts. Feed it to the optimizer. Run the output program for up to total cost (time) $C+1$. If it has output zero, then the original program halts. If not, the original program does not halt.

...I agree with user17410's suggestion to look at the primitive recursive functions as they are likely to be able to cover most problems we want to solve practically.

• just a note: in order to work, all costs should be $\geq 1$. Commented Sep 3, 2013 at 13:13
• @MarzioDeBiasi - good point, or at least $\exists c > 0$ s.t. all costs $> c$. Otherwise I guess there could be some sort of infinite series summing to less than $C$....
– usul
Commented Sep 3, 2013 at 14:03
• Assuming there are only finitely many different instructions (which seems reasonable), all costs positive is enough. Commented Sep 3, 2013 at 14:22

two examples based on a more broad interpretation of your question & the terms in it which are not strictly defined in the question:

• optimiziing FSMs ie finding the minimal FSM eg via Myhill-Nerode theorem. FSMs are indeed "languages" by the technical TCS definition, however whether they are "programming languages" would be a more controversial assertion. the problem is that "programming language" is generally taken to be, or standardly defined as, a Turing-complete language, as pointed out in comments. so that would have to be weakened for your question to have a nontrivial answer (agreeing with the idea that finding optimal programs for Turing complete languages is basically undecidable without further restrictions).

• finding the minimal circuit. circuits map onto languages in the natural way of defining a family of (minimal) circuits $C_n$ for a language, eg as in the definition of P/Poly and other natural "circuit-based complexity classes". a brute force algorithm with "very slow" run time (exponential time or worse) suffices to find a minimal circuit but only for a/each fixed $n$, basically the smallest DAG-connected-gates that is equivalent (in the truth table).

This is undecidable for Turing-powerful languages.

Proof is by reduction from the all-inputs halting problem ("Does Turing Machine $M$ halt for all inputs?"), which is undecidable. Suppose the optimizer $O$ described in the question exists. Given a machine $M$, we can easily produce a machine $Z(M)$ that behaves identically to $M$ except that, whenever it halts, it outputs zero instead of whatever output $M$ was going to give. But, now, $M$ halts on all inputs if, and only if, $Z(M)$ outputs zero for all inputs if, and only if, $O(Z(M))$ is the program that immediately returns zero and halts.

• Small nitpick: I think that's not quite a complete proof, as there might be multiple programs that immediately output zero and halt that all have an equally low cost. My previous answer addresses this.
– usul
Commented Sep 2, 2013 at 22:14
• I was assuming that the program with no instructions has cost zero and is taken to halt with output zero. Also, it's not stated that cost means running time, which your solution seems to require. Commented Sep 2, 2013 at 23:29
• well, I would like that assumption to be WLOG. I think my proof should not require that cost = running time: We can just add to our total the "cost" of each instruction in the program as we execute it (since the cost of each instruction is known), and once we exceed the "cost" of some known zero-outputting program, we know the original machine doesn't halt.
– usul
Commented Sep 3, 2013 at 3:03
• I was worried that a machine could not terminate and still use space less than $C$. But I think you're OK: the optimizer isn't allowed to replace a program that always halts and outputs zero with a program that sometimes doesn't halt. Commented Sep 3, 2013 at 7:50
• Yeah, but as Marzio's comment on the other answer says, I guess there is additional subtlety there and we need some small assumptions.
– usul
Commented Sep 3, 2013 at 14:05