# Joan Lindsay Orr


# The Halting Problem

There is an algorithm to associate every Turing machine with a natural number, called the Turing number of that machine. Thus we can consider the set $$S$$ of all pairs $$(m,n)$$ in $$\NN\times\NN$$ where $$m$$ is a Turing number and the corresponding Turing machine will halt given input $$n$$.

For any Turing machine $$T$$ and input $$n\in\NN$$ write $$T(n)$$ for the output of $$T$$ with input $$n$$. This output is either a natural number, if $$T$$ halts, or undefined if $$T$$ does not halt. The set $$\NN\times\NN$$ can be encoded as natural numbers to be input to $$T$$, for example by encoding $$m$$ and $$n$$ as unary numbers as strings of $$1$$'s, with a single $$0$$ separating them, so we also write $$T(m,n)$$, where this encoding is implied.

If the Halting problem is algorithmically decidable then there is a Turing machine $$H$$ which outputs $$1$$ if its input is a pair $$(m,n)$$ from $$S$$ and $$0$$ otherwise. From $$H$$ we can clearly build a Turing machine $$G$$ which halts with output $$0$$ if $$H(k, k) = 0$$ and runs without halting if $$H(k, k) = 1$$. Let $$g$$ be the Turing number of $$G$$ and consider $$H(g, g)$$. On one hand, if $$H(g, g) = 0$$ then $$G(g)$$ halts, and so $$H(g, g) = 1$$, a contradiction. On the other hand, if $$H(g, g) = 1$$ then $$G(g)$$ does not halt, and so $$H(g, g) = 0$$, also a contradiction. Thus we conclude that the Halting problem is not algorithmically decidable.