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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Schulz
    Mar 19 '14 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.

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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