= 27d567bc2d48d9f40e9ccc20ea370b15)
David_Bolin comments on Open Thread - Aug 24 - Aug 30 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (318)
I'm very confused about something related to the Halting Problem. I discussed this on the IRC with some people, but I couldn't get across what I meant very well. So I wrote up something a bit longer and a bit more formal.
The gist of it is, the halting problem lets us prove that, for a specific counter example, there can not exist any proof that it halts or not. A proof that it does or does not halt, causes a paradox.
But if it's true that there doesn't exist a proof that it halts, then it will run forever searching for one. Therefore I've proved that the program will not halt. Therefore a proof that it doesn't halt does exist (this one), and it will eventually find it. Creating a paradox.
Just calling the problem undecidable doesn't actually solve anything. If you can prove it's undecidable, it creates the same paradox. If no Turing machine can know whether or not a program halts, and we are also Turing machines, then we can't know either.
There is no program such that no Turing machine can determine whether it halts or not. But no Turing machine can take every program and determine whether or not each of them halts.
It isn't actually clear to me that you a Turing machine in the relevant sense, since there is no context where you would run forever without halting, and there are contexts where you will output inconsistent results.
But even if you are, it simply means that there is something undecidable to you -- the examples you find will be about other Turing machines, not yourself. There is nothing impossible about that, because you don't and can't understand your own source code sufficiently well.
The program I specified is impossible to prove will halt. It doesn't matter what Turing machine, or human, is searching for the proof. It can never be found. It can't exist.
The paradox is that I can prove that. Which means I can prove the program searching for proofs will never halt. Which I just proved is impossible.
I looked at your specified program. The case there is basically the same as the situation I mentioned, where I say "you are going to think this is false." There is no way for you to have a true opinion about that, but there is a way for other people to have a true opinion about it.
In the same way, you haven't proved that no one and nothing can prove that the program will not halt. You simply prove that there is no proof in the particular language and axioms used by your program. When you proved that program will not halt, you were using a different language and axioms. In the same way, you can't get that statement right ("you will think this is false") because it behaves as a Filthy Liar relative to you. But it doesn't behave that way relative to other people, so they can get it right.