6 ms·
An "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 instanc
by meastham 16y ago
An "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 16y 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 16y ago[deleted]
- Groxx 16y 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 16y agoWhy are you only looking at the program and ignoring the wrapper? The detector should also look at the wrapper.
- Groxx 16y 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 16y 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 16y 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.
- ars 16y 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 16y 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.