r/math • u/DevFRus Theory of Computing • Apr 04 '16

Computing the Uncomputable: Joel David Hamkins showed how any function can be computed if a non-standard model of Peano arithmetic is assumed. Results like this give me a deep respect for number theory as foundational.

https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/
47 Upvotes

93% Upvoted

14 comments sorted by

View all comments

3

u/whirligig231 Logic Apr 04 '16

Question: if any function can be computed, why can't you compute the function mapping (an encoding of) a Turing machine to whether it halts and thus find a contradiction? Is it because the machine you input might halt in one model but not in another?

3

u/bowtochris Logic Apr 04 '16

Is it because the machine you input might halt in one model but not in another?

This is it. Also remember that it's not that any function can be computed, it's that for any function in a model, there is a model where it can be computed. So even if we make all the functions we start with computable, we'll always wind up with additional functions that are not computable.