The problem dovetailing solves
The previous guides left you with one uncomfortable fact: a recognizer is allowed to loop forever. On a string in its language it must eventually accept, but on a string outside the language it may run on without end, never saying no. That single permission — the looping loophole — is exactly what separates a mere recognizer from a decider, which must always halt with a verdict. So far we have treated this as a limitation to live with. Now we turn it into something we have to ENGINEER around, because we are about to run several looping machines side by side.
Here is the trap, made concrete. Suppose you want to know whether a string w belongs to a union of two recognizable languages, L1 or L2. The obvious plan is: run machine M1 on w; if it accepts, accept; otherwise run M2 on w. The bug is fatal — if w is in L2 but NOT in L1, then M1 might loop forever on w, and you never even reach M2. You are stuck at the first machine, waiting for an answer that will never come, even though the real answer (accept, via M2) was sitting right there. Running them one-after-another fails precisely because of the looping loophole.
Dovetailing: running everything a little at a time
Dovetailing is the fix, and the idea is wonderfully simple: never let any one computation run to completion before you check on the others. Instead, give each computation a tiny time slice in fair rotation. Picture a parent reading bedtime stories to several restless children at once — rather than finishing one whole book (and maybe never finishing, if a child keeps demanding 'again!'), you read one page to child A, one page to child B, one page to child C, then back to A for page two, and so on. No child is ever starved, and any story that DOES end will end in finite time. The name comes from carpentry: dovetail joints interleave their teeth so two pieces lock together — here we interleave the steps of many computations.
Let us repair the broken union from before. To recognize L1 or L2 on input w, run M1 and M2 in lockstep: do one step of M1, then one step of M2, then the second step of M1, the second step of M2, and continue alternating. If EITHER machine ever enters its accept state, halt and accept. Now the argument is airtight: if w is in L1, M1 accepts after some finite number of steps, and the dovetailing reaches that step; if w is in L2, M2 does, and we reach that step too. The other machine looping forever no longer matters, because we never wait for it — we only ever wait one step at a time. This is the real proof that recognizable languages are closed under union.
Dovetailing scales beyond two machines to INFINITELY many, and that is where it earns its keep. Suppose you must run one computation for every string in Sigma-star (the set of all finite strings over the alphabet) — infinitely many of them. You cannot run computation #1 to the end, then #2, because #1 might loop. Instead you walk a triangular schedule: in round k you advance the first k computations by one extra step each. So computation #1 gets steps in every round, #2 starts in round 2, #3 in round 3, and any single (computation, step-count) pair is reached after only finitely many rounds. Nothing infinite is ever waited on; everything finite is eventually serviced.
Naive (BROKEN): finish each computation before the next C1: step1 step2 step3 ......(may loop forever)..... <-- stuck here C2: never reached C3: never reached Dovetailed (FAIR): advance the first k computations in round k round 1: C1.step1 round 2: C1.step2 C2.step1 round 3: C1.step3 C2.step2 C3.step1 round 4: C1.step4 C2.step3 C3.step2 C4.step1 ... Every pair (Ci, step j) occurs by round i+j-1 -> finite wait. If ANY Ci ever accepts, we see it in finite time, even if every other computation runs forever.
The enumerator: a machine that lists a language
Dovetailing now unlocks a completely different — but exactly equivalent — way of picturing recognizable languages. So far a recognizer has been a JUDGE: you hand it a string, it (maybe) says yes. An enumerator flips the relationship around. It is a Turing machine with no input at all and an extra printer attached. You switch it on and just let it run; whenever it likes, it prints a string and moves on. The language of an enumerator is simply the set of all strings it ever prints, in any order, with repeats allowed. Think of it not as a bouncer checking IDs at the door, but as a tireless author publishing one member of the language after another, forever.
The headline theorem — the enumerator characterization — is that these two pictures describe the SAME class: a language is Turing-recognizable if and only if some enumerator enumerates it. (This is exactly why the class is also called recursively enumerable — 'enumerable' is literally the enumerator's promise.) Both directions of the proof are short and both lean on dovetailing or its cousin, a systematic walk through all strings. Once you see them, the equivalence stops feeling like a coincidence and starts feeling inevitable.
- Enumerator gives recognizer (the easy direction). Given an enumerator E, build a recognizer M for the same language: on input w, run E and watch its printer; every time E prints a string, compare it with w; if it matches, M accepts. If w is in the language, E eventually prints it, so M accepts; if not, M simply keeps watching (it may run forever — and that is fine, recognizers are allowed to loop).
- Recognizer gives enumerator (the dovetailing direction). Given a recognizer M, build an enumerator E. Naively running M on string #1, then #2, would get stuck if M loops on #1. So instead E dovetails: it lists all strings s1, s2, s3, ... of Sigma-star in order, and runs M on the first k of them for k steps each, increasing k forever. Whenever this dovetailed run sees M accept some string si, E prints si.
- Check it works. Every string M accepts is accepted within some finite number of steps, and the dovetailed schedule reaches that (string, step-count) pair after finitely many rounds, so E prints it. Strings M never accepts (it rejects or loops on them) are never printed. So E prints exactly the language of M — the two machines agree, and the equivalence is proved.
Enumerate in order, and you can DECIDE
The enumerator view pays off with a sharp insight into the decidable–recognizable gap. A plain enumerator may print in any jumbled order, with repeats. But suppose an enumerator could print its strings in strict increasing order — shortest first, ties broken alphabetically, no repeats. Then something powerful follows: the language is not just recognizable, it is decidable. The reason is that ordered output lets you give up. To decide membership of w, run the ordered enumerator and watch: the moment it prints w, accept; the moment it prints any string that comes AFTER w in the order, you know w will never appear, so reject. Ordering converts the never-ending 'keep waiting' into a definite 'it would have shown up by now'.
This dovetails beautifully (pun intended) with the theorem from the previous guide: a language is decidable exactly when it and its complement are both recognizable. The ordered-enumerator condition is just another face of the same coin. A decider can always be turned into an in-order enumerator (run the decider on every string in length-then-alphabetical order, printing the accepted ones), and an in-order enumerator can always be turned into a decider, as we just saw. So 'decidable', 'recognizable AND co-recognizable', and 'enumerable in increasing order' are three equivalent descriptions of the very same class.
Why recognizable languages are NOT closed under complement
Dovetailing buys generous closure properties for the recognizable languages, but it cannot buy everything — and the gap it cannot close is the most instructive part of this rung. We just saw that recognizable languages are closed under union (dovetail two recognizers and accept if either accepts) and likewise under intersection (run both to completion, in sequence is fine here, and accept only if BOTH accept). They are also closed under concatenation and the Kleene star, all via dovetailing or guessing. Decidable languages are closed under all of these too, AND under complement (a decider always halts, so just swap its accept and reject states).
But the recognizable class is NOT closed under complement, and the reason is the swap trick fails. If M is only a recognizer, swapping accept and reject is hopeless: where M used to loop forever (giving no answer), the swapped machine still loops forever, so it does not accept the complement either. There is no dovetailing rescue, because the missing answers were never produced in the first place — you cannot interleave a step that does not exist. This is not a failure of cleverness; it is a genuine structural fact about the class.
The cleanest proof ties the whole rung together. Suppose, for contradiction, that the recognizable languages WERE closed under complement. Then for any recognizable L, its complement would be recognizable too — meaning L is both recognizable and co-recognizable, which by the previous guide's theorem makes EVERY recognizable language decidable. But the next rung will exhibit a language (the acceptance problem for Turing machines) that is recognizable yet provably undecidable. Contradiction. So recognizable-but-not-decidable languages exist, and their existence is exactly what blocks closure under complement. The looping loophole is not a quirk; it is load-bearing.