edited tags
Raphael
• 70.4k
• 27
• 162
• 359
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}$$.