# If most numbers are uncomputable, in what sense do they exist?

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?

• if all the computable results are dense in the whole topological space, it's pragmatically useful for all applications. Commented Apr 28, 2021 at 17:10
• Turn it around: why should computability be necessary for existence? That's always seemed to me a somewhat hubristic stance. Commented Apr 28, 2021 at 17:32
• In what sense does 2 exist? Is it different? Does having a short label for it make all the difference? Commented Apr 28, 2021 at 17:44
• What does "most numbers are uncountable" mean? All real numbers have countably many digits. Commented Apr 28, 2021 at 21:35
• From what I understand the 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 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". Commented Apr 28, 2021 at 22:14

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.

• (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
Commented Apr 29, 2021 at 20:07
• @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... Commented Apr 30, 2021 at 1:26

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 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. Commented May 2, 2021 at 19:57
• I don’t know that much about this but I think it’s interesting to consider that if someone is saying “can’t be described” but they mean “can’t be described finitely” it makes the mysteriousness seem less. They just have infinite descriptions. It just sounds like pretty expectable. Commented Aug 7 at 19:33

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.

• 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
Commented Apr 29, 2021 at 20:12

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.

I place my finger at a random point on the ruler and go, "THERE."

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

• 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
Commented Apr 29, 2021 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 Commented Apr 29, 2021 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. Commented May 26, 2021 at 12:44
• @CriglCragl I don't see the relevance. My argument didn't depend on computation or measurement of any kind. Commented May 26, 2021 at 20:04
• I think the issue is that below a certain size threshold, in quantum physics, it does not make any more sense to talk about points or distances. So the example only works with a simpler mathematical model of physics, like Newtonian space. Actual space is just weird when things get very small. Commented Aug 9 at 12:39

An uncomputable number such as Chaitins Omega does exist in mathematical sense - it is a well defined string of digits. Just there is no finite algorithm for finding all these digits. This shows in a very stark way the 'unknowability' of some concrete mathematical objects. If we list all numbers up to a given number of digits the list will contain Omega up to that number of digits.

• maybe we misunderstand each other, but I don't mean computability in the sense of being able to compute all the digits - the number pi is a transcendental real number and it is impossible to compute all its digits since there are infinite number of digits to pi, yet they are computable, for any N the Nth digit of pi can be computed in finite time. I meant in the post that there are real numbers that are not computable in this sense.
– nir
Commented Aug 6 at 19:08
• I didn't mean that either - The key is there is no single finite algorithm A(n) to find any nth digit. We can prove such numbers exist as a string of digits, but we can't find them in this way. It is related to the existence proof of theorems which can't be proved which however must be true. Commented Aug 7 at 8:26
• ah, interesting (btw, I'm not the down-voter)
– nir
Commented Aug 7 at 9:05
• One could say that Chaitin's Omega is well defined mathematically and that there are only countably infinite well defined numbers, so that necessarily not all real numbers are computable or well defined.
– nir
Commented Aug 8 at 20:53

The question makes some wrong assertion about what can be done with uncomputable numbers, though this is not strictly relevant to the question, and should rather go to a math forum.

Uncomputable numbers are well defined, and we can simply assert: "uncomputable numbers cannot be the result of computation to arbitrary precision, so how can we say they exist?" That would make the question more concise and less confusing.

Though the other answers are already great, and it's unclear how being computable to any precision (but never fully computable) is a great line to draw. Definability would seem a little more relevant: https://en.m.wikipedia.org/wiki/Definable_real_number (though the answers would likely remain same). They are also called non-finitely describable numbers (there is no finite description of them using any formalism).

The fineprint however is that many uncomputable numbers can still be computed to a certain degree of precision (like the first 1 million decimals). We can call them n-uncomputable if they are not computable starting with precision n. We can trivially construct such numbers like the number that starts with one million zeros after the dot, and then continues with the digits of uncomputable number x. (It looks like cheating, but that's how maths work).

And for n-uncomputable number, we deal with them in computation in the same way we deal with computable numbers in practice, even if we do calculations with pi, a real and computable number, we never completely calculate all infinite digits of pi in a mathematical computation.

Even in theory, we can do computation with total precision in some cases. E.g. for computation of multiplication of rational numbers, we can use their representation as fraction to get precise results in finite time. Like 1/3 + 1/3 + 1/3 = 1 (though this depends on the algorithm and representation used). The same may be possible with some combinations or representations of uncomputable numbers. And this is a crucial difference to indefinable numbers. Without a definition, even if we use a symbol, we cannot express what that symbol stands for. Yet still most real numbers are indefinable.

The other issue is the statement

therefore most real numbers are not an answer to a computable mathematical problem.

This is wrong because in maths we can define problems that can be solved without computing all digits of any real number. As a silly philosophical example, 1 * x = x. Can be solved without going through each digit.

We can also imagine maths problems dealing with combinations of uncomputable numbers that happen to have a computable result. Such as x - x = 0 can be computed without going through all digits of x.

Another philosophic issue behind the question is hat computability as defined using e.g. turning machines is not a useful philosophic boundary to existence, as other forms of computation such as quantum computing would introduce different sets like quantum-computable numbers, which might be uncomputable on a turing-machine, but computable in a quantum computer. And that's just one possibility, philosophically we cannot assert the impossibility of other such forms of computation. Just because we don't know them (yet) does not mean we can draw a line.

So computability as currentlty defined is probably totally irrelevant to philosophy. (And maybe will be called turing-machine-uncomputable numbers one day).

My Naive Intuition

When I am in grade school the teacher drew a chalk line on the blackboard. She said this is a line segment. The formal definition of a line is infinite lenght in both directions. Also each line segment, no matter how small, contains an infinite number of points. This blew my mind! An infinity of infinities? An unbounded universe? I thought the line wants to bend, curve around on itself, and form an huge circle like the great circle of a massive sphere! This is what formed my intuition for the concept of the real numbers in my math and engineering studies: an infinite set of indefinite points that maps to any line segment and/or to the whole line! When we compute a real number in the set of real numbers we intuitively or formally put it into an ordered set on the so-called real number line.

It seems to me that a real number ought to be in theory computable simply by doing any computation that generates more digits, for example, the way we compute pi. We iterate using an algorithm to find more digits of pi and these would map to greater precision of real number description in a model of the number line. But then we run out of time, talent, or inventive machinery to compute more digits of pi with current technology. Then we think these numbers exist but are uncomputable due to time and talent and technology constraints, or something like that?

I admit that formal mathematics is not my primary area of study or talent. My intuition may be far from what mathematicians mean by computable or uncomputable real numbers.

• No. Uncomputable numbers defy intuition, so some understanding of computer science theory is required. Real numbers with infinite digits like pi still count as computable. See math.stackexchange.com/questions/58036 , math.stackexchange.com/questions/462790 Commented Aug 8 at 20:21
• It's easier to think intuitively about the indefinable real numbers. They have infinite digits, and there is no way anyone can tell anyone else how to build one of them, other then by sending an infinite letter containing the whole number. That's different from pi where we can describe the number in a geometric way. Commented Aug 8 at 20:40