<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>...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.</p>

CC BY-SA 3.0
2013-09-03T13:13:09.290Z
just a note: in order to work, all costs should be $\geq 1$.
Marzio De Biasi
CC BY-SA 3.0
2013-09-03T14:03:59.573Z
@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
CC BY-SA 3.0
2013-09-03T14:22:41.917Z
Assuming there are only finitely many different instructions (which seems reasonable), all costs positive is enough.
David Richerby
CC BY-SA 3.0
2013-09-02T16:29:41.607Z
2013-09-02T16:29:41.607Z
usul
<p>two examples based on a more broad interpretation of your question &amp; the terms in it which are not strictly defined in the question:</p>

<ul>
<li><p>optimiziing FSMs ie finding the minimal FSM eg via <a href="http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem" rel="nofollow">Myhill-Nerode theorem</a>. FSMs are indeed <a href="http://en.wikipedia.org/wiki/Regular_language" rel="nofollow">"languages"</a> 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).</p></li>
<li><p>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 <a href="http://en.wikipedia.org/wiki/P/poly" rel="nofollow">P/Poly</a> 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 <em>but only for a/each fixed $n$</em>, basically the smallest DAG-connected-gates that is equivalent (in the <a href="http://en.wikipedia.org/wiki/Truth_table" rel="nofollow">truth table</a>).</p></li>
</ul>

CC BY-SA 3.0
2013-09-02T15:44:59.877Z
2013-09-02T15:44:59.877Z
vzn
<p>This is undecidable for Turing-powerful languages.</p>

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

CC BY-SA 3.0
2013-09-02T22:14:18.363Z
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
CC BY-SA 3.0
2013-09-02T23:29:49.850Z
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.
David Richerby
CC BY-SA 3.0
2013-09-03T03:03:31.733Z
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
CC BY-SA 3.0
2013-09-03T07:50:52.893Z
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.
David Richerby
CC BY-SA 3.0
2013-09-03T14:05:18.017Z
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
CC BY-SA 3.0
2013-09-02T19:49:36.517Z
2013-09-03T11:21:45.343Z
2013-09-03T11:21:45.343Z
David Richerby
<p>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?</p>

<p>Practical example:</p>

<pre><code>(optimize '(* a a) [['* 2] ['pow 1]])
</code></pre>

<p>Should return:</p>

<pre><code>(pow a)
</code></pre>

<p>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).</p>

CC BY-SA 3.0
2013-09-02T06:10:13.600Z
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.
CC BY-SA 3.0
2013-09-02T06:24:21.053Z
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.
MaiaVictor
CC BY-SA 3.0
2013-09-02T07:20:41.143Z
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.
Andrej Bauer
CC BY-SA 3.0
2013-09-02T08:17:48.923Z
@Andrej, It's undecidable if a program always returns zero so it's undecidable whether the output of the optimizer should just be the empty program.
David Richerby
CC BY-SA 3.0
2013-09-02T10:27:08.983Z
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 ... :-)
Marzio De Biasi
CC BY-SA 3.0
2013-09-02T14:09:10.123Z
@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.
John D.
CC BY-SA 3.0
2013-09-02T14:57:03.597Z
@David: sorry, I do not follow your logic. Could you write a proper answer to the question which explains why this is undecidable for Turing machines? I think that would already be useful to have.
Andrej Bauer
CC BY-SA 3.0
2013-09-03T13:10:14.010Z
A clarification: suppose your language has an instruction **while (<cond>) do {<block>}** of cost 1; what is the cost (in your interpretation) of the endless program P: **while(1) do { }** ? Is it infinite or 1 ?
Marzio De Biasi
<pl.programming-languages>
Is there any language for which a perfect optimization is decidable?
MaiaVictor
# Is there any language for which a perfect optimization is decidable?

(Asked by: username_0 on 2013-09-02)

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).

**Tags:** pl.programming-languages
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: @Andrej, It's undecidable if a program always returns zero so it's undecidable whether the output of the optimizer should just be the empty program.  
> **username_4**: 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 ... :-)  
> **username_5**: @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.  
> **username_2**: @David: sorry, I do not follow your logic. Could you write a proper answer to the question which explains why this is undecidable for Turing machines? I think that would already be useful to have.  
> **username_4**: A clarification: suppose your language has an instruction **while (<cond>) do {<block>}** of cost 1; what is the cost (in your interpretation) of the endless program P: **while(1) do { }** ? Is it infinite or 1 ?  

---

## 3 answers

### Answer by username_6 on 2013-09-02. Score: 4

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.

> **Comments:**
> **username_4**: just a note: in order to work, all costs should be $\geq 1$.  
> **username_6**: @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$....  
> **username_3**: Assuming there are only finitely many different instructions (which seems reasonable), all costs positive is enough.  

---

### Answer by username_7 on 2013-09-02. Score: 2

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](http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem). FSMs are indeed ["languages"](http://en.wikipedia.org/wiki/Regular_language) 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Truth_table)).


---

### Answer by username_3 on 2013-09-02. Score: 0

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.

> **Comments:**
> **username_6**: 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.  
> **username_3**: 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.  
> **username_6**: 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.  
> **username_3**: 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.  
> **username_6**: Yeah, but as Marzio's comment on the other answer says, I guess there is additional subtlety there and we need some small assumptions.  

---

