Halting Problem

Idea

The halting problem is a decision procedure for deciding whether a Turing machines $M$ halts on an input string $w$. It was proven by Turing that such a problem is undecidable.

Definition

$\mathbf{Halt}:TM(\Sigma )\times {\Sigma }^{\ast }\to \mathbb{B}$ be defined as $P(M,w)=\top$ iff $M$ terminates on input $w$, where $TM(\Sigma )$ is the set of Turing machines on an input language $\Sigma$.

Undecidability

$H$ is recursively enumerable but not decidable.
The proof essentially goes:

1. Fix $e:TM(\Sigma )\times {\Sigma }^{\ast }\to {\Sigma }^{\ast }$ to be an injective computable encoding.
2. Suppose for a contradiction that you have a decider $H$ for the language $\mathbf{Halt}\circ e$.
3. Construct a TM $M:TM(\Sigma )$ that given an input machine $N$ runs $H$ on $⟨N,N⟩$.
4. If $H$ returns $\top$ then loop, otherwise halt (it doesn’t matter what is returned).
5. Now run $M$ on $M$. This terminates iff $H⟨M,M⟩=\perp$ iff $M$ doesn’t terminate.
6. Contradiction. Hence no such deciding TM can exist.
   This proves that the set of decidable problems is a strict subset of the recursively enumerable languages.