4 ms·
It does look at the wrapper. The problem is that whatever decision P makes about Q, Q then goes and does the opposite. Consider: def P(program): if progr
by scott_s 17y ago
It does look at the wrapper. The problem is that whatever decision P makes about Q, Q then goes and does the opposite. Consider:
def P(program):
if program halts:
true
else:
false
def Q(program):
if P(program):
false
else:
Q(program)
When we call Q(Q), we call P(Q). Let's say P(Q) returns false; P says that Q halts. In that case, the conditional fails, and we then call Q(Q) infinitely. Q has done the opposite of what P said it would do.
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.
- ars 17y agoWho allowed Q to call P? 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.
- scott_s 17y agoI don't understand your question. Q calls P because it's defined to do so. 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.
- ars 17y agoHow is Q even aware the P even exists? Q is running inside P, it should not have any idea that P is examining it.
- deleted 17y ago[deleted]
- deleted 17y ago[deleted]
- scott_s 17y agoP doesn't detect the paradox. We do. We have intelligence; algorithms follow a prescribed set of rules. No one is sure what, exactly, "intelligence" is, but we can say it's not the same as just an algorithm. We're also not guaranteed to be correct. Remember that P is a program to detect whether any program halts. It's possible to write a program that can detect if some programs will halt. You just have to constrain what the programs can do to the point that the rules the programs can follow will not be Turing-complete. We could also use machine-learning techniques to try to recognize the structure of infinite-loop programs, but that's not the same as an algorithm that is always correct.
- Groxx 17y agoTo state that requires the assumption that we are qualitatively different than a program. I believe that's been a question since far before Turing's time. What if we are equivalent to a program? Then a program can be made to detect paradoxes.
- scott_s 17y agoI'm comfortable stating that we are qualitatively different than an algorithm. I'm also comfortable stating that we're probably similar to a Bayesian machine-learning process which is only able to make probabilistic determinations.
- Groxx 17y agoSame here, just felt it needed to be pointed out. There are plenty of people who do make the claim, in which case experience appears to disprove the proof.
- argv_empty 17y agoWhat if we are equivalent to a program? Then a program can be made to detect paradoxes. It has not been shown that all paradoxes are human-detectable.
- deleted 17y ago[deleted]
- BrandonM 17y agoYour explanation is good, but your pseudocode doesn't match what you're saying about it. There is a bug. One way to write it would be: 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 Now, calling P(Q, Q) is what shows the truth of the Halting Problem. 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 As long as programs like Q are allowed in your language, P cannot exist. Now, if you constrain Q such that every loop and recursion includes a proof of completion* , you can write a program P. * This is generally possible by annotating the loop with a mathematical proof that the looping mechanism is approaching a terminating condition)
- Groxx 17y agoWhile 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 ago