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

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