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

Question

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?

Answer 1

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.

Answer 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?

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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.