5 ms·
I still wonder why the anti-halting-detecting-program + halting-detecting-program aren't viewed as a single program, as they can't be separated from each other
by Groxx 17y ago
I still wonder why the anti-halting-detecting-program + halting-detecting-program aren't viewed as a single program, as they can't be separated from each other in the proof. By wrapping the detector in an external application, aren't you modifying the detector, changing the assumptions of the proof?
An external halting detector (such as one of us) would tell you the hypothetical arrangement would never halt. If we can prove it would never halt, can't a program?
- meastham 17y agoAn "external halting detector" couldn't correctly tell if the arrangement would halt. If we decide that the input of the program halts, then the wrapper instance loops infinitely and we were wrong. If we decide that the input of the program doesn't halt, then the wrapper halts and we were also wrong.
- Groxx 17y agoThat's just it, in that case we are part of the process, because we affect the operation / output. Any halting detector looking the whole thing, which must include us, would show that we always negate what comes out of what we're doing, and would say so. Just like you did. You've accounted for all output, and demonstrated that it always negates us. By that, if a halting detector cannot exist, then how do we exist? We can tell if a hypothetically-impossible device (Q calling P and reversing the output) will loop forever or not.
- deleted 17y ago[deleted]
- Groxx 17y agoBy changing the detector, you're surely a defector from the point of the proof. If what comes out is made moot, give the whole thing the boot: look at it from the roof. edit: previous comment requested my argument in rhyme :) edit2: second verse! If the halt-checker is wrapped, isn't it not? Since we've just solved it, why can't a 'bot? Just what's going on here? So if it's internal... ... this damned, infernal... Lets just go get a beer.
- ars 17y agoWhy are you only looking at the program and ignoring the wrapper? The detector should also look at the wrapper.
- Groxx 17y agoExactly what I've been thinking since I first heard this proof. (this comment partially motivated by a "woot! someone agrees!", and partly to say congrats on your evil-th day here!)
- ars 17y agoHeh :) But I prefer the Jewish interpretation: http://ohr.edu/ask_db/ask_main.php/277/Q1/ http://ohr.edu/ask_db/ask_main.php/277/Q1/
- scott_s 17y agoIt 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.
- johnrob 17y agoThe poem got me thinking critically as well. Here is how I rationalized it: No single program can ever predict the output of another one, because the program doing the predicting could theoretically be embedded in the program being analyzed. People can theoretically predict outcomes, because they cannot be embedded in programs.