title: "Halting Problem"

Halting Problem

Definition. The halting problem is the language $HALT_{\mathsf{TM}} = \{\langle M, w \rangle : M$ is a Turing machine that halts on input $w\}$. It is Turing-recognizable but not decidable.

Undecidability is proved by reduction from the acceptance problem $A_{\mathsf{TM}} = \{\langle M, w\rangle : M$ accepts $w\}$, which is itself proved undecidable by diagonalization against a machine given its own description. Read through the Church-Turing thesis, the result says no program in any language decides whether an arbitrary program halts on an arbitrary input. Rice's theorem settles essentially every non-trivial question about a machine's language. Halting is not such a question, so Rice does not apply to the halting problem itself; that undecidability comes from the reduction in Lecture 8, Example 1. Proved in Lecture 7.