Decidable iff recognizable and co-recognizable

Remarks

If a machine decides $L$, it recognises $L$; swapping its accepting and rejecting states gives a machine that decides, and so recognises, the complement. Conversely, let $M_1$ recognise $L$ and $M_2$ recognise its complement. On input $w$, run $M_1$ and $M_2$ alternately, one step at a time. Exactly one of them accepts $w$ after finitely many steps, so the combined machine always halts, and it accepts when $M_1$ is the one that accepts. The halting language $H$ shows that both halves of the condition are needed: $H$ is recursively enumerable, but $H$ is not decidable, so its complement is not recursively enumerable. The same statement for subsets of $\N$ says that a set is computable exactly when it and its complement are computably enumerable.

Going deeper

For a student

The theorem is the standard tool to show that a language is not recursively enumerable. Since the halting problem is recognizable but undecidable, the theorem shows that its complement is not recognizable. In the arithmetical hierarchy, it says that the sets in both $\Sigma_1$ and $\Pi_1$ are exactly the computable sets.