Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
    
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
6  
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
add comment

migrated from cstheory.stackexchange.com Jan 10 '13 at 2:47

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

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

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.