Decidability and Undecidability: Complete Beginner's Guide

A problem is decidable if some Turing machine halts with the correct yes-or-no answer on every possible input. Such a machine is called a decider. For example, "does this number divide evenly by 7" is decidable: a simple program can always answer it and stop.

Decidability draws the ultimate boundary of computation. Before asking how fast a program solves a problem, we must ask whether any program can solve it at all. The shock of the 1930s, due to Alan Turing, is that some perfectly well-defined problems are undecidable — no algorithm exists that always answers correctly.

Key Concepts

• Decidable language: a decider exists that halts on all inputs, accepting exactly the strings in the language.
• Recognizable language: a machine accepts all strings in the language but may loop forever outside it — weaker than decidable.
• The halting problem: given a machine M and input w, does M halt on w? The canonical undecidable problem.
• Reduction: proving undecidability by showing that a decider for problem B would yield a decider for an already-undecidable problem A.
• Rice's theorem: any nontrivial property of the language a Turing machine recognizes (like "does this program output 42") is undecidable.

How It Works

The halting problem is undecidable — proved by contradiction:

1. Assume a decider H exists that, given any machine M and input w, correctly reports whether M halts on w.
2. Build machine D: on input (a machine description), ask H whether that machine halts on its own description, then do the opposite — loop forever if H says "halts", halt if H says "loops".
3. Run D on its own description. If D halts, H said "loops", so D loops — contradiction. If D loops, H said "halts", so D halts — contradiction.
4. Both cases are impossible, so no such H exists. The halting problem is undecidable.

Worked Example

Contrast that with a decidable problem: "does DFA D accept string w?" Take a DFA with states q0 (start), q1, q2 (accept); transitions q0 to q1 on 'a', q1 to q2 on 'b', q2 to q2 on 'a' or 'b'. Run the decider on "ab":

1. Start in q0, read 'a', move to q1. Steps used: 1.
2. Read 'b', move to q2. Steps used: 2.
3. Input consumed in state q2, an accept state: accept.

The simulation finishes in exactly as many steps as input symbols — 2 steps here — so it halts on every input. That guaranteed termination is what undecidable problems lack: for the halting problem, no simulation strategy can promise to finish, because the simulated machine might never stop.

Common Misconceptions

• Undecidable means no instance can ever be answered. Many specific instances are easy — undecidable means no single algorithm answers every instance correctly.
• The halting problem says we cannot detect infinite loops. We do it routinely. It says no universal detector works for all programs and all inputs.
• Undecidable problems are just really hard. Hardness is about time; undecidability is about existence of any algorithm at all.

Real-World Applications

• Program verification: why no tool can perfectly detect all bugs, deadlocks, or vulnerabilities in arbitrary programs.
• Compiler limits: some desirable optimizations are undecidable, so compilers use safe approximations.
• Theorem proving: first-order logic validity is undecidable, shaping what proof assistants automate.
• Malware detection: perfectly deciding maliciousness is undecidable, so antivirus relies on heuristics and signatures.

Decidability asks the deepest question in computer science: can any algorithm solve this? The halting problem's "no" proves computation has hard limits, and reduction maps those limits onto practical problems from bug-finding to theorem-proving.