John 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 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.