As a quick additional note, you may observe that if we order the 
possible inputs the halts function (both considered as integers) in a 
big matrix, then the the call halts(i,i) is taking elements along the 
*diagonal* of this matrix, and the function D is modifying the output of 
the halts function along this diagonal.  Hey, diagonals! It's another 
diagonalization proof! The wikipedia article has a bit more thorough 
explanation of this:

http://en.wikipedia.org/wiki/Halting_problem, bottom of the `Sketch of 
proof' section.

Post a reply to this message