How does the Halting Problem have a contradiction?

Question

I’ve seen explanations about this, but I don’t see how will the program run in the first place. Example program that will be fed to itself:

define haltOrLoop(P):
if halt(P): loop forever
else: exit

If we run `haltOrLoop(haltOrLoop)` wouldn’t that be incomplete as `haltOrLoop` (the one inside the parenthesis) needs a program to run first?

In: 2

Answer 1

The details of `haltOrLoop()` are not important. The proof by contradiction is sufficient without any consideration for how it would be implemented.

The only thing the proof must do is propose, “assume `haltOrLoop()` is possible”. *How* it is possible isn’t important. We’re stating as a given that it is possible.

Once it is merely stated that it is possible, we show how that very simple assumption all on its own creates a contradiction. The only logical conclusion, then, is that `haltOrLoop()` is *not* possible. Not for the reason you’re asking about regarding recursion, but in general. There is literally no conceivable way to build `haltOrLoop()`. At all. Recursion or no.