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?

Improve this question
$\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
    Commented Mar 19, 2014 at 17:53

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ ...given that there are uncountably many languages. $\endgroup$
    – Joe
    Commented 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
    Commented 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?).

Improve this answer
$\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
    Commented Mar 22, 2014 at 22:57
  • 1
    $\begingroup$ @baffld: That's right. $\endgroup$
    – sdcvvc
    Commented 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.