The Halting Problem

Recall that for every Turing machine M there is a corresponding natural number n^M (the Gödel number of M); and recall as well that M_i, where $i \in$ N, is the ith Turing machine. (Remember that we have previously established an enumeration M₁, M₂, M₃, $\ldots$ of all Turing machines.) We will now prove that the following function is not Turing-computable. The Halting Problem is the problem of computing this function; hence we will show that the Halting Problem cannot be solved by a Turing machine.

$$h(n^M,m)=\left\{ \begin{array}{rl} 2 & \mbox{if $M: m \longri... ... \mbox{if $M: m \longrightarrow \infty,$} \end{array} \right.$$

To begin the proof that h is cannot be solved by a Turing machine, suppose the opposite: suppose that h is Turing-computable; then there exists some Turing machine H that computes this function. We know that there exists a Turing machine M^k which, when given an unbroken string of k 1's as input, produces a copy of this string with an intervening blank square. For example, if M⁴ were started in the configuration

1

1

1

1

$\ldots$

it would produce

1

1

1

1

1

1

1

1

$\ldots$

It is also clear that there exists a machine $M^\star$ which is such that

$$M^\star: \; n \longrightarrow \mbox{ halt iff } h(n,n) =1.$$

The specification of $M^\star$ is shown in the following figure, which shows the composite machine M_m that chains together M^k, H, and $M^\star$. As you can verify upon reflection,

$$\mbox{For every $n$}: M_m: \; \longrightarrow \mbox{ halt iff } h(n,n) =1.$$

Then, instantiating n to m:

$$M_m: \; m \longrightarrow \mbox{ halt iff } h(m,m) =1,$$

which is to say

$$M_m: \; m \longrightarrow \mbox{ halt iff } M_m: \; \longrightarrow \infty,$$

which is in turn

$$M_m: \; m \longrightarrow \mbox{ halt iff not } M_m: \; \longrightarrow \mbox{ halt},$$

an outright contradiction. QED