Completed second draft of this book

PDF version of this book

The Halting Problem

We begin with some notation.

1. A computer program with a single integer parameter and a single integer output is represented by $p_n(m)$. $n$ is the Gödel number of the program. $m$ is the parameter. $p_n(m)$ is the integer output.

2. If $p_n(m)$ halts we write $H(p_n(m))$.

3. We only consider programs with an output when they halt that is either 1 or 0. If $H(p_n(m))$ then $p_n(m) = 0$ or $p_n(m) = 1$.

Now we can give a sketch of the proof of the unsolvability of the Halting Problem.

The halting problem asks does there exist a computer program $h(n)$ such that $h(n)=1$ if $H(p_n(0))$ and if not $h(n) = 0$. We give a proof by contradiction. We assume $h(n)$ exists and prove this leads to a contradiction.

For any program $p_n$ with a single integer parameter $m$ it is straightforward to compute $k$ such that $p_k(0)$ behaves exactly as $p_n(m)$. This says for a given program $p_n$ and parameter $m$ we can compute $k$ which is the Gödel number of a program that has $m$ embedded in the program and acts like $p_n$ with parameter $m$. It easy to modify $p_n$ to create $p_k$. We reserve some block of program memory for $m$ and read that location instead of reading an input parameter.

Using the above technique we can use a solution to the halting problem to solve the halting problem for a computer program with any parameter. Such a program $s(n,m) = 1$ if $H(p_n(m))$ halts and 0 otherwise.

Now construct a program $g(n)$ from $s(n,m)$ such that $g(n)$ will not halt but loop forever if $H(p_n(n))$ (equivalent to $s(n,n)=1$) and otherwise it will halt.

$g$ must have some Gödel number $t$. What does $g(t)$ do? $g(t)$ is the same as $p_t(t)$. If $g(t)$ halts then $g(t)$ is designed to run forever! Therefore $g$, $s$ and $h$ cannot exist.

This sketch of a proof is far simpler than Gödel's result. The program modifications we describe are straight forward for an experience programmer but the details at the level of computer code are tedious. It is even more tedious to prove the modifications do what is intended. Gödel's proof in 1931 never mentioned computers. He went through the long and difficult exercise of showing that a formal system could be modeled as an arithmetic function definable within the formal system. He then proved the consistency of the formal system was equivalent to a question about this function. Using an argument similar to the above he showed one could not prove that property from within the system unless the system itself was inconsistent. (One can prove anything in an inconsistent system.)

Completed second draft of this book

PDF version of this book