= 27d567bc2d48d9f40e9ccc20ea370b15)
David_Bolin comments on Open Thread - Aug 24 - Aug 30 - Less Wrong Discussion
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.
Also, there is definitely some objective fact where you cannot get the right answer:
"After thinking about it, you will decide that this statement is false, and you will not change your mind."
If you conclude that this is false, then the statement will be true. No paradox, but you are wrong.
If you conclude that this is true, then the statement will be false. No paradox, but you are wrong.
If you make no conclusion, or continuously change your mind, then the statement will be false. No paradox, but the statement is undecidable to you.