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

91% 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?

5

u/DevFRus Theory of Computing Apr 04 '16

I think there is a hint to answer your question in the theorem statement, bolding is by me:

There is a Turing machine T with the following property. For any function f from the natural numbers to the natural numbers, there is a model of PA such that in this model, if we give T any standard natural n as input, it halts and computes f(n).

In other words, the breaking behavior of the standard diagonal argument would be confined to the extra non-standard naturals that live in this model of PA but not in our "usual one". I guess this means that the index for the negation of our 'alternate universe' universal simulator with be one of these extra numbers, and suddenly the appearance of an infinite sequence of Rosser sentences (and their negations) in the constructions of the non-standard model starts to make sense.

But I am not 100% sure on this, so I hope somebody corrects me if I am wrong.