Decidable and Turing-Recognizable Languages

A Turing machine $M$ processes an input string $w$ by running through a sequence of configurations, as established when configurations and single-step computation were defined. On any fixed input, exactly one of three things happens: $M$ enters its accept state and halts, $M$ enters its reject state and halts, or $M$ runs forever without halting. This trichotomy is the raw material from which the entire vocabulary of computability is built. Call $M$ a decider if, for every input string $w$, $M$ halts — either accepting or rejecting — and never loops forever. A decider gives you a complete, guaranteed verdict on every input; this is the strongest and most desirable behavior an algorithm can exhibit. A language $L$ is decidable (equivalently, recursive) if there exists some decider $M$ with $L(M) = L$, meaning $w \in L \iff M$ accepts $w$, and additionally $M$ halts on every $w$ (accepting members of $L$ and rejecting everything else). Call $M$ a recognizer for language $L$ if $L(M) = L$, with no further requirement: $M$ must accept every $w \in L$, but on strings $w \notin L$, $M$ is permitted either to reject or to run forever. A language $L$ is Turing-recognizable (equivalently, recursively enumerable, or r.e., or semidecidable) if some Turing machine recognizes it. The word "semidecidable" captures the asymmetry precisely: only the "yes" side of the decision is guaranteed to terminate. The crucial structural fact is that every decider is automatically a recognizer — a machine that always halts correctly is in particular a machine that accepts exactly the members of $L$ (it just happens to also reject everything else with a guarantee). This immediately gives

The heart of computability theory is the discovery that this containment is strict: there exist languages that are Turing-recognizable but not decidable. The canonical witness is

the language underlying the Halting Problem's acceptance variant. $A_{TM}$ is Turing-recognizable — simulate $M$ on $w$ and accept if the simulation accepts — but no decider for $A_{TM}$ can exist, by a diagonalization argument. This single example is the seed from which nearly all undecidability results grow via reduction.

The clean way to see the relationship between deciding and recognizing is to build the machines explicitly and to prove the equivalence theorem that connects "recognizable" to "there is an algorithm that enumerates the language."

Building a recognizer from a machine that simulates another machine. Given the encoded pair $\langle M, w \rangle$, a universal recognizer $U$ simulates $M$ step by step on $w$: ``` procedure Recognize-ATM(⟨M, w⟩): // U is a universal Turing machine: it interprets M's transition // table and simulates M running on w, one configuration at a time. initialize configuration C0 := start configuration of M on w C := C0 loop forever: if C is an accepting configuration of M: accept if C is a rejecting configuration of M: reject C := next configuration of M from C // one simulated step // if M loops forever on w, this loop never halts — that is fine // for a recognizer, but would violate the decider requirement ``` This machine is a legitimate recognizer for $A_{TM}$: whenever $M$ accepts $w$, the simulation eventually reaches an accepting configuration and $U$ accepts; whenever $M$ rejects $w$, $U$ rejects; whenever $M$ loops on $w$, $U$ loops too. $U$ never gives a wrong answer, but it fails the decider requirement precisely on the looping case — it does not halt there.

Why you cannot simply "wait longer" to fix this. A natural instinct is: run $M$ for more and more steps, and if it hasn't halted, guess "no." This is unsound, because for any finite bound $t$, there exist machine-input pairs that take more than $t$ steps to accept. Any fixed cutoff misclassifies some accepting instance as rejecting. There is no way to distinguish, by looking only at a finite prefix of the computation, "still working" from "will never finish."

The Enumeration Theorem. A deeper structural fact makes "Turing-recognizable" synonymous with "the language of accepted strings can be listed by an algorithm, possibly with repetition and without a guarantee of ever hitting a given non-member." Formally: $L$ is Turing-recognizable iff there is a Turing machine $E$ (an enumerator) that, running with no input, prints out a sequence of strings $w_1, w_2, w_3, \ldots$ (with possible repeats, in any order, possibly running forever) such that $L$ is exactly the set of strings that eventually get printed. From enumerator to recognizer: given $E$, build $M$ that on input $w$ runs $E$, and whenever $E$ prints a string, checks whether it equals $w$; if so, $M$ accepts. If $w \in L$, it will appear in $E$'s output eventually, so $M$ accepts; if $w \notin L$, $M$ simply never accepts (it loops), which is exactly recognizer behavior. From recognizer to enumerator — the dovetailing trick: this direction is the more delicate and instructive one, because a naive attempt fails. Given recognizer $M$, you cannot just "run $M$ on $w_1$, then $w_2$, then …" because $M$ might loop forever on $w_1$ if $w_1 \notin L$, and you would never get to try $w_2$. The fix is to dovetail: interleave a growing amount of simulation time across a growing set of candidate strings. ``` procedure Enumerate(M): // M is a recognizer for language L, over some fixed alphabet Σ. // s1, s2, s3, ... is the standard enumeration of all strings in Σ* // in length-then-lexicographic order (so every string appears at // a specific finite index). for i := 1, 2, 3, ...: for j := 1 to i: simulate M on input s_j for exactly i steps if M accepts s_j within those i steps: print s_j // may print duplicates; that is allowed ``` Every pair $(i, j)$ with $j \le i$ is visited exactly once as $i$ ranges over all positive integers, so for any fixed string $s_j$ that $M$ accepts within $k$ steps, the pair $(i, j) = (\max(k, j), j)$ (or any $i \ge \max(k,j)$) is eventually reached, and $s_j$ gets printed. Strings not in $L$ are never printed, because $M$ never accepts them regardless of how long it runs. This establishes the equivalence in both directions.

Deciders. If $M$ is a decider running in $T(n)$ steps on inputs of length $n$, deciding membership costs $O(T(n))$ time and $O(S(n))$ space where $S(n)$ is the space $M$ uses — these bounds are exactly the resource bounds studied later under Time Complexity and space complexity. The definitional claim here is not about a specific bound but about guaranteed termination: for every $w$, the computation of $M$ on $w$ is a finite sequence of configurations ending in accept or reject. This is an all-quantified halting guarantee, and it is what makes decidability a robust, checkable-in-principle property from the outside — you can always ask "has it halted yet?" and eventually get a truthful "yes."

Recognizers. A recognizer gives no uniform bound on halting time as a function of $n$ alone — indeed for a fixed length there can be no computable bound, since if there were, you could decide the language by running for that many steps and rejecting if it never halted, contradicting undecidability of languages like $A_{TM}$. So the "complexity" of a mere recognizer is unbounded on the reject side; only accepting runs are guaranteed finite, and even then with no known bound in advance.

Correctness of the enumerator/recognizer equivalence. The proof sketch above is a full correctness argument, but it is worth stating the invariant explicitly. In the dovetailing enumerator, the invariant maintained after completing outer iteration $i$ is: > For every $j \le i$ and every string $s_j$ that $M$ accepts within $i$ steps, $s_j$ has already been printed. This invariant holds by direct execution of the nested loop (the inner loop at outer index $i$ explicitly simulates $s_j$ for $i$ steps for every $j \le i$). Taking $i \to \infty$, every string $s_j \in L$ eventually satisfies "$M$ accepts $s_j$ within $i$ steps" for $i$ large enough (namely $i \ge \max(j, \text{acceptance time of } s_j)$), so it is printed at that stage or later. Conversely no $s_j \notin L$ is ever printed, since printing only happens upon a genuine accept by $M$'s simulation. This is exactly the semantics of Turing-recognizability, establishing the equivalence rigorously rather than by analogy.

Why decidable $\subsetneq$ recognizable, not just $\subseteq$. The inclusion direction is immediate (a decider is a recognizer). Strictness needs a genuine diagonalization, sketched here because it is the load-bearing fact of the whole subject. Suppose, for contradiction, that $A_{TM}$ had a decider $H$: $H(\langle M, w\rangle)$ always halts, accepting iff $M$ accepts $w$. Construct $D$: ``` procedure D(⟨M⟩): if H(⟨M, ⟨M⟩⟩) accepts: // does M accept its own description? reject else: accept ``` $D$ is well defined and always halts, because $H$ is assumed to always halt. Now ask what $D$ does on its own description $\langle D \rangle$:

• If $D$ accepts $\langle D\rangle$, then by $D$'s definition $H(\langle D,\langle D\rangle\rangle)$ rejected, meaning $D$ does not accept $\langle D\rangle$ — contradiction.
• If $D$ rejects $\langle D\rangle$, then $H(\langle D,\langle D\rangle\rangle)$ accepted, meaning $D$ does accept $\langle D\rangle$ — contradiction.

Both cases are contradictory, so no such $H$ can exist. Hence $A_{TM}$ is undecidable. But $A_{TM}$ is Turing-recognizable (the universal simulator above recognizes it), which exhibits a concrete language in Turing-recognizable minus decidable, proving the containment strict. This argument is the direct descendant of Cantor's diagonal argument against a bijection between a set and its power set, transplanted into the world of machine descriptions.

Tradeoffs, honestly stated. Decidability is the gold standard but is a strong requirement that many natural questions fail to meet; recognizability is a weaker, more common guarantee that still has teeth (it supports semi-automated verification: run and wait, and if it says yes, trust it). The class of decidable languages is closed under complement, union, and intersection — because you can build a decider for the complement by simply flipping the accept/reject roles of a decider, which halts on everything by hypothesis. Turing-recognizable languages are closed under union and intersection (dovetail two recognizers) but not guaranteed closed under complement, which is exactly the seed of the co-Turing-recognizable class and its relation to decidability, taken up separately.

Consider three concrete languages over machine encodings, tracing what kind of machine each admits.

Language 1: $A_{DFA} = \{\langle B, w \rangle : B$ is a DFA that accepts string $w\}$.

This machine always halts — the simulation is bounded by $|w|$ steps with no possibility of looping, since DFA computation is a straight-line walk through states with no branching or backtracking. Hence $A_{DFA}$ is decidable.

Language 2: $A_{TM} = \{\langle M, w\rangle : M$ accepts $w\}$, as above.

This machine recognizes $A_{TM}$ but is not a decider, precisely because step 5 can occur (e.g. $M$ is a machine that loops on all inputs, so $\langle M, w\rangle \notin A_{TM}$ and the simulator hangs). By the diagonalization argument above, no decider for $A_{TM}$ exists — this failure is unavoidable, not a limitation of this particular construction.

Language 3: $E_{TM} = \{\langle M \rangle : L(M) = \emptyset\}$ ("does $M$ accept nothing at all?"). Trying the naive approach — dovetail $M$ over all strings and see if it ever accepts — gives a recognizer for the complement $\overline{E_{TM}}$ (accept if you ever witness $M$ accept something), but gives no recognizer for $E_{TM}$ itself in any obvious way, and in fact $E_{TM}$ can be shown Turing-recognizable-but-not-decidable by reduction from $A_{TM}$, foreshadowing the reduction technique used pervasively once decidable problems about automata are studied in depth. The three languages above thus stratify exactly the classes this article defines: fully decidable ($A_{DFA}$), recognizable but not decidable ($A_{TM}$), and a further example ($E_{TM}$) whose non-recognizable complement will matter once closure under complement is examined.

A second trace, showing dovetailing concretely. Suppose alphabet $\Sigma = \{a\}$ and $M$ is a recognizer such that $M$ accepts $s_j = a^j$ after exactly $2j$ steps of simulation (a toy stand-in for "acceptance time grows with input"). Enumerate $s_1=a, s_2=aa, s_3=aaa,\ldots$

Every string eventually gets enough simulated steps to reveal its true accept time, so the enumerator prints exactly $\{a^j : j \ge 1\}$ (with repeats), matching $L(M)$ exactly, as the general argument guarantees.

The vocabulary of deciders, recognizers, and the boundary between them emerged directly from foundational work on the limits of mechanical computation in the 1930s, tightened and formalized over the following decades into the standard hierarchy taught today.

Every practical verification and analysis tool lives on one side of this line or straddles it deliberately. Type checkers for languages with decidable type systems (Hindley–Milner inference in ML-family languages) are deciders — they always terminate with a definite yes/no on whether a program type-checks. Model checkers for finite-state hardware and protocols exploit decidability of automaton-based questions (emptiness, equivalence) to give guaranteed answers about bounded systems. Static analyzers and linters for general-purpose languages, by contrast, typically implement recognizer-style or approximate procedures for properties like "does this code path ever execute," because the exact question is undecidable by reduction from the halting problem; industrial tools accept this and report either a sound over-approximation or "unknown" rather than looping forever. SAT and SMT solvers are deciders for their respective decidable theories, underlying modern compiler optimizations, program synthesis, and hardware verification pipelines. Theorem provers like Coq, Lean, and Isabelle formalize proofs whose checking is decidable (a fixed, finite proof object is verified in bounded time) even though finding the proof is not guaranteed to terminate — exactly the decider/recognizer split relocated to proof search versus proof checking. Understanding this boundary is also what lets engineers recognize, before writing code, that a proposed feature ("detect all infinite loops in user-submitted code and reject them") is asking for something no algorithm can deliver in full generality, redirecting effort toward sound approximations instead.

Ask the tutor: If a language and its complement are both Turing-recognizable, what can you conclude about the language itself, and why?