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.
- Run
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.