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.
4
-
$\begingroup$ What is "a problem"? What would the input to this theoretical program look like? $\endgroup$– ShaullCommented Aug 28, 2014 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$– user2108462Commented Aug 28, 2014 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$– ShaullCommented Aug 28, 2014 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$– RaphaelCommented Aug 28, 2014 at 14:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\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$ Commented Aug 28, 2014 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$– ShaullCommented Aug 28, 2014 at 13:42
-
1$\begingroup$ Great answer, despite the question not being completely clear. $\endgroup$ Commented Aug 28, 2014 at 13:53