= 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)
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.