## Every function can be computable!

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

### Every function can be computable!

I recently read Joel David Hamkins' blog posts (one of which is the title)

http://jdh.hamkins.org/a-program-that-a ... -universe/
http://jdh.hamkins.org/every-function-c ... omputable/

However, my math-vocabulary isn't well developed enough to understand the nuances of the terms he uses. If my reading is correct, it seems to be relevant to one of the more popular discussions in the math forum, specifically Natural_ChemE's back-and-forth with someguy1 on the status of the continuum hypothesis.

The blog posts appears to formalize the position that what functions are computable depends on the model of arithmetic/set theory that we choose. The point not made in the blog post, but made by Natural_ChemE, is that the models of arithmetic/set theory that we are capable of choosing are constrained only by physics.

However, I'm not clean enough about the precise definition of "Model" used in Dr. Hamkins' post, and so I was hoping someone here might give me an explanation, or point me towards some learning materials.
bloaf
Forum Neophyte

Posts: 9
Joined: 13 Jan 2016

### Re: Every function can be computable!

bloaf » May 7th, 2017, 2:25 pm wrote:The blog posts appears to formalize the position that what functions are computable depends on the model of arithmetic/set theory that we choose. The point not made in the blog post, but made by Natural_ChemE, is that the models of arithmetic/set theory that we are capable of choosing are constrained only by physics.

LOL This thread is someguy1 bait for sure. I have less to say than you'd think but I'll do my best to shed some light.

Regarding NatChemE's position, he's not here to disagree so it would not be fair for me to rehash any of that thread. But Hamkins is talking about abstract set theory, and there's no known relation between set theory and physics at the present time. So it's not entirely sensible to bring up NatChemE's point of view in the context of the Hamkins articles. We're talking set theory and not physics. The space of all possible mathematical structures, whether they are physical or not.

In short, nothing in Hamkins's article or my exposition here have anything at all to do with the real world. As far as we know, of course.

bloaf » May 7th, 2017, 2:25 pm wrote:However, I'm not clean enough about the precise definition of "Model" used in Dr. Hamkins' post, and so I was hoping someone here might give me an explanation, or point me towards some learning materials.

First, Hamkins is a world-class set theorist on the forefront of research. So learning materials would include a fair amount of grad-level set theory at a minimum. If you ask specific questions I can fill you in on what little I know. I don't think there are very many elementary Wiki-type expositions of higher set theory. Maybe Google around for set theory, independence proofs, model theory, large cardinals, and so forth. Hamkins has a great article on his concept of the set-theoretic multiverse that's well worth reading.

But I can talk sensibly about models. Standard set theory is Zermelo-Fraenkel, ZF. We know that the axiom of choice (AC) is independent of ZF. That means we can take AC as an axiom, and ZF + AC, called ZFC, is consistent if ZF is.

Or we can take as an axiom the negation of AC, and that system is consistent as well (if ZF is).

[By the way from now on I'll just say "such and so is consistent," leaving out the qualification "if ZF is." The point is that we know that *if* ZF is consistent, so is ZFC. But we don't know (within ZF) if ZF is consistent. So all statements about consistency are relative to other ones. If this is consistent then that is. In general I'll ignore this but it's always implied].

So ZFC and ZF-C (ZF minus C) are both consistent. They are in effect two different set theoretic worlds in which different statements of mathematics are true.

** Math is not physics

Now first, please please please note that we are not talking about physics. There is not a shred of evidence or even a plausibility argument that ZF is instantiated in any way in the real world. For one thing. ZF assumes there are infinite sets. There are no infinite collections of anything in the real world.

It's not even plausible that a statement like AC even has a sensible truth value in the real world. To find out, we'd have to take an uncountably infinite collection of sets (whatever they are) and see if there's some other set containing exactly one element from each of these other sets.

Now what kind of sense can that make in physics? It's not any part of contemporary science. For the moment, set theory is purely an abstract mathematical idea with no referent in the real world.

Of course we can use basic ideas like unions and intersections. The set of boys and the set of red haired people has as their intersection the set of red haired boys. That's part of the world, to be sure, but it's far too simple to capture the actual strangeness of set theory.

If I have an apple on the desk, that's physical. Can you honestly tell me that there's some physical referent for the set containing the apple? Let alone the set containing the empty set. Such things are purely mathematical abstractions.

So I hope that we can simply, flat out forget about any physical considerations. For some reason people have a hard time doing that in discussions of pure math, and much confusion ensues.

From now on we are simply not talking about the world. Only what goes on in modern set theory.

** Back to the article

Now there are a lot of models of set theory. ZFC and ZF-C are two familiar ones. Even in ZF, which assumes infinite sets, we can actually deny that there are infinite sets and we still get a consistent set theory. It's basically the number theory of the Peano axioms. So those are more models.

Set theorists have gotten very good at cooking up exotic models of set theory in order to examine various exotic modern axioms.

So Hamkins's point is that given any function $f : \mathbb N \to \mathbb N$ there is SOME crazy model of set theory in which $f$ is computable. That in itself is amazing. But remember, these are very weird models.

But now Hamkins has a very subtle cheat. Note his wording. I'll copy this in verbatim.

Hamkins wrote:There is a Turing machine program $p$ with the property that for any function $f : \mathbb N \to \mathbb N$ on the natural numbers, including non-computable functions, there is a model of arithmetic or set theory inside of which the function computed by $p$ agrees exactly with $f$ on all standard finite input.

(Emphasis mine)

What's that bolded bit mean? Consider one of NatChemE's examples, the hyperreal numbers. The hyperreals are a nonstandard model of the first-order theory of the real numbers in which we have every familiar real number, along with lots and lots of infinite and infinitesimal numbers as well. In particular, the hyperreals contain hyperintegers, or infinite integers, numbers that do not exist in the standard integers.

What Hamkins is saying is that our magic universe that makes some function computable, is only making that function computable on the standard, finite numbers. It's not necessarily computable on the nonstandard, non-finite numbers that exist in that model.

So in a sense, as surprising as Hamkins's result is, it's saying a little bit less than it seems. It's not saying the given function is computable in the new universe. Only the function's restriction to the standard, finite integers matches the original function. We don't know anything about its extension to the nonstandard or on-finite numbers in the new model. It seems to be a bit weaker than the title of the article but this is pretty technical and I can't say for certain.

That's my first take from Hamkins's article. Fire away with questions, I'll do my best.

But if there is one single tl;dr takeaway, it's that this has nothing to do with physics.

Also by the way I should admit that I don't really grok what it means to have a Turing machine operating in an alternate model of set theory. I think that's the core mystery here. I don't know what that really means.
someguy1
Member

Posts: 494
Joined: 08 Nov 2013

### Re: Every function can be computable!

ps -- I got a little more insight from these two links mentioned in the comments to the Hamkins article.

https://johncarlosbaez.wordpress.com/20 ... omputable/

someguy1
Member

Posts: 494
Joined: 08 Nov 2013

### Re: Every function can be computable!

Thanks a lot, someguy1, I'm always impressed by your in-depth responses. The two blog posts you linked are indeed helpful. I've not taken any grad-level abstract math courses, my experience is limited to an honors undergrad course which went through Gallian's book "Contemporary Abstract Algebra."

To push back just a little bit, my defense/explanation of my previous view is essentially this:

To say that some reasoning is abstract is somewhat dangerous. Specifically, it can make people think that the work mathematicians do in their heads is somehow privileged.

It seems to me that people imagine the following scenario.
$a\overset{\text{abstract reasoning}}{\longrightarrow}b$
Where this means that you have some abstract reasoning that leads from abstract premise a, to abstract conclusion b. This could be something as simple as a = 1 + 1 and b = 2, or it could be more complicated, like a = geometric postulates and b = the pythagorean theorem. People like those mentioned in the link above believe that we have some special faculty that lets us go straight from a to b via a magical immaterial process (read: it happens in your soul!) and therefore has no constraints whatsoever.
Where I think the more accurate process looks like this:
$a\overset{I^{-1}}{\longrightarrow}a'\overset{\text{P}}{\longrightarrow}b'\overset{\text{I}}{\longrightarrow}b$

Where I represents some "interpretation" function that converts a physical state (a') into an abstract state (a) and P represents some physical process. I is the kind of process we use when we interpret a circuit with a certain resistance as being a 1, while a different resistance might be interpreted as a zero, and P is essentially just "letting physics do its thing for a while." We perform this process pretty explicitly when we punch numbers into a calculator and read the result, but I'd argue that we do the same thing even when we are just using the Feynman problem solving algorithm.

So! I would argue that all abstract reasoning consists of this I-1 P I process, and each step in that process is fundamentally physical. In other words, reasoning abstractly from a to b is possible if and only if there exists this physical I-1 P I process from a to b.

Therefore, if it is possible for a mathematician to reason as though ZFC or ZF-C is true, AND it is possible for a mathematician to reason as though ZF!C (ZF + the negation of AC) is true, we naturally haven't said anything about physics other than there exist I-1 P I processes that are consistent with ZFC, ZF-C, and ZF!C.

Returning to Hamkins' blog posts, his whole point is about a turing machine program p that can produce the output of a function f : ℕ → ℕ if only it is operated within the right model, M. My thoughts are that the fact that we can "operate" our own thought processes under different models suggests that we should be able to operate actual physical implementations of turing machine program p under different models as well. The question in my mind is: how many such models are available to us? And it still seems to me that the answer depends on what kind of physical I-1 P I processes exist.
bloaf
Forum Neophyte

Posts: 9
Joined: 13 Jan 2016

### Re: Every function can be computable!

bloaf » May 8th, 2017, 10:50 am wrote:Thanks a lot, someguy1, I'm always impressed by your in-depth responses. The two blog posts you linked are indeed helpful. I've not taken any grad-level abstract math courses, my experience is limited to an honors undergrad course which went through Gallian's book "Contemporary Abstract Algebra."

I've picked up a lot of what I know online, it's just not in one place. SEP is a good resource that goes beyond Wikipedia.And now that I think about it, I learned more about all this from Nagel and Newman's book Gödel's Proof, than I ever did in any math classes I took. I think I've just picked up everything I know over the years, especially since the Internet.

* Before responding to your post I wanted to add a couple of things about the Hamkins paper.

After reading through that Reddit thread I got a bit more understanding of what's going on. It's related to Gödel numbering. In Gödel's original proof of his incompleteness theorem, he coded up every possible statement you could make in number theory as a number. The number 47 might represent a proof of Fermat's last theorem. [Of course it would actually be a much larger number]. So particular numbers represent sentences of number theory.

Then in different models of number theory, different sets of numbers represent "true" statements. Or something like that. In any event it's about the relationship between nonstandard models of number theory, and Gödel numbering in that universe.

* My grasp on Hamkins's paper is extremely tenuous, I hope that's clear. I know a little about the general subject but can't really follow the reasoning in the paper.

* To address your comments I'd just like to answer in general rather than engaging with each of your points; because in fact you've brought up some very interesting ideas I've never given any thought to. I've never even entertained the possibility that set theory might have any instantiation in the real world. I want to spend more time reading your post before replying specifically.

My general orientation is this.

For simplicity let's define two positions in mathematical philosophy.

Platonism: Math refers to the real world.

Formalism: Math does not refer to the real world but is only a formal game played with symbols on paper.

Of course these are extreme simplifications and there is an extensive philosophic literature on the subject. But these will do for the point I'm about to make. Which is:

When I do math I put on my formalist hat. I take math on its own terms. If I were to put time into a paper like Hamkins one I'd just try to understand the math. I'd need to read up on Godel numbering, work through the Baez article, then start going through the paper line by line and looking things up, etc.

Now at the end of the day when I'm done doing math from a formalist perspective, I might put my feet up on the desk, relax, and speculate on what it all mean.

But then I am doing philosophy and not math.

To sum up: When doing math, you should be a formalist whether or not you really are one.

That is my longtime belief and perhaps I should make it more clear. When I argue for a formalist view of math it's not because I'm a necessarily a formalist; but because I think taking math on its own terms is the only way to have any hope of understanding it.

I'll leave it at that and go read your post some more. I will say though that when I contemplate what I know about higher set theory (to be clear I know a little ABOUT higher set theory, which is not the same as knowing higher set theory!) I truly have a hard time imagining that it refers to the real world at all.

Look up large cardinals and you tell me. These are cardinal numbers so large they can't even be proven to exist in ZFC. They strain one's credibility even as mathematical objects, let alone physical ones. But modern set theorists take them very seriously.

ps -- If you want to get a good flyover of modern set theory, clicking on all the links in that article is a great way to go about it.
someguy1
Member

Posts: 494
Joined: 08 Nov 2013

### Re: Every function can be computable!

Your post has so much going on that I'll just respond a little at a time as my thoughts percolate. You've given me a lot to think about.

bloaf » May 8th, 2017, 10:50 am wrote:

To say that some reasoning is abstract is somewhat dangerous.

I find that a strange statement. Civilization is built on abstractions. Law, money, property, government, religion. It's all abstractions. We crawled out of caves and built all you see around you by the power of abstraction.

People say mathematics is abstract but they don't even see the abstraction around them. Someone lives in a house on their "property." Show me property in physics. It's a social convention. An abstraction. A Martian physicist can tell red light from green. But she cannot tell you which means stop and which means go. That's not a physical fact. It's a social fact. It's an abstraction.

Our entire world is almost all abstraction. The way we live, our societies, everything we do as a member of civilization. It's not to be found in physics. It's all social abstraction. Nothing is real. Electromagnetism keeps your atoms together and gravity keeps you from floating off into space. Beyond that your life is a collection of social constructs true by virtue of nothing more than collective agreement.

Yet people complain about the abstraction of math! They don't see that they live in a world of abstraction. Math is the least of it!

Can you say why you think abstraction is dangerous?
someguy1
Member

Posts: 494
Joined: 08 Nov 2013
 Braininvat liked this post

### Re: Every function can be computable!

No more? I'm disappointed. I loved your post. Virtually every single sentence you wrote inspired me to write an entire essay in opposition. I could have ranted for weeks. If you ever want to come back and continue this please do :-)

I was particularly intrigued by your accusation of "privilege" at those who think abstractly. Is this some kind of millennial snowflake thing? I am really curious as to what you meant by "To say that some reasoning is abstract is somewhat dangerous. Specifically, it can make people think that the work mathematicians do in their heads is somehow privileged."

Are you saying that the pointy-headed perfessors should be shipped off to a forced labor camp until they see the error of their ways? Chairman Mao's cultural revolution and all that?

What did you mean by that remark?
someguy1
Member

Posts: 494
Joined: 08 Nov 2013

### Re: Every function can be computable!

LoL....could bloaf mean epistemically privileged? Or the meaning of propositions is always questionable in the sense of Kripke's skeptical stance, so only the speaker or writer who generates an abstract proposition has the privileged perspective of knowing exactly and certainly the meaning. I'm guessing it's privilege in the epistemic sense, not the social sense.

Braininvat

Posts: 5489
Joined: 21 Jan 2014
Location: Black Hills

### Re: Every function can be computable!

Braininvat » May 15th, 2017, 3:02 pm wrote:LoL....could bloaf mean epistemically privileged? Or the meaning of propositions is always questionable in the sense of Kripke's skeptical stance, so only the speaker or writer who generates an abstract proposition has the privileged perspective of knowing exactly and certainly the meaning. I'm guessing it's privilege in the epistemic sense, not the social sense.

Ah! Too much politics and not enough philosophy in my brain. Thanks for the clarification.

ps -- I found something online about Kripke's epistemic paradox and frankly my eyes glazed over pretty fast. Evidently if I write 37 + 78 no one else can be sure if I mean + as the usual addition on the whole numbers, or if I mean some other + that means something else once I get past a certain point. Kripke's point being, I suppose, that in order to "know" what I mean by +, you have to interrogate me on a number of cases. But you can never be sure if once the numbers get large enough, I mean some OTHER meaning of +.

I suppose this is valid, in a sort of nihilistic way. I know there was this whole philophy of language phase in which all the analytic philosophers got themselves all worked about the idea that the study of language was really really important. Kripke's name generally comes up. Honestly that's almost everything I know about it.

There is certainly no mathematical problem. We can unambiguously define the + operator from the Peano axioms. I think it answers Kripke's objection. The symbol + has the default meaning of the mathematical +. Kripke should pick a different example.

But what does Kripke mean? It's true I might be a brain in a vat. It's true that when you said this you meant that. What of it? We must go through our daily lives as if things made sense, even if we suspect they don't.

Have I got any of this right?

Personally I think the OP meant the political meaning! The kids on campus remind me very much of the Chinese cultural revolution of the 1970's. The physical circling and public yelling and shaming of anyone suspected of not adhering to the cultural orthodoxy. It's frightening. Intellectuals did get sent to camps. I used think I was a liberal. On most things I still am. But what the hell is this? I'm for free speech so I'm a racist Nazi? That's what some of the kids think.

So I'll say that I'd like to know more about Kripke, but I'll reserve judgment on what the OP meant when the OP shows up to say. After all, it's Kripke again. We can't know what the OP meant! Only the OP knows what the OP meant.

Is that it?

https://en.wikipedia.org/wiki/Cultural_Revolution
someguy1
Member

Posts: 494
Joined: 08 Nov 2013

### Re: Every function can be computable!

Joel Hamkins is using something called "Proof by effective procedure" in his blog. He uses it willy-nilly, presuming his reading audience is already familiar with it. In my opinion it is a voodoo procedure, much similar in the voodoo used in "analytic continuation" applied to holomorphic functions defined by infinite series. ( For fairness of coverage, analytic continuation is accepted as valid mathematics by academia. )

Hamkins also makes rough quick references to compactness of models -- like a person eating toast for brunch. Compactness in models is very subtle mathematics. He just blubbers over it like it's easy for him to just assume and move on.

It is unlikely that his blog could be read by anyone other than a grad student.

To clear up an earlier confusion, when a person uses a proof by effective procedure, they are making no references to how long a machine would have to run before accidentally stumbling upon the right proof p. For all we care this could take 10116 years. Theorems don't care. We have infinite time and infinite scratch space to "write them all down" in a set.

The specific "offense" is committed here:
Clearly, PA proves that program e accepts only a finite set, since either no such proof is ever found, in which case e accepts nothing (and the empty set is finite), or else such a proof is found, in which case e accepts only that particular finite set. So PA proves that e accepts only finitely many inputs

Consider the case in which "no such proof is ever found". When does that happen? Well it happens after an infinite number of steps has exhausted all the proofs, coded as integers. In terms of mathematics, that statement is agreeable in principle , in the same way that induction on an infinite set is agreeable in principle.
Last edited by hyksos on August 8th, 2017, 12:27 pm, edited 2 times in total.

hyksos
Member

Posts: 981
Joined: 28 Nov 2014

### Re: Every function can be computable!

...........

hyksos
Member

Posts: 981
Joined: 28 Nov 2014