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.

Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable?

If some other language $S$ and its complement $\overline{S}$ are both recognizable, then $S$ and $\overline{S}$ are decidable. If $\overline{S}$ is unrecognizable, then then $S$ is undecidable but still recognizable. Why do we ignore the idea that $S$ and $\overline{S}$ may both be unrecognizable? This implies that $\exists! s \in S \cup \overline{S} = \Sigma^*$ on which no machine halts, otherwise I don't see why we cannot have $x,y \in \Sigma^*$ and $x \neq y$ such that no machine halts on $x$ or $y$, where $x \in S$ and $y \in \overline{S}$.

Perhaps I am making a false assumption somewhere?

share|improve this question
1  
The following language $\{\langle M_1,M_2\rangle \mid M_1, M_2 \text{ Turing machines and } L(M_1)=L(M_2)\}$ is neither recognizable, nor co-recognizable. –  A.Schulz Mar 19 at 17:53

2 Answers 2

up vote 10 down vote accepted

I'll write "corecognizable" as a shortcut for "complement of recognizable". There are countably many recognizable languages and countably many corecognizable languages. Therefore, there are uncountably many languages which are neither recognizable nor corecognizable.

share|improve this answer
    
...given that there are uncountably many languages. –  Joe Mar 19 at 22:57
    
@Joe That is not something you need to take as a given. It is easily shown. –  Taemyr Mar 20 at 9:39

It is completely possible for both $L$ and $\overline{L}$ to be unrecognizable. For example, for any unrecognizable $M$, the language $L = 0M + 1\overline{M}$ over $\Sigma = \{0,1\}$ has this property (why?).

share|improve this answer
    
I am not familiar with this formulation of languages. Is $L = (\{0 \} \circ M) \cup (\{1\} \circ \overline{M})$, where $\circ$ denotes concatenation? –  baffld Mar 22 at 22:57
1  
@baffld: That's right. –  sdcvvc Mar 25 at 21:10

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.