4 ms·
We encounter the paradox of P because of the definition. It doesn't need to detect its own use (though remember: reflection), it just needs to see when a separ
by Groxx 17y ago
We encounter the paradox of P because of the definition.
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.
- ErrantX 17y ago> We encounter the paradox of P because of the definition. 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)
- scott_s 17y agoHonestly, I think the difficulty you're having is one of form, not content. That is, you understand the mechanics behind the proof, but you don't accept that the form of the proof works. Your objections hinge on the implications of a paradox, and our seemingly arbitrary construction of Q. 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.