7
$\begingroup$

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.

Thanks you all very much!

$\endgroup$
3
  • $\begingroup$ for better response plz cite where you read this & the exact stmt. fyi turings early 1936 essay considered the idea. see computable numbers / wikipedia $\endgroup$
    – vzn
    Mar 25, 2015 at 23:00
  • $\begingroup$ @vzn What is the precise idea considered by Turing? Using randomness? No computer program can print an uncomputable number, $\endgroup$
    – babou
    Mar 26, 2015 at 1:37
  • $\begingroup$ @babou basically/ roughly as sketched out in some answers below, a 1-1 correspondence can be made between reals and computable functions to show that not all reals are computable. so Turings result on undecidability can be seen equivalently as a proof of the existence of uncomputable real(s). as to the other angle in the question, random numbers in computers are computed via pseudorandom functions and therefore do not escape this inability to compute uncomputable numbers. $\endgroup$
    – vzn
    Mar 26, 2015 at 15:56

3 Answers 3

5
$\begingroup$

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 $n^{th}$ symbol the opposite (1 for 0, and 0 for 1) of the $n^{th}$ symbol of the $n^{th}$ 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\in[0.0, 1.0[$ defined as follows: its $n^{th}$ digit is $1$ iff the Turing Machine with Gödel number $n$ halts on empty input, and $0$ otherwise. This number is very precisely defined. But if it were computable, we would have a way to decide the halting problem. Hence, there is no algorithm, no program, that can enumerate the bits of the real number $h$, and thus there is no way to print it. And using random generators will not help.

Of course, it could be that some random generator, controlled by a random physical process such as radioactive decay would produce precisely that number (with a probability closing to zero as time passes). But, at best:

1- you would have at any time only a rational number which is a prefix of the non-computable real you are interested in

2- you would most likely be unable to check wether your prefix is really correct

3- you would have no garantee that the next digit will still be correct.

But, even then, you must assume that the random generator uses some physical "true" randomness source. Even randomly created, or computing with whatever technique known or yet to be invented, no computer program can print an uncomputable real number, such as the number $h$ defined above. That is a result of computability theory that no such program can exist.

Your only hope is that computability theory does not apply to radioactive decay or some other such physical phenomena. But I know of no proof either way. And it would not really help you in any meaningful way, because the probability of success is zero, and because you would have no way of knowing you are succeeding. Note that I cannot say "of knowing you have succeeded", because you never reach the end of that infinite process, so that any proof would have to be an on-going continuous process, which cannot be finitely defined for essentially the same reason a printing program cannot exist for an uncomputable number.

$\endgroup$
2
$\begingroup$

Not all real numbers can be printed.

Consider some system of representing numbers using a finite number of symbols. You can make this system as complex as you want: decimal numbers, fractions, roots, integrals, trig functions, etc.

Because there's a finite number of symbols in any system we have to write or print a number, we can create a bijection from the set of numbers we can write down to the integers.

Cantor proved that there is no 1:1 mapping from the integers to the real numbers. Which means, there are more real numbers than we can print.

Now, there are real numbers which we can't enumerate: that is, there's no algorithm saying "give me the first $n$ symbols of an infinite-length representation of this number.

The thing is, uncomputable numbers do exist. Your random generator could, by chance, generate the first $n$ symbols of an uncomputable number. But there's no way to check if those first $n$ symbols are correct, and there's no way to get the $n+1$th symbol, even if we have the first $n$ symbols.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer. But imagine my program has an loops infinitely printing a random sequence of numbers of a random length (and randomly writes or not a point in this sequence). Given any real number possible and enough time my program would print it or maybe not. But theoretically is possible. Isn't this right? $\endgroup$
    – NMO
    Mar 25, 2015 at 16:01
  • $\begingroup$ So, the string is infinite, so at any point it's possible you will have outputted the first $n$ symbols. Given enough time, for any $n$, your program will print the first $n$ symbols of an undecidable number. But 1. you have no way of knowing that you've printed the correct digits, and 2. you never print the "whole" number, since its sequence is infinite. $\endgroup$
    – jmite
    Mar 25, 2015 at 21:37
1
$\begingroup$

This is not really an answer to your question, but a direct consequence from the fact that "$\mathcal{R}$ is uncountable", which may interest (or dismay) you.

There are much more unsolvable (in terms of Turing-decidable) problems than solvable ones.

The argument is as follows:

The set of all algorithms (represented as Turing machines) is countably infinite, equinumerous to the set of natural numbers $\mathcal{N}$. We can each Turing machine into a string and count them one by one, e.g., in the order of the increasing string length (note that the alphabet $\Sigma$ is finite).

However, the number of all the problems (represented as languages) is $2^{\mathcal{N}}$ (it is the number of mappings from $\mathcal{N}$ to $\{0,1 \}$), which is uncountably infinite. It is impossible to count/print all the algorithms, just like it is impossible to count all the real numbers.

We conclude that some problems have no corresponding algorithms at all. Even worse, there are much more unsolvable problems than solvable ones.

$\endgroup$
1
  • $\begingroup$ This seems pretty close to what the OP is saying, less formally, and with a mathematical error, in his first paragraph. And it also appears in some form in the other answers, including mine. However, I do not feel too confortable with it since I tried to understand the interpretation of Cantor's diagonal argument in Wikipedia. It seems to state that constructivist mathematicians do not infer from that a "difference in size (cardinality)", as classical mathematicians do, but only the non-existence of a bijection. $\endgroup$
    – babou
    Mar 26, 2015 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.