Decidable languages are closed under complement. If a language is a decidable there is a TM that accepts and halts strings that belong to the language and rejects and halts strings that do not belong to the language. Flipping the accept and reject states generates a TM to decide the complement of this language.
Not all Recognizable languages are closed under complement. If the complement of a recognizable language is also recognizable, the language is, in fact, decidable.
Suppose is recognizable and recognizes . Assume that the complement, is also recognizable and recognizes .
Here is a decider for
On input
- For
- Run on for steps. If accepts, accept.
- Run on for steps. If accepts, reject.
Thus, if a language and its complement is recognizable, then the language is decidable.
We know that, is recognizable but not decidable. This implies that is not recognizable.