Given some unrecognizable language $L$, is it possible for its complement $\\ove

Question

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 eq 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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.