I\'ve recently read that there were many real numbers that would never be reacha

Question

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there are infinite real numbers between two integers so Real numbers infinity is bigger than integer numbers.

Well my question is, couldn't we overpass this limitation by writing a program that prints out a random number in every execution? I know this is not a warranty that every real number would be printed but at least they would all have a chance.

Please point out if my reasoning is wrong and why.

Explanation / Answer

In a nutshell: Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique property. But these cannot be printed by any program precisely because they are not computable. Using randomness in the hope of printing by chance the uncomputable number you are interested in is impossible with a program, unless you use a physical random phenomenon as randomness source (depending on physics, with probability zero, and without knowing whether you are succeeding).

I am not sure what you mean by a number that is not "reachable by humanity".

The fact that there is an infinity of real numbers between two integers does not imply that there are more real numbers than integers (though there are more).

For example, there is an infinity of rational number between two integers, but the number (cardinality) of integers and rational numbers is the same. Actually, there is an infinity of rational numbers between any two rational numbers, but it does not imply that there are more rational numbers than rational numbers.

By the way, there is an infinity of rational numbers between any two real numbers, but there are more real numbers than rational numbers.

That should at least tell you that determining which set is bigger is not at all obvious, and is not related to the number of angels who can dance between two numbers.

Then why are there more real numbers than integer? Here is one of the proofs due to Cantor. The reals in the interval [0.0,1.0[ are isomorphic to infinite sequences of the symbols 0 and 1, which is their representation in binary notation (by just adding a decimal/binary point in front). If you consider any enumeration of these infinite strings, it is always possible to define a string that is not in the enumeration, by using for its nth symbol the opposite (1 for 0, and 0 for 1) of the nth symbol of the nth number of the enumeration. This means that if you attempt to define a one-one correspondance between the integers (used to enumerate) and the reals (being enumerated) there are always reals that are not included in the enumeration, which can be interpreted as implying that there are more reals than integers.

This technique is a diagonalization proof, similar to the proof technique used for proving the undecidability of the halting problem.

Now, as remarked in the question, any program texts can be read as an integer, so that one may consider there are no more programs than integers. This is why we may conclude that there are numbers that cannot be computed by a program, hence cannot be printed (else, each real could be mapped to the integer corresponding to the program that prints it.). But this fast reasonning may not be so convincing, so lets get more into details. and also consider an actual example.

Your printing device, assuming it does what you expect, even if it started at the big bang, is only producing digits one by one, and will at any time have produced only a finite number of digits, say n. That only defines a rational number, and even if we are actually printing some irrational number. Assuming we are using binary numbers, if we have already printed n digits, they correspond to a rational number x, and all we know is that the number we ultimately print will be in the interval [x,x+2?n[. But this interval will always contain an infinity of rational numbers, of computable real, and of uncomputable reals. And this will remain so for any future value of n. Stating that you want to print an uncomputable number, any uncomputable number, is a meaningless endeavor. It reminds me of people looking for the pot of gold at the foot of the rainbow.

The meaningful problem is not to write any uncomputable number, but to write a specific one, identified by a specific property. Consider for example the binary real h?[0.0,1.0[ defined as follows: its nth digit is 1 iff the Turing Machine with G

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.