3 ms·
While running some errands, I think I realized the core of my trouble accepting this proof. I think it may be the same for a lot of people, but I've never hear
by Groxx 17y ago
While running some errands, I think I realized the core of my trouble accepting this proof. I think it may be the same for a lot of people, but I've never heard it stated, so here it is:
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.
- jorgeortiz85 17y agoTh original P is defined as a program that can decide whether any program halts or not. If your proposed P doesn't terminate for some programs, then it hasn't made a decision, and it's not really the P you set out to find. 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.
- Groxx 17y agoGood point. But that doesn't mean it's useless. Check it with an external P: If it's a paradoxical process like is given in the proof, it won't finish, which will be detected, uniquely, as a paradox because it won't halt.
- argv_empty 17y agoFor what finite number of steps can we watch the program and know afterwards that it will never halt in the future?
- scott_s 17y agoThere's a difference between P(Q(Q)) not being able to finish its evaluation and P(Q(Q)) stating that Q(Q) will never finish. If P does not finish, then you have no answer. If you have no answer, then P does not do what we defined it to do. 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.
- Groxx 17y agoNo, P(Q(Q)) will finish, because P(Q) will not, and Q(Q) will call P(Q), preventing Q(Q) from halting. 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.
- scott_s 17y agoWe're doing proof sketches, not formal proofs. In a formal proof, it would be explicit. A proof sketch is to show the big concepts behind the proof. The formal proof grinds through the details to make sure those concepts do, in fact, pan out as we think. 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?