Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language

$$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$

A language is said to be recursive if there exists any rule to determine whether a string belong to language or not. We have a rule here, but the rule itself depends upon an unknown equation. So can we say $L$ is recursive?


If P=NP, then $L = (0+1)^*$ which is regular grammar. Hence, it is recursive.

If P!=NP, then $L = \phi $ which is also a regular grammar. Hence, recursive.

In both the cases, $L$ will be a recursive language.

PS I see a lotta GATE problems these days :D

| cite | improve this answer | |
  • $\begingroup$ Recursive languages have the ability to accept or reject a string. Can u tell me if the language will accept or reject the string 100 $\endgroup$ – alienCoder Feb 25 '14 at 10:56
  • 4
    $\begingroup$ @alienCoder no, but all we have to show is that a Turing Machine that decides the language exists. No matter which case is true, there is a TM to decide it, we just don't know which one it is. $\endgroup$ – Luke Mathieson Feb 25 '14 at 12:24
  • 1
    $\begingroup$ @alienCoder, a language is just a set of strings, it has no abilities nor does it accept or reject anything. An automaton (an idealization of a computer program or machine; in this case a Turing machine) can accept or reject. $\endgroup$ – vonbrand Feb 25 '14 at 16:52

This appears to be a semantic confusion. You are talking about two languages here, both of which are regular, both are recursive, both can be decided. The question we currently cannot answer is whether the label $L$ applies to the empty language or the language $(0 + 1)^*$, but that has no bearing at all on whether the label refers to a language that is recursive. Languages aren't labels (like $L$) they are sets of strings.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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