# Halting Problem

The halting problem asks the question whether a program P terminates on input I.

To solve the halting problem means to find a program H satisfying the following specification.
- H takes as input a program P and an input I.
- H always terminates.
- H(P,I) = true if P terminates on I.
- H(P,I) = false if P does not terminates on I.

We want to show that the halting problem is not decidable, that is, there is no program H satisfying the four properties above.

**Remark:** Turing (1937) introduced what is now called a Turing machine in order to give a precise definition of "program".

In other words, we want to show that a program H with the properties above cannot exist.

**Theorem:** There is no program H with the four properties above.

*Remark:* Generally, to show "not A", one assumes "A" and derives a contradiction.

So let us assume that H exists.

Define a program S (for "strange") as follows.

**Definition:** S(X) loops if and only if H(X,X)=true.

More explicitly, in pseudo-code, we can write S(X) as

if H(X,X) then while true do skip

Because H exists and always terminates, we know that S(X) does not terminate if and only if H(X,X)=true.

We now derive a contradiction by asking whether S(S) terminates:

H(S,S)=true       iff (by definition of H)
S(S) terminates   iff (by definition of S)
H(S,S)=false

where `iff` abbreviates `if and only if`, often written as `<=>` or $\Leftrightarrow$.

QED

## References

A wonderful book with many anecdotes, but also working through all technical aspects of Turing's original paper is Petzold's [The Annotated Turing](https://en.wikipedia.org/wiki/The_Annotated_Turing).