is the normal proof of halting problem undecidability is wrong?

122 Views Asked by At

The normal proof goes as follows:

if H(f) is a program that takes the source code of any program f and return whether it halts, we define G to be

if(H(G)){ loop forever } else { halt } Which is a contradiction if you run H on G.

My problem is the unjustified assertion that a program like G even exists, as presumably it is able to print its own source code and run H on it (or something analogous to that) and halt or not halt based on that. My intuition tells me this violates some information theoretic result I am not smart enough to know about.

Furthermore, since we have no idea what H even looks like, this proof only works if you can prove that for every program P, there exists a program G which can print its own source code, run P on it, and then do some stuff based on that. Since the mere existence of Quines, which still conserve information, is already a deep and complicated result (from what I can tell), the truth of Gs existance is sketchy to say the least.