16.2 Decidability and Undecidability
Computability theory classifies problems by what algorithms can guarantee. A decision problem asks a yes/no question about an encoded input, so it can be identified with a language: the set of encodings whose answer is yes. Examples include “Is this token stream generated by grammar G?”, “Does this control-flow graph contain a cycle?”, and “Does machine M accept input w?”
A language is decidable if some decider halts on every input and answers membership correctly. It is recognizable (recursively enumerable) if some recognizer accepts every member but may either reject or run forever on a nonmember. Every decidable language is recognizable, but some recognizable languages are not decidable.
Halting behavior separates deciders from recognizers
For a recognizable language, one can enumerate candidate computations and eventually find an accepting witness when one exists. Failure to find one after a million steps does not establish nonmembership. This is why compiler search procedures often have three operational outcomes: proved, disproved, and unknown/timeout, even when their internal logic is more specialized than a Turing machine.
If both a language L and its complement ¬L are recognizable, then L is decidable. Run the two recognizers in dovetailing fashion: simulate one step of each, then another step of each. Exactly one must eventually accept, yielding the answer. Running the first recognizer to completion before starting the second is not sufficient because the first may loop forever.
Finite-state problems, parsing for a fixed context-free grammar, type checking for deliberately decidable type systems, graph reachability, and bounded model checking are decidable. Their complexity may still be high; “decidable” does not mean fast. Conversely, undecidability is stronger than intractability: it says no algorithm can halt with a correct yes/no answer for every allowed input.
Reductions transfer impossibility
To show a new problem B is undecidable, we usually reduce a known undecidable problem A to it. A many-one reduction constructs a total computable function f such that
x ∈ A if and only if f(x) ∈ BIf a decider for B existed, compute f(x) and call that decider to decide A, contradicting the known result. The direction matters: A ≤ B says B is at least as hard as A. Reducing the target to the known hard problem does not prove the target hard.
A complete proof defines the transformation on every source input, argues that it terminates and is computable, proves the yes direction, and proves the no direction. Hand-waving “these problems seem similar” is not a reduction. If reducing to a complement, the membership equivalence must be inverted consistently.
Restriction can restore decidability
An undecidable general problem often has useful decidable fragments. Termination is decidable for finite-state programs because repeated configurations reveal a loop. It may be decidable for a structurally recursive language whose type checker enforces decreasing arguments. Equivalence is decidable for deterministic finite automata, although equivalence of arbitrary programs is not.
This is an important language-design lever. A macro system can prohibit unbounded recursion so expansion always terminates. A query language can restrict iteration. A proof assistant can require total functions or explicit termination evidence. A compiler's constant evaluator can impose a step and memory limit, returning “not a compile-time constant” rather than promising to decide arbitrary execution.
Be precise about the input domain. “The analyzer always terminates on programs with at most 20 Boolean variables and bounded loops” is compatible with undecidability of the unrestricted problem. So is an algorithm that is correct when it answers but sometimes returns unknown. What impossibility forbids is a total, universally correct decision procedure over a Turing-complete domain.
When reading a computability claim, ask four questions: What exactly is encoded as input? Must the algorithm halt on all inputs? Are both yes and no answers required to be correct? Is an unknown result permitted? These details distinguish a decider, recognizer, semi-decision procedure, bounded checker, and heuristic—and prevent theoretical limits from being applied more broadly than the theorem states.