patternModerate
Is it possible for a language and its complement to both be unrecognizable?
Viewed 0 times
languagebothpossibleitsforcomplementunrecognizableand
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#22814, answer score: 13
Revisions (0)
No revisions yet.