Closure Properties and the Co-Turing-Recognizable Class

A language $L$ over an alphabet $\Sigma$ is Turing-recognizable (also called recursively enumerable) if some Turing machine $M$ halts and accepts on every string in $L$, and either rejects or runs forever on every string not in $L$. A language is decidable (recursive) if some Turing machine halts on every input, accepting strings in $L$ and rejecting strings not in $L$. Decidability is strictly stronger: it demands a guaranteed, halting verdict in both directions, while recognizability only guarantees a halting verdict on the "yes" side. The complement of $L$, written $\overline{L}$, is the set of all strings over $\Sigma^*$ not in $L$. Closure properties describe how these classes behave under set operations. The decidable languages are closed under complement, union, intersection, and concatenation — if you can decide $L_1$ and $L_2$, you can decide combinations of them by running both deciders and combining the verdicts, since both always halt. The recognizable languages are closed under union and intersection, but not closed under complement in general. This failure of closure is not a minor technicality; it is the structural reason undecidable-but-recognizable languages exist at all, and it is precisely quantified by the central theorem below.

Theorem (Decidability via recognizability of both sides). A language $L$ is decidable if and only if both $L$ and $\overline{L}$ are Turing-recognizable. This theorem is the bridge between the two classes. The forward direction is easy: a decider for $L$ is trivially a recognizer for $L$, and swapping accept/reject states gives a decider — hence a recognizer — for $\overline{L}$. The reverse direction is the substantive half, and it is a dovetailing argument: run two recognizers side by side, alternating steps, until one of them halts. Because every string is in exactly one of $L$ or $\overline{L}$, and because both languages have a recognizer, one of the two machines is guaranteed to halt eventually on any input, giving a correct, always-halting decision procedure.

The constructive half of the theorem — building a decider out of two recognizers — is the mechanism worth internalizing, since it recurs throughout computability theory. The technique is called dovetailing: instead of running one machine to completion (which might never happen) and then the other, we interleave their execution step by step so that neither one can "starve" the other of CPU time. ``` // Given: recognizer M1 for language L // recognizer M2 for language ~L (the complement of L) // Goal: a decider D for L function D(w): // simulate M1 and M2 in lock-step, one step at a time initialize configuration c1 = start configuration of M1 on w initialize configuration c2 = start configuration of M2 on w loop forever: c1 <- advance M1 by exactly one computation step from c1 if M1 has halted in c1: if M1 accepts: return ACCEPT // (M1 rejecting w is impossible for a recognizer's // intended use here, but if it happens, fall through) c2 <- advance M2 by exactly one computation step from c2 if M2 has halted in c2: if M2 accepts: return REJECT // w is in ~L, so w not in L // unreachable: guaranteed to halt, see correctness argument below ``` Two engineering details make this work in practice. First, "advance by one step" must be well-defined for an arbitrary Turing machine simulation — this is exactly the same simulation primitive used to build the universal Turing machine underlying $A_{TM}$. Second, the loop must genuinely alternate a bounded amount of work per round (one step each), not run $M_1$ to some heuristic cutoff before trying $M_2$; otherwise, on inputs where $M_1$ loops forever, $D$ would never reach $M_2$ and would fail to halt. The other direction of the theorem — decidable $\Rightarrow$ both sides recognizable — is the trivial "flip the decider" construction: ``` // Given: decider D for language L (always halts) // Build: recognizer for L, and recognizer for ~L function Recognizer_for_L(w): return D(w) // D already halts and gives correct verdict function Recognizer_for_complement(w): if D(w) == ACCEPT: return REJECT else: return ACCEPT // still always halts, since D always halts ``` Since a decider is, by definition, a machine that always halts with the correct verdict, simply swapping its accept and reject outputs yields a decider for the complement — and a decider is in particular a recognizer.

Correctness of the dovetailing decider. Fix any input $w$. Because $L$ and $\overline{L}$ partition $\Sigma^*$, exactly one of the statements "$w \in L$" or "$w \in \overline{L}$" is true. If $w \in L$, then since $M_1$ recognizes $L$, $M_1$ halts and accepts after some finite number of steps $s_1$. If $w \in \overline{L}$, then since $M_2$ recognizes $\overline{L}$, $M_2$ halts and accepts after some finite number of steps $s_2$. In either case, one of the two machines halts within a finite, input-dependent number of steps. Because the scheduler advances both machines by exactly one step per round, after at most $2\max(s_1,s_2)$ total simulated steps the halting machine's halt is observed, and $D$ returns the corresponding verdict. Crucially $D$ never needs to wait for the non-halting machine: it only needs to notice, at each round, whether either machine has halted yet. So $D$ always halts, and it halts with the correct answer — hence $D$ decides $L$.

Complexity. This construction is about computability, not efficiency, so there is no polynomial bound to state — but it is worth being honest about the resource cost. If $w \in L$ and $M_1$'s accepting computation takes $s_1$ steps, the dovetailed decider may take $O(s_1)$ rounds only if $M_2$ also happens to halt around then; more precisely it takes $O(\min(s_1, s_2))$ rounds in the case both machines eventually halt (which is guaranteed here since one always does for any given $w$), each round costing the constant-factor overhead of simulating one step of each machine. The simulation overhead itself is bounded by a polynomial in the machine's description size for standard simulation techniques, but the number of rounds is fundamentally unbounded as a function of $|w|$ alone — deciding some decidable languages this way can be astronomically slow, since decidability makes no promise about running time. Space usage is similarly unbounded in principle but always finite for a given halting computation, since each of $M_1$, $M_2$ only uses finitely much tape before halting.

Why recognizability alone does not give closure under complement. The dovetailing trick above requires a recognizer for $\overline{L}$ to exist. If only $L$ is known to be recognizable, dovetailing $M_1$ against nothing achieves nothing on the "no" side: if $w \notin L$, $M_1$ simply loops forever, and there is no witness process to detect this in finite time in general. This is not a failure of cleverness — for $A_{TM}$ it is a theorem.

Theorem. $\overline{A_{TM}}$ is not Turing-recognizable. Proof. Recall $A_{TM} = \{\langle M, w\rangle : M \text{ is a TM that accepts } w\}$, which is recognizable via the universal simulator (established by Undecidability by Diagonalization alongside its undecidability). Suppose, for contradiction, that $\overline{A_{TM}}$ were also recognizable. Then both $A_{TM}$ and its complement would be recognizable, so by the theorem above, $A_{TM}$ would be decidable. But $A_{TM}$ is proven undecidable by the diagonalization argument: assuming a decider $H$ for $A_{TM}$ lets us build a machine $D$ that runs $H(\langle D, D \rangle)$ and does the opposite, producing a contradiction on input $\langle D, D\rangle$ exactly as in Cantor's diagonal argument. This contradiction refutes the assumption that $\overline{A_{TM}}$ is recognizable. $\blacksquare$ This is the contrapositive engine of the whole article: instead of directly building a diagonalizing machine against $\overline{A_{TM}}$, we route the argument through the decidability–closure theorem, reusing the already-established undecidability of $A_{TM}$. This is a template you will reuse constantly: to show some language $B$ is not recognizable, it often suffices to show $B$'s complement is recognizable and that if $B$ were also recognizable, some known-undecidable language would become decidable.

Let's trace both directions of the theorem on a small but genuine example, then apply the contrapositive machinery to a second language.

Example 1 — a decidable language, forward direction. Let $L = \{\langle M \rangle : M \text{ is a TM whose transition table has an even number of entries}\}$. This is decidable: count the table entries and check parity — always halts. We exhibit both recognizers explicitly per the theorem.

Both halt on every input, confirming decidable $\Rightarrow$ both sides recognizable, with room to spare (both are in fact decidable too).

Example 2 — the reverse (dovetailing) direction on a toy pair. Suppose (hypothetically, for illustration only — this is a toy, not $A_{TM}$) $L' = \{n : n \text{ is prime}\}$ encoded in unary/binary, with:

• $M_1$: on input $n$, trial-divides up to $\sqrt n$; halts and accepts iff $n$ is prime, halts and rejects iff composite. (In reality $M_1$ already halts on both sides — primality is decidable — but suppose we only trust the "accept primes" behavior for this drill.)
• $M_2$: on input $n$, searches divisors $2,\dots,n-1$; halts and accepts as soon as it finds one (so accepts composites), and would in principle "run forever" if we naively didn't bound the search — we impose the bound $n-1$ so it always halts.

Dovetailing: on $n = 17$, round-robin single steps of $M_1$ and $M_2$. $M_1$ tests divisibility by $2,3$ ($\sqrt{17}\approx 4.1$) and halts accepting after checking up to $4$; $M_2$ would need to check up to $16$ divisors before concluding "no divisor found," but since $M_2$ here is defined to loop or reject only after exhausting all candidates, $M_1$'s halt is detected first, in about 3–4 rounds, and $D$ correctly outputs ACCEPT ("17 is prime") well before $M_2$ finishes its longer search. This mirrors the general theorem: the decider does not need both machines to be efficient or even comparably fast — it only needs the one that will eventually halt on this particular input to halt in finite time, and it detects whichever happens first.

Example 3 — applying the contrapositive to a new language. Define $B = \{\langle M \rangle : M \text{ does not halt on any input}\}$ (the "totally non-halting" machines). One can show, using a very similar reduction-flavored argument foreshadowing Mapping Reducibility, that $B$ is not recognizable. Sketch: recognizability of $B$ would let you build a recognizer for $\overline{A_{TM}}$ by a reduction that transforms $\langle M, w\rangle$ into a machine $M_w$ that ignores its input and simulates $M$ on $w$, looping forever if $M$ accepts $w$ (never halting) and halting immediately otherwise. Then $M_w \in B$ (never halts) exactly when $M$ does not accept $w$, i.e., exactly when $\langle M,w\rangle \in \overline{A_{TM}}$. A recognizer for $B$ would thus recognize $\overline{A_{TM}}$ — which we just proved impossible. This is precisely the reduction technique the theorem sets up.

The theorem connecting decidability to two-sided recognizability, and the resulting classification of $A_{TM}$ and its complement, emerged directly from the foundational work on computability in the 1930s and its systematization in the following decades.

The recognizable-but-not-decidable phenomenon is not an academic curiosity confined to Turing machines; it shows up wherever a search or verification process can confirm success but has no guaranteed way to confirm failure. Program verifiers and type checkers for sufficiently expressive languages exhibit exactly this asymmetry: they can certify "this program type-checks" by exhibiting a derivation, but detecting "this program will never type-check under any elaboration strategy" is, in the worst case, exactly as hard as the halting problem — which is why real-world tools impose termination bounds, restricted type systems, or accept the risk of non-termination on pathological inputs. Automated theorem provers and SAT/SMT solvers used in hardware and software verification (as in compilers, security analyzers, and formal-methods tooling) are recognizers for "provable" or "satisfiable," and their looping-on-failure behavior is a direct, practical instance of one-sided recognizability. Model checkers used to verify hardware circuits and communication protocols similarly can confirm the existence of a bug (a reachable bad state) but proving the absence of bugs in unbounded-state systems runs into the same theoretical wall, motivating techniques like abstraction and bounded model checking that trade completeness for termination. More broadly, the decidability–closure theorem is the ancestor of the entire hierarchy of unsolvability degrees. It directly motivates Mapping Reducibility as the tool for transferring undecidability and non-recognizability from known hard languages like $A_{TM}$ to new ones, and it is the base case of the Oracles and the Arithmetic Hierarchy, where languages are classified by how many alternations of "recognizable" and "co-recognizable" quantifiers are needed to define them.

Ask the tutor: Can you walk through why interleaving must be exactly one step per machine per round, rather than some other fixed schedule?