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
of all pairs in where is a Turing number and the
corresponding Turing machine will halt given input .

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

If the Halting problem is algorithmically decidable then there is a Turing
machine which outputs if its input is a pair from and
otherwise. From we can clearly build a Turing machine which halts with
output if and runs without halting if . Let
be the Turing number of and consider . On one hand, if
then halts, and so , a contradiction. On the
other hand, if then does not halt, and so ,
also a contradiction. Thus we conclude that the Halting problem is *not*
algorithmically decidable.