Decidability & the Halting Problem

Decidable vs. recognizable, and why the halting problem is undecidable.

The idea

Decidability classifies languages by whether a Turing machine can settle membership in them. A language is a set of strings; a machine is a procedure; the two ways of pairing them must be kept distinct.

A machine decides a language $L$ when it halts on every input and accepts exactly the strings of $L$. A machine recognizes $L$ when it accepts exactly the strings of $L$ but may run forever on strings outside $L$. The accepted strings are the same in both cases; what differs is whether a no ever comes back. A decider always answers, while a recognizer asked about a non-member may run forever, revealing nothing. Every decider is a recognizer; the converse fails.

The language that witnesses the failure is the acceptance problem

$A_{TM} = \{ \langle M, w \rangle : M \text{ accepts } w \},$

where $\langle M \rangle$ denotes a finite description of the machine $M$, written out as a string. A machine recognizes $A_{TM}$ by simulating $M$ on $w$ and accepting if the simulation accepts; if $M$ loops, the simulation loops, which recognition permits.

Theorem (Undecidability of the acceptance problem).

The language $A_{TM} = \{ \langle M, w \rangle : M \text{ accepts } w \}$ is Turing-recognizable but not decidable: no Turing machine halts on every input $\langle M, w \rangle$ and accepts exactly when $M$ accepts $w$.

The theorem does not say that deciding acceptance is hard, or that no one has yet found the algorithm: no such algorithm exists.

Ways to work on it

• Walkthrough. Deciding vs. recognizing, and Turing's diagonal proof that the acceptance problem is undecidable.
• Practice. Classify a language or read off the diagonal contradiction.
• Hardest. Prove the halting problem undecidable.

Not sure where to start? Take the ten-question placement test.