decidable iff recognizable and co-recognizable

Here is the keystone theorem of this whole map. Suppose you have two helpers searching for the same string. One helper is hunting for evidence that the string IS in the language and will shout YES the moment it finds it. The other is hunting for evidence that the string is NOT in the language and will shout NO the moment it finds it. If exactly one of these two searches is guaranteed to succeed for every string, then running both at the same time gives you a procedure that always returns an answer. That is the trick that turns two one-sided machines into one two-sided decider.

The precise statement: a language L is decidable if and only if L is BOTH recognizable (recursively enumerable) and co-recognizable (its complement is recognizable). One direction is easy — a decider for L gives a recognizer for L (just accept), and flipping accept/reject gives a recognizer for the complement. The other direction is the clever part. Let R1 recognize L and R2 recognize the complement of L. On input w, run R1 and R2 IN PARALLEL, alternating their steps (this interleaving is called dovetailing). For any w, exactly one of R1, R2 must eventually halt and accept: if w ∈ L then R1 accepts, if w is not in L then R2 accepts. So this combined machine always halts — accept when R1 wins, reject when R2 wins — which is a decider. Hence L is decidable.

This theorem is the engine behind much of the structure of the computable world. It explains why an undecidable language that is recognizable (like A_TM) must have a complement that is NOT recognizable — otherwise the language would be decidable, a contradiction. It gives a clean three-way picture: decidable languages sit in the overlap of the recognizable and co-recognizable classes; the truly hard languages sit in exactly one of those two; and some languages lie outside both. It is also the reason dovetailing is such a load-bearing idea: parallel patience converts two partial answers into one total one.