8
$\begingroup$

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?

$\endgroup$
1
  • 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, 2014 at 17:53

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ ...given that there are uncountably many languages. $\endgroup$
    – Joe
    Mar 19, 2014 at 22:57
  • $\begingroup$ @Joe That is not something you need to take as a given. It is easily shown. $\endgroup$
    – Taemyr
    Mar 20, 2014 at 9:39
10
$\begingroup$

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?).

$\endgroup$
2
  • $\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, 2014 at 22:57
  • 1
    $\begingroup$ @baffld: That's right. $\endgroup$
    – sdcvvc
    Mar 25, 2014 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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