\( \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\TT}{\mathbb{T}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\H}{\mathcal{H}} \newcommand{\e}{\epsilon} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \)

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.