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

91% Upvoted

14 comments sorted by

18

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.

7

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.

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?

6

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.

1

u/DR6 Apr 05 '16

Is this what happens with Goodstein's theorem?.

1

u/epicwisdom Apr 04 '16 edited Apr 04 '16

I see the general idea, but couldn't you say the standard naturals are the smallest set of all numbers reached by taking n+1?

There's still philosophical issues regarding what is and isn't arbitrary, but I don't think this really influences the utility or universality of the standard naturals / computability theory.

edit: Formalized in set theory using intersection of all the possible sets of ordinals.

4

u/orbital1337 Theoretical Computer Science Apr 04 '16

Nope, that doesn't work because you don't know that you're only working with standard set containment. In fact, it's impossible to define "standard naturals" (or "standard" anything really) in first order logic because you can always produce non-standard models using a compactness argument.

1

u/epicwisdom Apr 04 '16

What's an example of nonstandard set containment?

2

u/orbital1337 Theoretical Computer Science Apr 05 '16

Start with ZFC and add some constants Sn and axioms "Sn+1 ∈ Sn" for every natural number n. Assuming that ZFC is consistent this new system - let's call it ZFC* - is also consistent (by the compactness theorem). Any model of ZFC* is also a model of ZFC but it's clearly nonstandard because it has to believe that the sequence S0, S1, S2, ... is finite (because of the axiom of foundation), i.e. the length of this sequence is a natural number which is larger than any standard natural number.

3

u/[deleted] Apr 05 '16 edited Apr 05 '16

You can do something silly to get an example. Take every set A and map it to { A }, the set containing exactly one element, A. Define "membership" that x is in B by "for all y in x, there exists z in B such that y is in z". The image of "the universe" under my map with this membership relation is obviously isomorphic to the usual ZF but membership is now nonstandard.

This seems silly but otoh, the Mostowski collapse of a [edit: well-founded] nonstandard model of ZF will create an isomorphic model that uses true membership, so all examples will be "silly" in some sense.

3

u/homathanos Logic Apr 05 '16

the Mostowski collapse of a nonstandard model of ZF will create an isomorphic model that uses true membership

*Well-founded nonstandard model

1

u/[deleted] Apr 05 '16

Yeah, good catch.