7

Since the set of computer programs is countable and the set of real numbers is uncountable, then it means most real numbers are incomputable. i.e. there does not exist an algorithm to compute their digits one by one (each digit in finite time) - therefore most real numbers are not an answer to a computable mathematical problem. therefore, in what sense do such numbers exist?

11
  • 4
    if all the computable results are dense in the whole topological space, it's pragmatically useful for all applications. Apr 28 at 17:10
  • 7
    Turn it around: why should computability be necessary for existence? That's always seemed to me a somewhat hubristic stance. Apr 28 at 17:32
  • 4
    In what sense does 2 exist? Is it different? Does having a short label for it make all the difference?
    – Conifold
    Apr 28 at 17:44
  • 3
    What does "most numbers are uncountable" mean? All real numbers have countably many digits. Apr 28 at 21:35
  • 3
    @KristianBerry I posted an edit (yet to be accepted) addressing this. I think the OP is talking about real numbers and means to say the set of real numbers is uncountable. Thus, the possible proposed paradox pertains to the fact that the vast majority of real numbers cannot be computed because the set of real numbers is uncountable while the set of computable numbers is countable. Apr 29 at 2:42
5

Computability of real numbers from Turing machine or Church's lambda calculus isn't necessary for a generic existence. According to computable number reference here:

Every computable number is definable, but not vice versa. There are many definable, noncomputable real numbers, including:

1.any number that encodes the solution of the halting problem (or any other undecidable problem) according to a chosen encoding scheme.

2.Chaitin's constant, ... which is a type of real number that is Turing equivalent to the halting problem.

The order relation on the computable numbers is not computable.

So since the order relation on computable numbers are not computable, does this mean their order relation does not exist? Of course not:

The set of computable real numbers (as well as every countable, densely ordered subset of computable reals without ends) is order-isomorphic to the set of rational numbers.

Another example is from the fact that the set of computable numbers is not closed under the basic operation of taking the supremum of a bounded computable sequence such as Specker sequence.

Finally there's uncomputable function such as Busy beaver function, and we can carefully construct some uncomputable number through some infinite convergent series using Busy beaver function, but apparently such constructed number is defined clearly and exists on the real number line per Cantor-Dedekind axiom.

Of course, some constructivism schools pursued your similar idea to completely eliminate noncomputable reals for all mathematics, though they're not the majority:

Though the computable reals exhaust those reals we can calculate or approximate, the assumption that all reals are computable leads to substantially different conclusions about the real numbers. The question naturally arises of whether it is possible to dispose of the full set of reals and use computable numbers for all of mathematics. This idea is appealing from a constructivist point of view, and has been pursued by what Bishop and Richman call the Russian school of constructive mathematics.

2
  • 1
    (1) and (2) are countable, aren't they? and if so there may still be an uncountable multitude of undefinable numbers. As for the rest, can you please try to explain in as simple terms as possible the meaning of your examples and claims? the terms and concepts involved are pretty dense technically. Thanks!
    – nir
    Apr 29 at 20:07
  • 1
    @nir thx for ur comment. My answer shows the possibility of certain uncomputable numbers exist in the sense of Cantor/ZFC+CH. More concrete examples of noncomputable real numbers see (math.stackexchange.com/questions/462790/…). Of course in the sense of a Turing machine those uncountable noncomputable numbers don't exist and that's why u have Russian constructive school mentioned above which is a better math for proponents of computational theory of mind. Since Cantor, Gödel and Cohen, we can choose different maths to dwell in... Apr 30 at 1:26
2

According to mathematical nominalism, "existence" is reserved for things that exist physically. In this view, neither computable numbers nor uncomputable numbers exist. Mathematics can be sensibly viewed as a what-if scenario: what-if objects satisfying <certain definitions> existed? What would follow from that counterfactual hypothetical?

Note that in the real world we have no Turing machines with infinite tapes, nor do we have infinite time for them to run.

Now consider this: it gets even worse. Consider the set of formulas that name real numbers. "12" "∑_{i=0}^∞ π^{-i}" "Chaitin's constant" and "sqrt(7)" are elements of this set. Each formula is a finite sequence of symbols, chosen from a finite alphabet. This means that the set of formulas naming real numbers is countable. And yet the set of real numbers is uncountable! This means that not only are most real numbers uncomputable, most real numbers can't even be written down with a formula of finite length!

A consequence of this is that for most real numbers x, "x exists" is not actually a formula anyone can write down, because no one can write a formula for x. If we can't even write down "x exists," how can "x exists" be said to be true or false?

1
  • 1
    +1 for the most important thing about real numbers: Most of them can’t be described, or even named, with any finite number of symbols, chosen from any countable set of symbols.
    – gnasher729
    May 2 at 19:57
1

What does it mean for something to exist mathematically? That will depend on whom you ask.

If mathematical realism (Radical platonism) would be the true ontology of reality, there is no necessity to restrict it to the turing-computable only. Some views on mathematical realism exclude the non turing-computable, while others don't.

For intuitionists mathematical existence is mostly located in the mind of the mathematician. For them neither computable nor uncomputable numbers truly exist in platonic sense.

1
  • 1
    I am not concerned so much with the concept of existence. When it comes to existence I am in the opinion that the only clear example for existence is my own consciousness (an example by inward pointing) - so I only use the term existence loosely in this question. this is why I ask in what sense they can be said to exist rather than claim they do not.
    – nir
    Apr 29 at 20:12
1

Let's say I have a ruler with one endpoint marked "0" and the other endpoint marked "1". Every point on this ruler corresponds bijectively to a real number between 0 and 1. Ruler with tick marks between 0 and 1.

I place my finger at a random point on the ruler and go, "THERE."
Same ruler as before with a finger added pointing at a red dot on the ruler.

Now, the computable numbers are countable, so they have zero measure on my ruler.
There is a precise technical sense in which my finger has almost surely landed on a point which does not correspond to a computable real number.
Why should the number that that point corresponds to be any less "real", just because there's no algorithmic procedure to write down its decimal digits?
Conversely, if the non-computable real numbers "don't exist", that's the same as saying the location in space that my finger is pointing to doesn't exist. I don't know of any current model of physics, or scientific evidence, that claims that some apparent, indicatable spatial locations are in fact illusory.
(Of course, a subjective idealist might be happy to handwave away the existence of anything physical at all, but to a subjective idealist the only things that exist are minds and concepts, and so a subjective idealist would accept the existence of uncomputable numbers because they exist as concepts.)

4
  • Am I wrong if I claim that there is necessarily an uncertainty involved with the position your finger is pointing at, and that in that uncertainty, narrow as it maybe lie an infinity of computable positions ? :)
    – nir
    Apr 29 at 20:00
  • @nir You're not, but it doesn't matter, because we can just define the red point on the ruler to be the probabilistic median of the finger positions (where my finger has 50% probability to be to the left of it, and 50% probability to be to the right) and then the same argument goes through. en.wikipedia.org/wiki/Median#Probability_distributions Apr 29 at 20:25
  • It's thought no resolution below the Planck scale is possible, so you can only go to 42 places after the decinal point, or so.
    – CriglCragl
    May 26 at 12:44
  • @CriglCragl I don't see the relevance. My argument didn't depend on computation or measurement of any kind. May 26 at 20:04

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .