Solution to the Halting problem

The diagram to the left is not a "rigorous" proof, but illustrates the solution. The same applies to the almost one sheet summary. For the proof, download the whole paper.

The halting problem is the problem of determining whether a Turing machine will halt for a given input. One of the results of modern computing theory is that the halting problem cannot be solved. However, this argument, a proof by contradiction, like any other argument has premises. Two of the hidden premises are (a) that there is no distinction between the potential and actual infinite, and (b) that proof by mathematical induction is a form of algorithm. The important point is to realise that there is a distinction between proving that we

*know*something and having an algorithm that computes a result. The impossibility proof, then, is a proof that any machine that computed an algorithm would need an actually infinite number of parts, and as this is impossible, a computer cannot be built to solve the problem. But this is only an impossibility proof for computers, not for the human mind. It turns out that a proof that the halting problem for any Turing machine can be solved is a relatively simple induction on the number of states of a Turing machine.