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

[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.