= 27d567bc2d48d9f40e9ccc20ea370b15)
Incorrect comments on What independence between ZFC and P vs NP would imply - 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 (62)
Have you heard of Gödel's incompleteness theorems?
Whether a Turing Machine ever halts is a concrete question with a definite yes or no answer; but, if we could construct an axiomatic system with a recursively enumerable set of theorems such that for each Turing machine a theorem existed stating whether the machine halted or not, then we could build a decider for whether any Turing machine halts.
Then all possible models of reality are incomplete.
also see: http://en.wikipedia.org/wiki/David_Hilbert#Formalism
Whether a Turing Machine halts after a certain number of steps has a definite answer. But whether it halts eventually does not necessarily; what empirical data could prove that it halts eventually, other than seeing it halt?
An observation of a loop, a portion of the tape encoding a value that's decreasing each loop, and a check for it falling below a threshold that would lead to a halt?
That would only work for some turing machines. Incidentally, it's perfectly possible to decide for particular finite turing machines whether it halts - basically either set a time-out equivalent to the Busy Beaver for that TM (and it either halts before, or blows the time-out in which case it never halts), or, IIRC, you can store every configuration of the tape it passes through and if it repeats any configuration, then it will not halt. Neither of these is especially useful.
Of course. I made no claim at having solved the halting problem. My response was specifically to,
There is nothing else that will reliably show this for all machines. There are absolutely things that will show this for some machines.
Those heuristics and any others you come up with will fail to tractably confirm whether some machines halt.
Yes, but they can confirm that some machines will halt, without observing that they have halted, which seemed to be what was asked for. Any such approach must of course say "I don't know" (or itself fail to halt) in some cases.
My apologies, I was imprecise in my original comment. I was trying to get at the fact that "whether Turing machine M halts" is not actually a concrete question, as had been claimed above (I was assuming that the reason it was presumed to be concrete is because you can just watch the machine and it either halts or doesn't, and my point was that you can't actually just watch a machine to see if it will halt).