# Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable? [duplicate]

Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable? If not, why not? If yes, how can such a program be realistically constructed?

I would prefer an intuitive explanation over a formal one, thanks.

• What is "a problem"? What would the input to this theoretical program look like? Aug 28 '14 at 12:20
• I mean a problem in the most general sense - it would be the domain of all problems in computer science. The input would be in either natural or formal language. Aug 28 '14 at 12:26
• That's not clear enough. How would you represent such a problem? If it's in natural language, just parsing the input is presumably undecidable. Aug 28 '14 at 12:46
• From what sense I can make from the question (what does it have to do with AI?), the answer has been given before (seems to be the same idea @Shaull proposes).
– Raphael
Aug 28 '14 at 14:14

However, under any reasonable assumption, no such program exists. One way to see this is through context-free languages: assume we can solve your problem even to the very restricted class of context-free languages. Thus, we have a program $P$ that given a grammar $G$, outputs a TM $M$ whose runtime is optimal (which is also not clearly defined, but let's ignore that for now) and recognizes the same language as $G$.
We can use this program $P$ in order to decide, given a CFG $G$, whether $L(G)=\Sigma^*$, by running $P$ and checking if it outputs a TM which is just a single accepting state (which is the only optimal TM under a reasonable optimality definition). Since this problem is undecidable, then $P$ cannot exist.