I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the complement of an unrecognizable language?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Sure: the Halting language (sometimes called $K$) is recursively enumerable whereas its complement ($\overline{K}$) is famously not.
Generally speaking, the existence of such languages follows from the implication you state -- the complement of enumerable yet undecidable languages can not be enumerable -- by the existence of precisely enumerable yet undecidable languages.
That said, there are also non-enumerable languages whose complement isn't either.
