On Tue, May 1, 2018 at 1:13 PM, James Davis <lorentztrans@gmail.com> wrote:
On Tue, May 1, 2018 at 7:19 AM, Cris Moore <moore@santafe.edu> wrote:
... For any set of axioms, there is a Turing machine which 1) never halts and 2) that set of axioms cannot prove that it never halts. ...
But don’t you agree that the Halting Problem has a definite truth value? In other words, that a given Turing machine (with a given input) either runs forever or doesn’t, regardless of our ability to prove it? ...
To answer the question posed, shouldn't we ask if, given any *particular* TM, there exists *some* consistent system/set of axioms that can prove whether it halts or not? I was under the impression that the answer here was "yes", regardless of any individual consistent system being unable to tackle the general problem.
The problem is when you have nonstandard natural numbers. It's perfectly valid, for instance, to have a Turing machine halt after ω + 3 steps. You can say, "oh, but we use the unique standard model defined by the second-order theory", but then the second order theory has to live in some universe, and there are universes in which what's uncomputable in your universe can be computable in mine: http://jdh.hamkins.org/every-function-can-be-computable/ https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/ So as soon as you move away from "only physically implementable math is real", then you have do deal with all these other models. -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com