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?


2 Answers 2


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

  • $\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, 2014 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$ Feb 25, 2014 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, 2014 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.


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.