3
$\begingroup$

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)?
Improve this question
$\endgroup$
8
  • 5
    $\begingroup$ Can we please refer non-research-level questions to cs.stackexchange.com, rather than encourage people by answring them? Thanks! $\endgroup$
    – Andrej Bauer
    Commented Apr 7, 2013 at 17:38
  • $\begingroup$ This question does not appear to be a research-level. I think the question is more suitable for Computer Science which has a broader scope. $\endgroup$
    – Kaveh
    Commented Apr 7, 2013 at 23:46
  • $\begingroup$ @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. $\endgroup$
    – Cyker
    Commented Apr 8, 2013 at 23:38
  • 3
    $\begingroup$ 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! $\endgroup$
    – Andrej Bauer
    Commented Apr 9, 2013 at 12:46
  • 1
    $\begingroup$ see cohen ref eg in this article 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. $\endgroup$
    – vzn
    Commented Apr 10, 2013 at 14:52

2 Answers 2

Reset to default
6
$\begingroup$

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 says that such properties are undecidable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! Does this method also apply to the decision version? That is, deciding whether a program is size-optimal. $\endgroup$
    – Cyker
    Commented Apr 8, 2013 at 23:03
  • $\begingroup$ 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. $\endgroup$
    – Diego Alonso
    Commented Apr 14, 2013 at 17:10
  • $\begingroup$ 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. $\endgroup$
    – Aryeh
    Commented Apr 19, 2013 at 11:57
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is there some variant of this proof that works for decision machines? I don't see immediately how to convert it. $\endgroup$
    – usul
    Commented Apr 7, 2013 at 15:47
  • $\begingroup$ $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. $\endgroup$
    – Cyker
    Commented Apr 8, 2013 at 21:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – gasche
    Commented Apr 9, 2013 at 8:02

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.