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?

nir
  • 4,531
  • 15
  • 27
  • 4
    if all the computable results are dense in the whole topological space, it's pragmatically useful for all applications. – Double Knot Apr 28 '21 at 17:10
  • 8
    Turn it around: why should computability be necessary for existence? That's always seemed to me a somewhat hubristic stance. – Noah Schweber Apr 28 '21 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 '21 at 17:44
  • 1
    As has been commented, in what sense does any number exist. [Chaitin's constant](https://en.wikipedia.org/wiki/Chaitin's_constant) is a (set of) uncomputable real number(s) that can be described to some extent, even though they are not computable. – nwr Apr 28 '21 at 19:50
  • 1
    See related question: https://philosophy.stackexchange.com/questions/64526/existence-of-numbers-on-number-line – Ajax Apr 28 '21 at 20:13
  • 3
    What does "most numbers are uncountable" mean? All real numbers have countably many digits. – Kristian Berry Apr 28 '21 at 21:35
  • 2
    From what I understand the [Löwenheim–Skolem theorem](https://en.wikipedia.org/wiki/Löwenheim–Skolem_theorem) means that for any axiomatic system that we normally think of as dealing with uncountable sets like the real numbers, there is an alternate way of interpreting the symbols (a 'model') so that the axioms refer only to countable sets. I think this is related to the answer [here](https://mathoverflow.net/a/44129) which says that there is a countable model of ZFC set theory "in which every real number and indeed every set-theoretic object is definable", i.e. has a finite "name". – Hypnosifl Apr 28 '21 at 22:14
  • 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. – Just Some Old Man Apr 29 '21 at 02:42
  • 1
    @JustSomeOldMan quite right, need another user to approve this edit. – causative Apr 29 '21 at 05:44
  • The fact that real numbers are uncountable does not mean that they are incomputable. In the same sense, you cannot count points in a line, but you can find any number of points in a line (in fact, real numbers are points in a line). From there on, the rest of your logic is ill-formed. – RodolfoAP May 30 '21 at 04:58
  • @RodolfoAP, I find your comment very very strange, since the best and shortest answer to it would be to repeat my question word for word. – nir May 30 '21 at 06:57

4 Answers4

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.

Double Knot
  • 4,184
  • 2
  • 5
  • 15
  • 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 '21 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 (https://math.stackexchange.com/questions/462790/are-there-any-examples-of-non-computable-real-numbers). 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... – Double Knot Apr 30 '21 at 01: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?

causative
  • 10,452
  • 1
  • 13
  • 45
  • 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 02 '21 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.

1Zer0
  • 64
  • 3
  • 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 '21 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.)

Rivers McForge
  • 182
  • 6
  • 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 '21 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. https://en.wikipedia.org/wiki/Median#Probability_distributions – Rivers McForge Apr 29 '21 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 '21 at 12:44
  • @CriglCragl I don't see the relevance. My argument didn't depend on computation or measurement of any kind. – Rivers McForge May 26 '21 at 20:04