[FOM] fun with paradoxes

[Alasdair Urquhart]

> Assume that the halting problem is undecidable. Let us consider a
> Turing machine - H - which behaves as such: given a (program, input)
> pair as input, accept it if the program halts on the given input and
> reject it if it loops. Clearly, because the halting problem is
> undecidable, this Turing machine cannot halt for all (program, input)
> pairs. Now, let us construct another Turing machine - G - which, by
> simulating and using the results of H, has the following behavior: if
> the input to this machine, which is the encoding of a Turing machine,
> halts when applied to itself, we halt. Otherwise, we loop forever.
> Now, consider what happens when we try and determine if G halts using
> H. Clearly, H cannot halt, for otherwise G would contradict itself.
> However, if H cannot halt when applied to G, then G cannot halt
> because it is defined in terms of this very result. And, if G cannot
> halt, then clearly H must halt when given G, a contradiction!

There is no paradox.  If the halting problem is undecidable, then
there is no such machine as H, that is to say, there is
no machine "which behaves as such: given a (program, input)
pair as input, accept it if the program halts on the given input and
reject it if it loops."  However, the author goes on to assume that
there is such a machine, for example, in the passage:

"then clearly H must halt when given G, a contradiction!"

This illustrates the familiar fact that if you assume contradictory
premisses, then you can prove all kinds of marvellous things.