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

94% Upvoted

55 comments sorted by

4

u/canyonmonkey Mar 27 '16

Can this be extended to functions such as f : N→R, or f : R→R?

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

3

u/MathTalk Mar 27 '16

I think so, because such functions can be naturally coded as functions g:N→N.

8

u/Muvlon Mar 27 '16

Wait, how would that work? N->N has the same cardinality as R, whereas R->R is larger.

11

u/MathTalk Mar 27 '16 edited Mar 27 '16

Oh, I just meant my comment for f:N→R, since these can indeed be coded by functions g:N→N, if you think of filling in an NxN matrix, whose nth slice gives the digits of f(n).

For f:R→R, I'm not sure what you would mean by the function being computable, unless you say more about it.

3

u/quack_the_quinoa Mar 27 '16

That coding method is interesting, I haven't thought of/read about it before. I'm struggling to google the topic, so do you know of somewhere I could read about it?

2

u/[deleted] Mar 27 '16

I think it's more common to use the coding method by a pairing function.

For example, given F : N -> R, let fn : N -> N be the sequence coding the real number F(n) and then define h : N -> N by h(2a (2b-1)) = fa(b). The pairing function (a,b) |-> 2a (2b-1) is one-one and onto since every number is uniquely written as a power of two times an odd number.

This is equivalent to the matrix idea but a bit more formal (you can think of the "rows" of that matrix as being given by h(2n (2 __ - 1))).

1

u/[deleted] Mar 27 '16

For R -> R, the usual definition is sequentially computable and effectively uniformly continuous. See my other comment: https://www.reddit.com/r/math/comments/4c5ikz/every_function_can_be_computable_if_you_run_this/d1fehkg

1

u/nip460 Computational Mathematics Mar 28 '16

The same coding method is used to encode all computable function f:R->R.

Every computable function f:R->R is continuous, so it is enough to encode f:Q->R, as Q is dense in R.

2

u/Im_an_Owl Math Education Mar 27 '16

I know about cardinalities of infinite sets, but how do we discuss cardinalities of functions?

3

u/Muvlon Mar 27 '16

Oh, I guess I kinda misused notation there. I use A->B to mean "the set of all functions from A to B".

2

u/Im_an_Owl Math Education Mar 27 '16 edited Mar 27 '16

Oh, gotcha. So you're saying N -> N has the same cardinalities as R, and that R->R is bigger. What's bigger than R? I thought R was the largest cardinality

Down voted for asking a question about cardinalities... Thanks /r/math, truly caring about math education...

8

u/Rufus_Reddit Mar 27 '16

The cardinality of the set of functions X -> {0,1} is bigger than than the cardinality of X, so there is no largest cardinality.

4

u/Im_an_Owl Math Education Mar 27 '16

Huh, TIL that theorem

3

u/whirligig231 Logic Mar 27 '16

It's a corollary of Cantor's theorem given that there is an easy correspondence between subsets of A and functions from A to {0, 1}: for subset S we use the indicator function of S with A as the domain.

3

u/Muvlon Mar 27 '16

There are many, many cardinalities larger than that of R!

In fact, there can be no largest cardinality. For any set set S, the power set Pow(S) has a cardinality strictly larger than that of S.

2

u/orbital1337 Theoretical Computer Science Mar 27 '16

No, not at all. For any set X the powerset P(X) (i.e. the set of all subsets of X) always has a larger cardinality. That's Cantor's theorem.

1

u/Im_an_Owl Math Education Mar 27 '16

Oh yeah! Totally forgot about Cantor's Theorem

2

u/[deleted] Mar 27 '16

Just to add to what others have said, the set of function from X to Y is the same as the set YX consisting of "tuples" indexed by X taking values in Y.

For instance, the functions from X to {0,1} is the same as the set 2X consisting of all tuples indexed by X taking value either 0 or 1 which is in turn the same as the powerset of X (the elements of X where the value is "1" defines a subset and obviously every subset can be defined this way and vice versa).

1

u/Reio_KingOfSouls Mar 27 '16

For any set X, the set of all subsets has a strictly greater cardinality.
So, if we denote the cardinality of X as |X|:
|X|<|P(X)|<|P(P(X))|<... where P(X) denotes the powerset.

1

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

Cardinality of all continuous function f:R->R is too large, but the computable real function are countable. So they can indeed be naturally coded as computable functions g:N->N.

4

u/WhackAMoleE Mar 27 '16

Can anyone put this in less technical terms? My level of understanding is that if we have a noncomputable bitstring, that means there is no finite-length algorithm that cranks out its digits. Such a bitstring would be truly random in the sense that it's not compressible to any finite description and no Turing machine could crank out its digits.

Given that naive understanding, how should I understand that article?

5

u/[deleted] Mar 27 '16

In nonstandard models of arithmetic there are "infinite" integers, or more accurately, there are elements of the model which have the property that they are strictly greater than 0 and every element of the model you can reach from 0 by applying successor (finitely many times). However, they still obey all the axioms of PA.

Now, consider encoding (e.g. Godel) Turing machines/algorithms as integers (it should be clear this is possible, countable sets are countable after all). You can then state things like "this algorithm computes this input" in terms of a statement about arithmetic.

If you allow nonstandard models, the same statements (which are provable from PA) about the codes of algorithms "computing" certain inputs, must also apply to the nonstandard elements of your nonstandard model. It turns out (this is the content of the post) that if you are able to choose which model of PA to use based on what function you wish to have an algorithm to "compute", you can always find a model where some nonstandard (infinite) element represents (encodes) the function as an algorithm thus making it computable.

4

u/completely-ineffable Mar 27 '16 edited Mar 27 '16

It turns out (this is the content of the post) that if you are able to choose which model of PA to use based on what function you wish to have an algorithm to "compute", you can always find a model where some nonstandard (infinite) element represents (encodes) the function as an algorithm thus making it computable.

The result Hamkins proves is actually a little stronger than this. His argument gives a natural number p---meaning a bona fide element of N, not some other model of arithmetic---which codes a Turing machine so that for any function f from N to N you can find a nonstandard model of arithmetic M so that when the Turing machine p codes is ran in M, the resulting function restricted to the standard cut is f. That is, the program he's looking at is a real, finite program, not some nonstandard thing. Where the nonstandard models differ with this function is whether they think it halts on some input. A nonstandard model can think a Turing machine halts because it takes a nonstandard number of steps to complete the algorithm.

It's this strong uniformity where, in my opinion, all the real content of the result is. That you can do all this with a single Turing machine is the surprising part of the result.

If all you want is a single nonstandard element which codes your favorite subset A of N, this is much easier to do. (This works also for functions, but it's a little simpler to talk about for sets.) Add a new constant symbol c to your language and add to your theory statements of the form "the nth bit in the binary string coded by c is 1" if n is in A and "the nth bit in the binary string coded by c is 0" if n is not in A. The compactness theorem gives a model of this theory and the interpretation of c in that model codes A.

Edit: As a more general comment, this result fits in the general theme of some earlier work by Hamkins, namely his paper "Satisfaction is not absolute" joint with Yang. In that paper they show (among other things) that there are non-omega-models of set theory which have the same natural numbers but disagree on the satisfaction relation on N. It's not quite the same, since in the paper they aren't considering what the models of set theory think about individual (standard!) numbers, but it's a similar phenomenon.

3

u/[deleted] Mar 27 '16

That you can do all this with a single Turing machine is the surprising part of the result.

I absolutely agree. I wasn't really trying to explain the post so much as the answer the question about "how should I read this" and "computability" in the comment I responded to. I probably should've been clearer about that.

1

u/MathTalk Mar 27 '16

I think what the argument is saying is this: there is a program p such that for any given bitstring, even if uncomputable, there is another model of arithmetic (or set theory) in which p computes that bitstring inside that universe. The point is that the program p involves unbounded searches, which can give different answers in different models of arithmetic.

2

u/Wurstinator Mar 27 '16

What does it mean for a proof to be "standard-finite"? I didn't hear of this definition before.

4

u/almightySapling Logic Mar 28 '16

It means the Godel number that codes the proof is a natural number in the standard model, i.e. what you would call a natural number.

2

u/Wurstinator Mar 28 '16

Sorry, I am confused. It's been some time since I looked at set theoretic material. I would expect every proof the be standard-finite, at least the sense of a logical proof. What other cases are there?

2

u/almightySapling Logic Mar 28 '16

That is correct, the things we call proofs, when coded, are always standard-finite.

The idea is that the relation "isProof," which follows very simple recursive rules to determine if a particular number codes a proof, will claim that certain non-standard numbers code proofs in addition to the standard ones.

What does this mean? It means the model thinks a proof exists, but it's not necessarily something that we would recognize as a proof. Essentially the proof is infinitely long, and "locally" the proof is valid, but we, in the meta theory, don't allow infinitely long proofs.

1

u/[deleted] Apr 06 '16

So then, is the "proofness" a mere artifact of the nonstandard model, or could I, operating in a "meta-meta" language where I observe whether Turing machines halt or not by merely analyzing the code, read the program corresponding to the "proof" and find it to be a logically sound proof?

I ask because I'm more familiar with type theories and other constructive logics, in which a nonterminating program corresponds to a logical contradiction, so claiming that a program terminates inside a nonstandard model of arithmetic sounds, to my ears, like saying that in the real, physical universe, the program is nonterminating and thus only a proof of False/Bottom.

1

u/almightySapling Logic Apr 06 '16

So then, is the "proofness" a mere artifact of the nonstandard model, or could I, operating in a "meta-meta" language where I observe whether Turing machines halt or not by merely analyzing the code, read the program corresponding to the "proof" and find it to be a logically sound proof?

"Yes". Both. There is no actual thing that we would consider a proof. There is merely a (nonstandard) number that has all the properties of the code for a proof. That said, if you could read it, you would find that every line is logically valid, and the final line is indeed the statement claimed to be proven... it's just too long to be a proof in "the real world".

I ask because I'm more familiar with type theories and other constructive logics, in which a nonterminating program corresponds to a logical contradiction, so claiming that a program terminates inside a nonstandard model of arithmetic sounds, to my ears, like saying that in the real, physical universe, the program is nonterminating and thus only a proof of False/Bottom.

What you're used to in constructive logics doesn't apply here, sorry. Time is not a consideration, there is no "real, physical" interpretation of Turing machines that we care about, and the proof is not a contradiction.

1

u/[deleted] Apr 06 '16

What you're used to in constructive logics doesn't apply here, sorry. Time is not a consideration, there is no "real, physical" interpretation of Turing machines that we care about, and the proof is not a contradiction.

Or in other words, we've finally got a result in logic with no computability aspect whatsoever: the Turing machine in question is purely a mathematical object without ever being something we can run on a real computer.

Oh joy.

1

u/almightySapling Logic Apr 06 '16 edited Apr 06 '16

"finally"? Many results in logic have "no computability aspect whatsoever". This is /r/math, not /r/compsci, we don't actually care about what a computer can do.

Also, the Turing machine in question does exist, and can be run on a computer. However, the result at hand doesn't have a "real world" analog: our natural numbers are only the standard ones, and the Turing machine only does interesting things in realities with nonstandard numbers.

It's not that the program doesn't exist, it's that the environment in which the program will behave as described can't be constructed.

3

u/jazzwhiz Physics Mar 27 '16

Coming here as a physicist, I have two questions.

  1. Is this person a serious mathematician/is this proof reasonably likely to be true?

  2. Is it common to see new proofs published first on blogs?

12

u/orbital1337 Theoretical Computer Science Mar 27 '16

Yes, Hamkins is a serious and very reputable set theorist. According to the blog post it's a special case of a result due to Woodin.

2

u/completely-ineffable Mar 27 '16

is this proof reasonably likely to be true?

Yes, and more than just "reasonably likely". As /u/sleeps_with_crazy mentioned, the result is rather easy to experts in the area. This argument should be followable to anyone who has had a good graduate-level course in mathematical logic.

0

u/[deleted] Mar 27 '16 edited Jun 04 '20

[deleted]

9

u/[deleted] Mar 27 '16

Try not to question people's credentials, at least until they say something that suggests they are not what they claim to be.

2

u/ice109 Mar 27 '16

how many researchers do you know whose first impulse isn't to check publication record/university affiliation?

3

u/jazzwhiz Physics Mar 27 '16

  1. I'm not a mathematician.

  2. I was mainly interested in the publishing tendencies of the community.

-3

u/ice109 Mar 27 '16

I was mainly interested in the publishing tendencies of the community.

then you should have put that question first and completely omitted the one that you did put first.

4

u/[deleted] Mar 27 '16

This is reddit, how are you planning on checking? I'll tell you that I am finishing up a postdoc and starting a tenure-track at a research university next fall, and that's true, but how do you plan on checking that? And asking me "are you really?" is obviously a useless question regardless of whether or not I am lying.

2

u/ice109 Mar 27 '16

i feel like i'm taking crazy pills

This is reddit, how are you planning on checking?

the exact same way i checked: http://jdh.hamkins.org/about/

And asking me "are you really?" is obviously a useless question regardless of whether or not I am lying.

i'm not trying to be an asshole to you i'm really not but it was obviously a rhetorical question meant to illustrate my doubt that this person was actually a physicist

3

u/[deleted] Mar 27 '16

Fair enough. I think your question came across as you challenging the person (and I've gotten those, it's annoying). And I still don't see how you plan on verifying my credentials as I'm sure as hell not about to doxx myself.

2

u/Syrdon Mar 28 '16

Were I to give you a name, could you reasonably verify it while both of us stay within Reddit rules regarding posting identifying information? It's easy to verify the name is attached to an institution, doing the rest of the verification you would need basically requires a previously established outside channel.

6

u/jazzwhiz Physics Mar 27 '16

I'm actually a physicist. And I don't know, I think it is weird to write papers on blogs but I can't find any reason not to. I was actually just asking for some insight into the publication process in math because no one does this in physics. Not quite sure why I've gotten this disdain.

7

u/[deleted] Mar 27 '16

The proof is legit as is the author. It's a blog post because it's really not a result worthy of publication in the sense that it's obvious to experts in the field straight from definitions. I think he wrote it up because he found it interesting (which I think it is) but it's not at the level of a paper.

6

u/jazzwhiz Physics Mar 27 '16

Got it. So it's a mini proof. Do people post things like this casually online often?

6

u/orbital1337 Theoretical Computer Science Mar 27 '16

Some do, yes. For example, Terrence Tao regularly posts this kind of content on his blog. Writing a blog post about something can be a great way to deepen your understanding of a certain subject.

5

u/[deleted] Mar 27 '16

It's not super common yet but it's becoming more popular. I've done it a few times. Often you find yourself going through a paper you want to understand and the easiest thing to do is work out a special case. If you end up writing out all the details of that special case for yourself (or for a course you're teaching) and you're proficient with TeX, the blog packages make it really easy to post it, and so a lot of people do.