An interesting proof by Hamkins and a lot of discussion of its
significance on John Baez's blog. It agrees with my intuition that the
mathematical idea of "finite" is not so obvious.
Brent
-------- Forwarded Message --------
On Tue, May 1, 2018 at 1:13 PM, James wrote:
On Tue, May 1, 2018 at 7:19 AM, Cris 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
_______________________________________________
math-fun mailing list
math-...@mailman.xmission.com
https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
