Perhaps more controversially, I claim: Under the correct model M’ it seems that it’s impossible for a substantive question (such as Q) to be unanswerable.
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.
All this adds up to: The P versus NP problem (and questions like it that can be phrased as definitive questions about reality) must have an answer unless our model of reality is incomplete.
Then all possible models of reality are incomplete.
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.
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).
Whether a Turing Machine ever halts is a concrete question with a definite yes or no answer
This doesn’t seem right. In different models, different TMs halt, and it’s impossible to specify which model you really mean as settling the question. You can even decide, of your own free will, whether certain TMs halt or not (if you’re simulated by them, say). So, it should rather be the more trivial “In any given structure, whether a TM execution defined on it halts, is a property of that structure.”
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).
This doesn’t seem right. In different models, different TMs halt, and it’s impossible to specify which model you really mean as settling the question. You can even decide, of your own free will, whether certain TMs halt or not (if you’re simulated by them, say). So, it should rather be the more trivial “In any given structure, whether a TM execution defined on it halts, is a property of that structure.”