[FOM] fun with paradoxes

[hxl]

Hello all. I have listed below, for your pleasure, a paradox which
arises when you assume that the halting problem is undecidable. If you
can resolve this paradox, you win! (Of course, I already know the
answer and, if nobody gets it right, I will release it after some
time.)

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!

P.S. A similar paradox arises when one assumes that the real numbers
are not enumerable. Perhaps I will post this later.