# Is it possible for a language and its complement to both be unrecognizable?

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?

• 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. Mar 19, 2014 at 17:53

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.

• ...given that there are uncountably many languages.
– Joe
Mar 19, 2014 at 22:57
• @Joe That is not something you need to take as a given. It is easily shown. Mar 20, 2014 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?).

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