Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If a language is defined such that
$L = (0+1)^{\ast}$ if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$ otherwise

Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the empty langauge. Therefore $\mathsf{P} = \mathsf{NP}$ , $L$ is recursive (being regular), but is $L$ still recursive if $\mathsf{P} \neq \mathsf{NP}$?

share|cite|improve this question

migrated from Jan 10 '13 at 2:47

This question came from our site for theoretical computer scientists and researchers in related fields.

Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. We have migrated your question to Computer Science which has a broader scope. – Kaveh Jan 10 '13 at 2:47
In both cases L is regular ans thus recursive. – Ran G. Jan 10 '13 at 4:22
@Ran G. Turn into an answer? – Yuval Filmus Jan 10 '13 at 11:35

The language $L = \emptyset$ is indeed a recursive set.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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