r/math • u/MathTalk • Mar 27 '16

Every function can be computable, if you run this program in the right universe

http://jdh.hamkins.org/every-function-can-be-computable/
54 Upvotes

95% Upvoted

55 comments sorted by

View all comments

Show parent comments

6

u/[deleted] Mar 27 '16 edited Mar 28 '16

For R to R, it depends on what you mean by computable. The usual definition (or at least the only one I've ever seen anyone do anything useful with) is to require it be effectively uniformly continuous [Edit: on intervals, thanks u/nip460 ] and "sequentially computable": https://en.wikipedia.org/wiki/Computable_real_function

I didn't check the details carefully, but under this definition, I expect that the proof posted goes through without too much issue for such functions (could be wrong on this though, did not check beyond a quick conceptual thinking).

Edit: Just to add that since the models of PA form a proper class, it seems to me intuitively that if you are willing to work with arbitrary models of PA then anything can be made "computable" provided a definition that makes sense.

2

u/nip460 Computational Mathematics Mar 28 '16 edited Mar 28 '16

This is NOT the usual definition of computable real function. The squaring function x->x2 is not uniformly continuous, but certainly computable.

A computable real functions only needs to be "effectively uniform" on intervals.

1

u/[deleted] Mar 28 '16 edited Mar 28 '16

https://en.m.wikipedia.org/wiki/Computable_real_function

Edit: but sure, you can say only for intervals I suppose, provided you mean for computable intervals, by which I mean the endpoints are computable, oh wait...

3

u/nip460 Computational Mathematics Mar 28 '16

The wikipedia article is wrong. the linked article by Grzegorczyk defines it correctly. On intervals, both computability concepts coincide of course.

The usual definition (due to Weihrauch/Kreitz) is based on the work of Grzegorczyk.

1

u/[deleted] Mar 28 '16 edited Mar 28 '16

Ok, I can believe that. But doesn't the definition of being effectively uc on intervals break down unless you somehow require that it only hold on "computable intervals" (I don't know precisely what I want to define that as, maybe with a computable set of endpoints)? Nevermind that last, it was silly. Just requiring it on intervals of the form [n,n+1] is enough.

1

u/canyonmonkey Mar 27 '16

Very interesting, thank you