2
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by David Richerby, Raphael Aug 28 '14 at 14:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What is "a problem"? What would the input to this theoretical program look like? $\endgroup$ – Shaull Aug 28 '14 at 12:20
  • $\begingroup$ 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. $\endgroup$ – user2108462 Aug 28 '14 at 12:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Shaull Aug 28 '14 at 12:46
  • $\begingroup$ 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). $\endgroup$ – Raphael Aug 28 '14 at 14:14
4
$\begingroup$

As discussed in the comments, the question is not well-defined, since it's unclear what the input is.

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.

$\endgroup$
  • $\begingroup$ Given L(G), can you always create a turing machine that recognizes it? that means you would be able to solve the undecidable problem of whether if, given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules? $\endgroup$ – user2108462 Aug 28 '14 at 13:35
  • $\begingroup$ Yes, every CFG has an equivalent deciding TM, and yes, it's undecidable whether the language of a CFG is every string. $\endgroup$ – Shaull Aug 28 '14 at 13:42
  • 1
    $\begingroup$ Great answer, despite the question not being completely clear. $\endgroup$ – Patrick87 Aug 28 '14 at 13:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.