The Halting Problem

27 Oct 2024

---

The halting problem is the problem of determining whether a given program will halt or continue to run forever on a given input. The problem is undecidable: no algorithm exists that can solve it for all possible program-input pairs. We can show this using a two part proof. First, we prove, by contradiction, that the acceptance problem is undecidable. Second, we prove, also by contradiction, that the halting problem is undecidable.

The acceptance problem is the problem of determining whether a given Turing machine accepts a given input. We show that the acceptance problem is undecidable. Let

A_TM = {<M, w> | M accepts w}

be the set of strings that encode (M, w) pairs, where M is a Turing machine and w is a string. We claim that A_TM is undecidable. Suppose that A_TM is decidable. Then, there exists a Turing machine that decides A_TM. Call it H:

• H(<M, w>) accepts if M accepts w;
• H(<M, w>) rejects if M does not accept w.

Now, construct a new Turing machine D that uses H as a subroutine. D takes a string encoding of a Turing machine M as input, and passes M as both the first and second arguments to H, returning the opposite of H's output:

• D(<M>) accepts if H(<M, <M>>) rejects, i.e. D accepts <M> if M does not accept <M>;
• D(<M>) rejects if H(<M, <M>>) accepts, i.e. D rejects <M> if M accepts <M>.

Finally, pass D as input to itself:

• D(<D>) accepts if H(<D, <D>>) rejects, i.e. D accepts <D> if D does not accept <D>;
• D(<D>) rejects if H(<D, <D>>) accepts, i.e. D rejects <D> if D accepts <D>.

In both cases, we reach a contradiction. Therefore, the assumption that A_TM is decidable must be false. In other words, A_TM is undecidable.

Next, we show that the halting problem is also undecidable. Let

H_TM = {<M, w> | M halts on w}.

Again, we claim that H_TM is undecidable. Suppose that H_TM is decidable. Then, there exists a Turing machine that decides H_TM. Call it R:

• R(<M, w>) accepts if M halts on w;
• R(<M, w>) rejects if M does not halt on w.

Now, we can use R to construct a Turing machine S that decides A_TM, using R as a subroutine to determine whether M halts on w:

• S(<M, w>) rejects if R(<M, w>) rejects, i.e. M does not halt on w;
• S(<M, w>) rejects if M rejects w;
• S(<M, w>) accepts if M accepts w.

Therefore, if H_TM is decidable, then A_TM is also decidable. But we have already shown that A_TM is undecidable. Therefore, the assumption that H_TM is decidable must be false. In other words, H_TM is undecidable.