dovetailing

Suppose you must run many computations, and some of them might never stop, but you cannot afford to get stuck on one and ignore the others. The naive plan — run the first to completion, then the second, then the third — fails the moment the first one loops forever: you never even start the second. Dovetailing is the simple fix: give each computation a little time in rotation, like a juggler keeping many balls in the air, so that every computation makes progress and none can monopolize the clock. The name comes from a dovetail joint, where two pieces interlock tooth-by-tooth.

The mechanism in plain steps: to run computations C1, C2, C3, ... together, do one step of C1; then one step each of C1 and C2; then one step each of C1, C2, C3; and so on, expanding the batch and the depth as you go. (A common schedule runs Ci for j steps for every pair (i, j) in a diagonal order, which is why this is sometimes called diagonal scheduling.) The guarantee is that for any particular computation Ci, and any finite number of steps k, there is a definite moment in the schedule at which Ci has been simulated for at least k steps. So if ANY of the computations halts after finitely many steps, the dovetailing simulation will witness that halt in finite time — even though other computations run forever in the background.

Dovetailing is the workhorse behind several core results. It is how you build a decider from a recognizer for a language and a recognizer for its complement (run both, dovetailed, and one must halt). It is how an enumerator lists the members of a recognizable language: dovetail the recognizer over all strings, printing each one whose simulation accepts. And it underlies the proof that recognizable languages are closed under union and intersection. The single idea — never let one possibly-infinite task starve the others — is what makes 'run everything at once' a rigorous, finite-time-honoring technique.