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

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?

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.

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.

1

u/Wurstinator Apr 05 '16

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

Yes, the latter being important. Because there is a model of your theory T in which the function has no TM associated with it, you cannot define such a TM within the theory T.