Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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.
