computational philosophy of mathematics

[gusl]

I only believe in mathematical objects with finite information (i.e. with a finite expression). Things can expressed in any way you wish, intensionally, extensionally, whatever. So, while the natural numbers exist, not all subsets of it do.

While the set of real numbers exists (R can be expressed as the power set of N), not all of the traditional real numbers exist (only the computable ones do). So, in my definition, the cardinality of R is aleph_0 (i.e. the same as N). In fact, no set can have greater cardinality, for that would imply it had non-existing elements (since only computable things exist).

Can we design a set theory this way? How much of traditional set theory can be translated? Does we lose any good mathematics this way?

Whereas people seem to view uncomputability as a fundamental property of a problem, I tend to view it as another form of self-reference paradoxes. All "well-defined" problems are computable. Again, this is not a theorem or mathematical insight, but a re-definition, just like my "R only has countably many existing numbers" is a definition. But the point isn't just to change names and keep everything the same... it's to change the intuition that goes with the names.

Comments

[gustavolacerda.livejournal.com]

Very good question!

In a way, all mathematics is fictional, but some mathematics feels more fictional than normal. Transfinite stuff, for instance... It feels bullshitty to me whenever someone talks about higher infinities and other things which we necessarily can't grasp. The point is that we can only talk about them as abstractions, without ever actually seeing them.

Maybe I should talk about intuition, or maybe I should talk about accessibility or understandability (which I am formalizing as computability).

[pbrane.livejournal.com]

"Intuitive" is a very dangerous concept to introduce to formal systems: our brains are weak, and relying on being able to grasp things intuitively would have stopped us from ever developing quantum mechanics, or general relativity, or more than 3 spatial dimensions, for examples in physics.

In math, it's like those people who don't accept proof by contradiction, you can do it, but you're going to get a hell of a lot less math done, and some of the math you miss is really beautiful stuff.

But also - the contiuum is a pretty intuitive concept to me at least, even if the numbers you get aren't computable, you can compute them as arbitrarily accurately as you want so there's an intuitive idea of what they are if 'convergent limits' are intuitive to you (both the description of a real number as a Dedekind cut or a Cauchy sequence both allow for a deterministic process to tell you whether your rational guess at the number was within any fixed epsilon...).

[gustavolacerda.livejournal.com]

"Intuitive" is a very dangerous concept to introduce to formal systems: our brains are weak, and relying on being able to grasp things intuitively would have stopped us from ever developing quantum mechanics, or general relativity, or more than 3 spatial dimensions, for examples in physics.

Agreed. But uncomputable numbers are more than just "unintuitive". They are fundamentally un-(reachable? accessible?). You've never seen one, and you never will. I take this to mean they don't really exist, except as abstractions.

In math, it's like those people who don't accept proof by contradiction, you can do it, but you're going to get a hell of a lot less math done, and some of the math you miss is really beautiful stuff.

I've also expressed this instrumentalist feeling in my post: what's useful is good!


But also - the contiuum is a pretty intuitive concept to me at least, even if the numbers you get aren't computable, you can compute them as arbitrarily accurately as you want so there's an intuitive idea of what they are if 'convergent limits' are intuitive to you (both the description of a real number as a Dedekind cut or a Cauchy sequence both allow for a deterministic process to tell you whether your rational guess at the number was within any fixed epsilon...).

The point is that any real number you give me, whether through Cauchy sequences or Dedekind cuts, will be given to me in a finite form. Thus, we have a computable expression of the real number. But there are only countably such real numbers. The ones I say don't exist are the ones you can't possibly express finitely.

Have you heard of Fredkin? He believes everything in the physical universe is discrete.

[pbrane.livejournal.com]

You've never seen one, and you never will. I take this to mean they don't really exist, except as abstractions.


Just because you or I will never see one, why should this mean they don't "exist"? To me, all numbers are abstractions - they're formal constructs which interact with each other according to rules we made up. "x", the variable, takes on the value of some noncomputable number, say. I happen to know some finite amount of information about said number: it's between 0 and 0.00001, yadda yadda. Is it not existent just because I can't write it down in closed form?

The ones I say don't exist are the ones you can't possibly express finitely.

Yeah, I guess when you stick to dealing with only concrete numbers, you're going to inevitably end up with these. It just seems backwards to me - for me, I really do stick with the (finite, very expressable, but abstract) statements like, "to me, 'real numbers' are elements of the abstract set which is the unique-up-to-isomorphism complete ordered field". *That* finite expression encompasses the whole set, and I accept by logical extension that all of its members have equal 'existence' to the set as a whole. Not doing so seems contradictory to me - how can you accept "the set of real numbers" but not accept almost all of them. It seems you would have to not accept that the concept of completeness or continuity, or really limits at all, if you want to stick to only computable things.

Have you heard of Fredkin? He believes everything in the physical universe is discrete.

As a physicist, I tend to think that whenever a philosopher or mathematician posits descriptions about "the entire physical universe", they're talking out their ass. :) The only rational view of the universe I accept is that of the agnostic: we don't know what the hell it is.

[gustavolacerda.livejournal.com]

Fredkin is a physicist too. He studied with Feynman.

Secondly, while we "don't know what the hell it is", we need metaphysical theories from which to create physical theories. Fredkin predicts that digital physics will be falsifiable one day: from my understanding, it suggests that all symmetries will eventually be broken.

[pbrane.livejournal.com]

Hmmm... he sure doesn't read like a physicist - he reads like a computer scientist, and doesn't seem to have that great of a way of describing his ideas in detail, from what I can see on his site.

we need metaphysical theories from which to create physical theories.

I'm not sure what you mean by this: the scientific method is based on inductive, not deductive, reasoning: we describe what we observe, and we model it in a variety of ways. The models which have the fewest moving parts are the ones we prefer. That's physics.

We don't "postulate" that physics is a discrete system, we, for example, observe that GR (in a weakly coupled regime where it's valid), mixed with QFT (in a locally flat piece of space where *it* is valid), predicts that black holes have a temperature, and contain information: a finite number of possible microstates which is the exponential of the area of the event horizon (in units of the planck length).

This gedanken-observation hints at the fact that the information contained in any finite volume of space is indeed finite, and yeilds entropy proportional to the area bounding said volume (in units of the planck length). So yes, there are reasons to consider theories that have finite amounts of information density, but you shouldn't assume it from the start. String theory seems to embody this concept *even though* it's completely continuous, all the way down to, and below, the planck scale. Maybe the naive descriptions of string theory are describing information redundantly, but that doesn't mean it's any less real of a description (assuming it's right, of course), just because it uses a completely contiuous basis.

I guess I'm really not sure we need a new "metaphysical theory" from which to create physical ones - direct observation points to continuity down to 10^-19cm, and indirect (looking for violations of relativity, the equivalence principle) observations point further than that. Without a *physical*, not metaphysical, reason to assume discreteness, we shouldn't do it. It may turn out to be *true*, but that doesn't make the arguments for it compelling to me before the fact (especially because it's easy to go too far: it could be that space and time are discrete, but that quantum mechanics is still based on a whole bunch of continuous internal symmetries [i.e. superposition is still true, even if you take the superposition of two states with any complex [not just complex rational or constructable or whatever] coefficients in front of them).

[gustavolacerda.livejournal.com]

I'm not sure what you mean by this: the scientific method is based on inductive, not deductive, reasoning: we describe what we observe, and we model it in a variety of ways. The models which have the fewest moving parts are the ones we prefer. That's physics.

Unless you're doing it for expediency reasons, the fact that you use Occam's razor is due to your metaphysical theory. (i.e. we believe simple explanations tend to be true more often than complicated ones)

"Those who explicitly have a philosophy use an implicit one without realizing it."

Fredkin starts from an interesting metaphysical assumption. I know way too little to judge it further. But who knows, maybe it will be easier to understand things / make new discoveries if physicists start thinking this way.

[pbrane.livejournal.com]

The only part which uses Occam's razor is the "preferring fewer moving parts" part of it - the rest is just, "we describe what we observe", and so far, we've reached most of the conclusions of modern science with the premise of continuity. It's not *logically necessary* for there to be arbitrarily accurate continuity, but so far, that's all we have evidence for. But in some sense, Occam's razor in science is just for expediency: we don't claim that any model "is" the real world - it's just a model of it, and the more accurate the model, for the least amount of work, the better.

But who knows, maybe it will be easier to understand things / make new discoveries if physicists start thinking this way.

Possible, but so far, in the history of science, we typically have discretized continous things for computational purposes (recently) or to avoid singular problems that were artifacts of the construction (which we could remove and then take the discretization length to zero at the end of the day).

It still doesn't seem like *meta*physical assumption, but an actual physical one, and an unjustified one at that. Show me some evidence for discreteness, or else show me some nice theoretical problems solved by the proposal, or at least show me how it simplifies current descriptions, or else I'm not sure why it's being done: just because we're scared of the infinite? Seems pretty arbitrarily limiting.

[gustavolacerda.livejournal.com]

I really do stick with the (finite, very expressable, but abstract) statements like, "to me, 'real numbers' are elements of the abstract set which is the unique-up-to-isomorphism complete ordered field". *That* finite expression encompasses the whole set, and I accept by logical extension that all of its members have equal 'existence' to the set as a whole. Not doing so seems contradictory to me - how can you accept "the set of real numbers" but not accept almost all of them. It seems you would have to not accept that the concept of completeness or continuity, or really limits at all, if you want to stick to only computable things.

Interesting point (I missed it at first).

I don't want to give up completeness. Yet, I hold that not all limit points need to exist. The only limits that we need to exist are the limit points of computable sequences.

Ok. You're requiring R to be a complete ordered field. So let's take the rationals (Q) and close them under limits.
So, given any sequence of rationals, this set should contain their limit.
Since all possible inputs are computable, we only need to add countably many limits (one for each possible sequence).
So we still only have countably many numbers in R (which we call the "complete ordered field").


I think of mathematics in a lazy way (in analogy with "lazy evaluation"), so things only need to appear as you ask for them. In this view, it seems clear that only computable things exist. No set needs to contain uncomputable numbers, because countably many things are enough to serve all possible requests.

My thoughts on this are still sloppy. Please do criticize.

[pbrane.livejournal.com]

Ok. You're requiring R to be a complete ordered field. So let's take the rationals (Q) and close them under limits.
So, given any sequence of rationals, this set should contain their limit.


If it does contain all of the limits of all of the Cauchy sequences, then you're going to get all of the traditional R - all uncountably many numbers.

Since all possible inputs are computable, we only need to add countably many limits (one for each possible sequence).

But there are uncountably many convergent (cauchy) sequences of rationals, so adding each limit will indeed make your set uncountable (and hence, most of these sequences must not be computable).

If you want to keep completeness, then you're going to be stuck with uncomputable numbers: there is only one complete ordered field, and it contains uncountably many uncomputable numbers.

[gustavolacerda.livejournal.com]

I meant: we only care about computable Cauchy sequences. There are countably many of those. And so this gives us countably many new limits to add to our set.

Have you ever seen a non-computable Cauchy sequence?

[pbrane.livejournal.com]

Have you ever seen a non-computable Cauchy sequence?

Dude - I've only seen *finitely many* Cauchy sequences, let alone countably many. Does this mean I only believe in a finite number of them?

I believe in the intuitive concept of continuity, and I can't have that without all the noncomputable numbers, hence I believe in them too.

[pbrane.livejournal.com]

To reiterate: if you only care about the computable cauchy sequences, then you don't care about your field being complete: it won't be complete without the noncomputable ones added in as well.

[gustavolacerda.livejournal.com]

I'm revising the meaning of "number" all the way to the bottom. Only computable things are considered to exist at all.

So by saying the set is "complete" (or "closed under limit"), it is meant that "the limit of all Cauchy sequences is in the set". However, since noncomputable Cauchy sequences don't exist, then we don't have to worry about those limits.

To make things clearer, let me reconstruct everything from the bottom, with different names... Let N_ be the set of computable natural numbers.
We then define Z_ (the set of computable integers) and Q_ (the set of computable rationals). All of these coincide with their mainstream counterparts.

Then let CauchyQ_ be the set of computable Cauchy sequences with elements in Q (or Q_). This is not equivalent to CauchyQ.

Just like R is defined as the closure of Q under limits(CauchyQ), we shall define R_ to be the closure of Q_ under limits(CauchyQ_) (i.e. the limits of computable Cauchy sequences over Q).

R_ is by definition a complete extension of Q_ (again, it's not complete over noncomputable Cauchy sequences, in the same way that R isn't complete over the complex numbers).

One flaw with my proof in the previous comment, though, is that just one step of adding limits to the set isn't enough to prove closure. But regardless, even with countably many steps, each adding countably many points, you're still in the realm of the countable.

Countably many steps are enough to prove closure: nobody can look farther than that.

[pbrane.livejournal.com]

Then let CauchyQ_ be the set of computable Cauchy sequences with elements in Q (or Q_). This is not equivalent to CauchyQ.

Ok, so in fact, CauchyQ_ is a countable subset of CauchyQ (which is itself an uncountable set of sequences).

Defining R_ as the closure of Q under limits(CauchyQ_) is fine, but it won't be *complete*, in the technical sense: there exist convergent sequences in R_ whose limits are not in R_. R does not have this property: all convergent sequences in R reach a limit which is in R.

You can use your R_, but it's not complete. R doensn't need to be complete over the complexes: completenes isn't like algebraic closure - it's defined completely within the set itself: there are no sequences in R which converge to a complex number not in R.

[r6.livejournal.com]

you can compute them as arbitrarily accurately as you want

This is untrue, and basically at the heart of gustavolacerda argument. For a concreate example, take the ‘halting probability’ Ω (http://alixcomsi.com/Is_the_Halting_probability.htm).

Robert Solovay ... has constructed a self-delimiting universal Turing machine such that ZFC, if arithmetically sound, cannot determine any single bit of its halting probability ... Rephrased, the most powerful formal axiomatic system is powerless when dealing with the questions of the form “is the m’th bit of Omega 0?” or “is the m’th bit of Omega 1?”.

[pbrane.livejournal.com]

I'm not sure I follow: does this turing machine have a particular probability of halting on any given input?

Universal Turing Machine

[r6.livejournal.com]

This is a universal Turing machine so my understanding is it the probability that a given input (a number representing a Turing machine) will halt.

Re: Universal Turing Machine

[gustavolacerda.livejournal.com]

hmm.. what's the distribution of inputs, though?

Re: Universal Turing Machine

[pbrane.livejournal.com]

So it's actually a function, not a number right? : given an input number N, there is a probability Omega(N) that it halts. And you're saying that this particular turing machine has the property that Omega(N) is a real, yet uncomputable number, for some (all?) N?

[easwaran.livejournal.com]

I believe this number Omega is the limit as n approaches infinity of H_n/n, where H_n is the number of inputs less than n on which the Turing machine halts. I think there's a proof that this limit actually exists and any recursively axiomatized extension of ZFC can only compute some finite number of bits of this number. I had heard of most of this stuff just done by Chaitin - I didn't realize that other people (especially Solovay!) were interested.

[gustavolacerda.livejournal.com]

ok. *This* I consider troubling.

I don't like most undecidability results and try to call bullshit on them, by arguing that the problem is ill-defined due to self-reference.

One difficulty I had in my class on Kolmogorov Complexity was that we were using these uncomputable numbers as if they existed. But as we know, math doesn't care about the reality of what it's talking about...

[gustavolacerda.livejournal.com]

This halting probability business... again: self-reference, so I'm not going to be surprised if we get weird things.

I think what pbrane had in mind was your average uncomputable real number (which I tend to picture as a random point on the real number line), but the problem with those is that we have no idea what they are actually like, since we've never seen one!

Uncomputable Real Number

[r6.livejournal.com]

Well for any real number that has a single algorithm that can approximate it to any desired accuracy only contains a finite amount of information.

My point for pbrane was that uncomputable numbers cannot be approximated to any desired accuracy. I felt I should give an explicit example.

Re: Uncomputable Real Number

[gustavolacerda.livejournal.com]

Well for any real number that has a single algorithm that can approximate it to any desired accuracy only contains a finite amount of information.

I was thinking about this, and for numbers like pi (which we can approximate with a finite algorithm), it would still take an infinite-length input in order to get the algorithm to output pi to infinite precision.

So when we think of pi, we must think of it in an interactive way: not as a fixed number, but as a an algorithm that returns an approximation to (the perimeter of a circle of radius 1 / 2) to whatever precision you desire. But you yourself are limited in how much precision you can ask.

My point is that, when defining such numbers, we need to discount the information in the input. I'm not sure if the exact value of pi is computable... and I'm not sure this makes sense.