Why are you only looking at the program and ignoring the wrapper? The detector should also look at the wrapper.
def P(program):
if program halts:
true
else:
false
def Q(program):
if P(program):
false
else:
Q(program)
Now let's say that P(Q) returns true; P says that Q does not halt. In that case, the conditional succeeds, and Q returns false - it halts. Again, Q has done the opposite of what P said it would do.
Here we have a situation where Q will always do the opposite of what P says it will do. We've constructed a situation where P is always wrong; we've created a paradox. The only way out of it is to say P cannot exist.
Q is running inside P, and should have no access to it. I'm analyzing a program, the program doesn't get to ask me questions.
I described the runtime behavior because that's easy to grok. Presumably, any P must do some sort of "Oh, this happens, so that must happen." Whether we call that "running" or "inspection" is irrelevant.
Q is running inside P, it should not have any idea that P is examining it.
def P (program, input):
if [program on input] halts:
true
else:
false
def Q (input):
if P(Q, input):
Q(input) # P says we halt, so we won't
else:
true # P says we don't halt, so we will
It may be hard to think of conceptually, but when you explicitly state it all, it's pretty easy. P is a program. Q can be a program with P embedded in it. This is not anything unrealistic at all. Furthermore, calling P on (Q, Q) is not all that strange either, until you consider the resulting behavior:
P(Q, Q) -> should return true if Q halts on Q and false otherwise
Q halts on Q:
P -> true
Q loops. P was wrong
Q doesn't halt on Q:
P -> false
Q exits. P was wrong again
* This is generally possible by annotating the loop with a mathematical proof that the looping mechanism is approaching a terminating condition)
To my mind, it seems logical that if P reaches a paradox, it never returns. It's an infinite logical loop, never finishing, thus never returning true or false. Like evaluating "this statement is false", it's stuck on "if it's true, it's false. If false, true". To that end, the paradox isn't a paradox: it just never finishes.
If this is the case, then P(Q(Q)) does indeed escape the problem entirely: it shows that Q(Q) will never finish. That argument I've made, and I've seen others make, but the realization of the previous paragraph is new. And nobody I've debated this with has really attempted to look outside of "but it's a proof, it proves it", and re-iterating the steps of the proof. Not that many have tried for very long, they usually get upset that I can't see the "obvious". Thanks for sticking it out, I've had longer to think on this than I've had with others, and that may have been what I needed.
This reveals a missing assumption in the proof, or at least one I've never seen stated: that P must finish. If it must finish, then I accept the proof completely. If it's a paradox, I agree, it's a paradox, and it certainly is within that requirement. It must return, but it cannot, therefore it can not exist.
But then I must ask: Why must P finish on all inputs? I can make a program which doesn't (print(num) when passed Pi), why not this one?
I'd be very interested in any input / rebuttals to this. I'm not trying to be difficult, honest! I've understood the proof where P must finish for quite a while, but I don't see that it's a valid assumption if categorically stating that it's inherently un-doable.
In other words: can you make a P that decides correctly for -some- programs, but never gives an answer for others? Sure. (E.g., if the program is "while(true) {}", then it loops, otherwise I don't know.) But unless P works (terminates and gives a decision) for any arbitrary program, it's not generally useful.
But I think you're missing the more important point. We defined P to be a certain way, and as a result of that definition, we also demonstrated that it cannot do what we defined it to do. That's the fundamental problem. If you want to think of it in terms of what you're currently hung up on, then consider that implicit in our definition of P is that it will finish.
Also consider that if P does not finish, it's no better than just running the program with its input and observing the behavior.
As to the definition, I suppose, though it's largely implicit, which is effectively a big no-no in proofs. But that doesn't show that a real-world P must finish. If it doesn't, the failure of it to finish can be detected as detecting a paradox: just detect if the halt-detection halts.
P(Q) will finish because we defined it to do so. It will return either true or false. The problem isn't with the termination (or non-termination) of P(Q), it's with Q(Q). The termination status of Q(Q) is what gives us the paradox: its behavior is the opposite of what P(Q) said it would be. If we can construct a case where P behaves contrary to its definition, then it cannot exist.
In other words, we asked our oracle "Will Q finish?" and our oracle gave us a reply. Then Q went off and did the exact opposite, proving the oracle wrong. But our oracle is, by definition, always right, so we have a Serious Problem. We resolve this Serious Problem by recognizing that we asked our oracle a question that it can never know the answer to.
Remember that Q(Q) is what gives us the paradox in the first place. P(Q(Q)) is nonsense. It's like recognizing that 4/0 is undefined, then trying to define cos(4/0).
I think your discussion about a "real-world P" begs the question. (In the original meaning of the phrase.) The existence of P presents us with a paradox, so how can there be a real-world P?
By allowing it to not finish on paradoxical situations, it can exist in what would normally be a paradox. Thus P(Q(Q)) can indeed exist, because P(Q) does, even though it does not return.
There may still be a way to prove such a paradox-avoiding P cannot exist; I'm not claiming that. Just wondering why we require it to return, when as far as I can tell there's no legitimate, real-world reason to do so. Sure, it makes the proof easier, and allows us to use simple logical grammars... but since when has "simple" always been correct?
The equivalent would be the oracle remaining silent, denying the paradox the possibility of existing. If no statement is made, no paradox can be formed.
When constructing proofs, we can make assumptions and then run with them. But it's not valid to assume magic - and that's essentially how you want to define P. You want P to be able to detect that it has been used in a paradoxical situation. But it's not reasonable to assume a function knows how it's being used; to do so is basically magic.
We require that P returns because we defined it as a function in the mathematical sense, and mathematical functions have to provide an answer (even if that answer is "undefined"). P is a function that has to return true or false. No other responses, including not giving us an answer, are valid.
It doesn't need to detect its own use (though remember: reflection), it just needs to see when a separate use of it will cause a paradoxical situation. The proof wouldn't exist if P(Q) weren't part of Q, because that's what sets up the paradox: it's own return cannot be correct... unless it has another output, maybe?
And when I see a proof that a program cannot detect paradoxes, I'll accept that a modified P cannot. But I've never heard of anything along those lines. Until then, a mis-applied proof simply stifles attempts which may have been fruitful.
The point of the problem is this: to create a program P that will tell us if f(x) halts or not. Q is simply a function that breaks P so that it cannot give the right answer. Thus making P impossible.
Paradoxes are irrelevant to the issue :)
(You're over thinking this a lot; read one of the formal proofs and it will address pretty much all of your points)
Instead of banging your head against this proof more, I think you may want to read up on proofs in general. Your objections would apply to any proof by contradiction.
Example: consider that Q exists even if we don't define it. We discovered it, not invented it. Given P, we can define Q', but the problem with Q is still there. But this really has nothing to do with this specific proof - it's more fundamental than that.
And now P is a nonsolution to the original problem (the halting problem). The original problem was to come up with a program that always decides whether its input program halts. We already can build programs that identify the programs which halt and say nothing about programs that don't -- this is a trivial extension to any working interpreter for the language in question.
(this comment partially motivated by a "woot! someone agrees!", and partly to say congrats on your evil-th day here!)
But I prefer the Jewish interpretation: http://ohr.edu/ask_db/ask_main.php/277/Q1/