Closure under Complement: Decidable and Recognizable languages

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 L is recognizable and M recognizes L. Assume that the complement, \overline{L} is also recognizable and N recognizes \overline{L}.

Here is a decider for L

On input w

  1. For i = 0, 1, 2 \ldots
    1. Run M on w for i steps. If M accepts, accept.
    2. Run N on w for i steps. If N accepts, reject.

Thus, if a language and its complement is recognizable, then the language is decidable.

We know that, A_{TM} is recognizable but not decidable. This implies that \overline{A_{TM}} is not recognizable.

Leave a Reply

Your email address will not be published. Required fields are marked *