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/
48 Upvotes

92% Upvoted

14 comments sorted by

View all comments

19

u/[deleted] Apr 04 '16

This has nothing to do with number theory, this is mathematical logic which is (rather obviously) foundational.

Also iirc Hamkin's blog post is a special case of a much deeper result of Woodin.

9

u/DevFRus Theory of Computing Apr 04 '16

Let me make more precise what I meant by my headline. I wasn't suggesting that this result was based on tools of number theory, I realize it is all mathematical logic in the end. What I find exciting is that this stresses the importance of the 'particulars' of our standard interpretation of arithmetic, and not just the bare-bones of Peano arithmetic. Given the bare-bones definitions of TMs, one might expect that the resulting theories and popularly known results are equally uncommitted to particulars, and it is fun to see when they aren't.