<p>In your example, you consider a size optimizer, that is a program that </p>

<blockquote>
  <p>takes a program $P$, and returns an equivalent program $P'$ such that there is no other program $P''$ also equivalent to $P$ but strictly smaller than $P'$.</p>
</blockquote>

<p>With such a perfect size optimizer, you could build a decision procedure for this question</p>

<blockquote>
  <p>Is an input program $P$ equivalent to any program of at most $33$ characters? </p>
</blockquote>

<p>But this is a non trivial property of program semantics. <a href="http://en.wikipedia.org/wiki/Rice_theorem">Rice Theorem</a> says that such properties are undecidable. </p>

CC BY-SA 3.0
2013-04-08T23:03:39.420Z
Thanks! Does this method also apply to the decision version? That is, deciding whether a program is size-optimal.
Cyker
CC BY-SA 3.0
2013-04-14T17:10:53.913Z
Rice Theorem says that ANY question about program Semantics that is non-trivial is not decidable.


Trivial means all in or all out, in which case the property is decided by "return true" or "return false". 


Semantic equivalence between problems, the question
¿is a program P equivalent to a program Q?
is non-decidable, since for any fixed Q, 
"being equivalent to Q" is non-trivial.

The question "is this program size-optimal?" is also non-trivial, since you have size-optimal and size-not-optimal programs.
Diego Alonso
CC BY-SA 3.0
2013-04-19T11:57:24.580Z
Rice's theorem only applies to encoding-independent properties of RE languages (i.e., "is this language regular" but NOT "is this program minimal") -- so I don't think you can use it here.
Aryeh
CC BY-SA 3.0
2013-04-07T13:38:17.430Z
2013-04-07T13:38:17.430Z
Diego Alonso
<p>Let <code>fill</code> be the Turing machine that writes <code>1</code> on all positions of its output tape (it doesn't terminate, but that's not an issue). Let now <code>syra</code> be the machine that computes the <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="nofollow">Syracuse/Collatz sequence</a> for all <code>n</code> successively, and for each writes <code>1</code> in the <code>n</code>-th output position if the sequence goes back to a <code>1</code>. Now test if <code>M1(fill)</code> is equal to <code>M1(syra)</code>, and you've answered the Collatz conjecture.</p>

<p>Similarly, you can check the halting problem for any turing machine <code>M</code> by just turning it into the machine that writes <code>1</code> on the whole output tape after it normal function has terminated, and then comparing that to <code>fill</code>.</p>

CC BY-SA 3.0
2013-04-07T15:47:28.413Z
Is there some variant of this proof that works for decision machines? I don't see immediately how to convert it.
usul
CC BY-SA 3.0
2013-04-08T21:27:44.497Z
$EQ_{TM}$ is a well-known undecidable problem. But I don't quite see how it implies the TM $M_1$ in this question doesn't exist. The shortest program may not be unique.
Cyker
CC BY-SA 3.0
2013-04-09T08:02:41.970Z
@cyker to test unicity of two TMs provided your size compressor, define the machine that runs the first, then the second, then compare their results and puts all 0 if they're distinct, and leave it alone otherwise. Size-compress this new machine. If it's either of the input, they were equal to begin with. If it has a different size, they were distinct. If it's different but of the same length, repeat the comparison between this machine and one of the previous ones. This terminates as there is only a finite number of possible TMs of this size.
gasche
CC BY-SA 3.0
2013-04-07T07:37:56.537Z
2013-04-07T07:37:56.537Z
gasche
<p>A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that:</p>

<blockquote>
  <p>On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is equivalent to $M$.</p>
</blockquote>

<p>If size-optimization is not computable, the above $M_1$ shouldn't exist. </p>

<ol>
<li>How do we prove this? </li>
<li>Does this also mean a size-optimality decider can't exist?</li>
<li>How does this generalize to other kinds of optimization (speed-optimization, for example)?</li>
</ol>

CC BY-SA 3.0
2013-04-07T17:38:05.353Z
Can we please refer non-research-level questions to http://cs.stackexchange.com/, rather than encourage people by answring them? Thanks!
Andrej Bauer
CC BY-SA 3.0
2013-04-07T23:46:20.793Z
This question does not appear to be a research-level. I think the question is more suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-04-08T23:38:33.803Z
@AndrejBauer Well, I don't always know whether a problem is too easy or too hard. Sometimes they look the same. I don't encourage people to answer them. Those who like it just answer it. Those who don't like it can feel free to vote down.
Cyker
CC BY-SA 3.0
2013-04-09T12:46:52.190Z
As a rule of thumb, if you do not know whether something is a research-level question then it is not a research-level question, especially if you are not a researcher in the particular area of your question. So, you ask on a general forum first, and if all is silent, then you ask here. Good luck!
Andrej Bauer
CC BY-SA 3.0
2013-04-09T22:27:44.187Z
@AndrejBauer If the questions can be answered in the general forum perhaps I won't bother you guys here. They're not homework-level questions (at least I haven't found them in any homeworks). I've searched for related papers but didn't find anything useful. If you define research-level as conducive to a publishable result, perhaps they're not at that level. They are just a little bit interdisplinary. If you think they're too old or too obvious, just put a simple answer and that won't take too much time. If it ever takes you too much time, then they're not that simple, right?
Cyker
CC BY-SA 3.0
2013-04-10T02:13:58.127Z
fyi a somewhat similar question, the undecidability of consistent virus checkers was a proof published in a mathematical journal years ago.
vzn
CC BY-SA 3.0
2013-04-10T06:37:46.597Z
@vzn It'd be interesting to see how they define a virus if you have the link. BTW, do you have any idea on the existence of a size-optimality decider?
Cyker
CC BY-SA 3.0
2013-04-10T14:52:21.890Z
see cohen ref eg in this article [Can Viruses Be Detected?](http://www.symantec.com/connect/articles/can-viruses-be-detected). the apparent reference is "Fred Cohen, "Computer Viruses: Theory and Experiments", Computers and Security 6 (1987) 22-35". these are all basically variations of Rices thm & diagonalization, suggest you study that thm.
vzn
<pl.programming-languages><optimization>
Undecidability of program optimization
Cyker
# Undecidability of program optimization

(Asked by: username_0 on 2013-04-07)

A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M\_1$ such that:

> On any input $M$, $M\_1$ outputs $M\_{min}$ such that $M\_{min}$ is the shortest TM which is equivalent to $M$.

If size-optimization is not computable, the above $M\_1$ shouldn't exist.

1. How do we prove this?
2. Does this also mean a size-optimality decider can't exist?
3. How does this generalize to other kinds of optimization (speed-optimization, for example)?

**Tags:** pl.programming-languages, optimization

> **Comments:**
> **username_1**: Can we please refer non-research-level questions to http://cs.stackexchange.com/, rather than encourage people by answring them? Thanks!  
> **username_2**: This question does not appear to be a research-level. I think the question is more suitable for [cs.se] which has a broader scope.  
> **username_0**: @AndrejBauer Well, I don't always know whether a problem is too easy or too hard. Sometimes they look the same. I don't encourage people to answer them. Those who like it just answer it. Those who don't like it can feel free to vote down.  
> **username_1**: As a rule of thumb, if you do not know whether something is a research-level question then it is not a research-level question, especially if you are not a researcher in the particular area of your question. So, you ask on a general forum first, and if all is silent, then you ask here. Good luck!  
> **username_0**: @AndrejBauer If the questions can be answered in the general forum perhaps I won't bother you guys here. They're not homework-level questions (at least I haven't found them in any homeworks). I've searched for related papers but didn't find anything useful. If you define research-level as conducive to a publishable result, perhaps they're not at that level. They are just a little bit interdisplinary. If you think they're too old or too obvious, just put a simple answer and that won't take too much time. If it ever takes you too much time, then they're not that simple, right?  
> **username_3**: fyi a somewhat similar question, the undecidability of consistent virus checkers was a proof published in a mathematical journal years ago.  
> **username_0**: @username_3 It'd be interesting to see how they define a virus if you have the link. BTW, do you have any idea on the existence of a size-optimality decider?  
> **username_3**: see cohen ref eg in this article [Can Viruses Be Detected?](http://www.symantec.com/connect/articles/can-viruses-be-detected). the apparent reference is "Fred Cohen, "Computer Viruses: Theory and Experiments", Computers and Security 6 (1987) 22-35". these are all basically variations of Rices thm & diagonalization, suggest you study that thm.  

---

## 2 answers

### Answer by username_4 on 2013-04-07. Score: 6 | Accepted answer

In your example, you consider a size optimizer, that is a program that

> takes a program $P$, and returns an equivalent program $P'$ such that there is no other program $P''$ also equivalent to $P$ but strictly smaller than $P'$.

With such a perfect size optimizer, you could build a decision procedure for this question

> Is an input program $P$ equivalent to any program of at most $33$ characters?

But this is a non trivial property of program semantics. [Rice Theorem](http://en.wikipedia.org/wiki/Rice_theorem) says that such properties are undecidable.

> **Comments:**
> **username_0**: Thanks! Does this method also apply to the decision version? That is, deciding whether a program is size-optimal.  
> **username_4**: Rice Theorem says that ANY question about program Semantics that is non-trivial is not decidable.   Trivial means all in or all out, in which case the property is decided by "return true" or "return false".    Semantic equivalence between problems, the question ¿is a program P equivalent to a program Q? is non-decidable, since for any fixed Q,  "being equivalent to Q" is non-trivial.  The question "is this program size-optimal?" is also non-trivial, since you have size-optimal and size-not-optimal programs.  
> **username_5**: Rice's theorem only applies to encoding-independent properties of RE languages (i.e., "is this language regular" but NOT "is this program minimal") -- so I don't think you can use it here.  

---

### Answer by username_6 on 2013-04-07. Score: 4

Let `fill` be the Turing machine that writes `1` on all positions of its output tape (it doesn't terminate, but that's not an issue). Let now `syra` be the machine that computes the [Syracuse/Collatz sequence](http://en.wikipedia.org/wiki/Collatz_conjecture) for all `n` successively, and for each writes `1` in the `n`-th output position if the sequence goes back to a `1`. Now test if `M1(fill)` is equal to `M1(syra)`, and you've answered the Collatz conjecture.

Similarly, you can check the halting problem for any turing machine `M` by just turning it into the machine that writes `1` on the whole output tape after it normal function has terminated, and then comparing that to `fill`.

> **Comments:**
> **username_7**: Is there some variant of this proof that works for decision machines? I don't see immediately how to convert it.  
> **username_0**: $EQ_{TM}$ is a well-known undecidable problem. But I don't quite see how it implies the TM $M_1$ in this question doesn't exist. The shortest program may not be unique.  
> **username_6**: @cyker to test unicity of two TMs provided your size compressor, define the machine that runs the first, then the second, then compare their results and puts all 0 if they're distinct, and leave it alone otherwise. Size-compress this new machine. If it's either of the input, they were equal to begin with. If it has a different size, they were distinct. If it's different but of the same length, repeat the comparison between this machine and one of the previous ones. This terminates as there is only a finite number of possible TMs of this size.  

---

