Month: May 2005

Is there an algorithm that can generate random numbers? Of course, the question is if there is such an algorithm which is deterministic. But a deterministic algorithm always provides deterministic results. So the question is – can we provide an algorithm with a random seed, in such a way that it will provide an infinite range of random numbers in an unpredictable way? The answer is obviously no. I can prove it!

First, I already showed that it’s not possible to select a random number in the range 0 to 1, if all the possible numbers have the same probability. Since we can treat an infinite series of random bits (either 0 or 1 with the same probability) as a real number between 0 and 1, then it seems that I already proved it. But to clarify it, I only proved that we can’t tell such a selection, I didn’t prove we can’t make one. But if we can define an algorithm that can create such a series, this is equivalent to defining the number or telling it. Therefore, there exist series of 0 and 1 which no deterministic algorithm can create!

Second, if we consider the number of bits necessary to write down both the algorithm and the random seed, we can define this as n. Then there are only 2ⁿ number of possibilities for strings of length n. And therefore, the number of different series we can produce with n bits (both the algorithm and the random seed) is not more than 2ⁿ. And for any known algorithm, only the number of bits in the random seed counts. For n bits, this algorithm will create no more than 2ⁿ different series. This means that theoretically, if we see the beginning of a series given by this algorithm (the first m bits for some m) then we can tell the rest.

But, we can still create series of numbers (or series of bits) which look as random to us – that is, we can’t tell any order in it, we can’t compress it and so on. I like to define it with the word entropy (taken from physics). I was about to define it, but it seems that there is already a good definition in Wikipedia. In other words – although we can’t generate a true random series, we can generate a series which will look random to any observer. That’s good enough.

I like to consider irrational numbers, like the square root of 2 for example, as a series of pseudo-random bits (when written in the binary form). That is – there is no order in it, we can’t compress it and so on. While I will not try to prove it, I think it’s quite obvious. If you don’t believe me, then I’d like to give you a challenge – prove that the google (10¹⁰⁰) bit is either 0 or 1 (that is, either prove it’s 0, or prove it’s 1). I bet you can’t do it. And if for some strange reason you do succeed, try google! (the factorial of google) or googleplex (10^google).

If you need a way to calculate the first n digits of the binary form of the square root of 2, here’s a simple algorithm. Of course, you need to implement it or use a software which lets each number have n bits of precision (after the dot).

1. let x be any seed number, such as 1.
2. let x2 = 2/x.
3. let x be (x+x2)/2.
4. If the first n digits of x2 and x are not equal, go to step 2.
5. The result is x.

It can be proved that this algorithm converges very quickly – in about O(log₂(n)) iterations. That is, to calculate the google first bits will take less than 500 iterations of this loop (or actually, something around 332, which is the log of google in base 2). But the problem is, in order to make calculations of n precision you will need to store n bits, and the calculation itself will take about O(n) steps in machine language. So the total amount of time to calculate the first n bits of the square root of 2 is about O(n*log₂(n)). I doubt you will ever get to implement it for google!

Therefore, I can claim that there exists an integer n, which for every bit of the square root of 2 beyond the nth bit, we can’t prove that it is 0 and we can’t prove that it is 1. It’s not that we can’t calculate it – we can calculate it in theory, but it will take infinite time (that is, the calculation will never end during our life time). This is also related to the halting problem – the algorithm to calculate the first n bits of the square root of 2 will halt for every small n, but for big values of n it will never halt. Of course you can claim that in theory it will halt, but in reality there exists an integer n for which it will never halt. Even for relatively small numbers it will not halt – such as google, and you need only 333 bits to represent google in the binary form.

Since we don’t know if the googleth bit of the square root of 2 (and any bit beyond it) is 0 or 1, we can define its probability to be 50% for either 0 or 1. I’m not going to prove this mathematically, but for me it makes sense. Although every bit is either definitely 0 or definitely 1 (according to mathematical logic), for us it has 50%/50% probability to be either 0 or 1. This is like the uncertainty principle in quantum physics – we don’t know something, and we know we don’t know it, but we can define its probability for every possible value. The probability is not inherent in the value itself, but it is our knowledge of it. Although the value of every bit of the square root of 2 is deterministic, we can look at it in a probabilistic way.

A few days ago I came across the Clay Mathematics Institute’s website, and the one million dollar prizes they set for the people who will succeed in solving a few math problems. One of these problems is the famous P vs NP problem, which I came across during my studies of computer science. In the last few days I read some information about related issues – mostly mathematics and computer science issues. The main source I used was Wikipedia (in English), which is a very good source for reading information about anything.

Among the articles I read in Wikipedia are articles about the halting problem, the axiom of choice, P vs NP and other interesting issues. I decided to comment about these issues, and that’s the main reason for starting my own weblog.

The first subject I would like to comment about is the axiom of choice. The reason is because I believe this axiom is not true. Here is a short explanation why I think it is not true:

Suppose we have to select a random real number in a given range, say from 0 to 1. This can be achieved by various ways in real life, such as turning a roulette, throwing a dart, using computers random number generators etc. And suppose that each number in the range has an equal probability of being selected. Then I claim that this is already a paradox! And even if we limit ourselves only to rational numbers, it is still a paradox. It’s not possible to make such a selection. Only if we limit ourselves to rational numbers with a certain precision – that is, only if the set of possible numbers is finite, then we are able to make such a selection. Or, if we don’t require that each number will have an equal probability of being selected (this I will show later).

Why is it a paradox? Because the sum of all probabilities to select each number must be exactly 1. If there are infinite possible numbers, and all the probabilities are equal, then each probability must be exactly 0 (this is easy to prove). And if a probability is 0, then it cannot occur! Of course this still has to be proved, but I think it’s already intuitive. Things with probability 0 just don’t happen!

I want to tackle this issue from a different point of view. The issue is not selecting a number, but telling which number was selected or writing it down. Of course we can still claim that we can select a number even if we can’t tell it or write it down, but this is like claiming about anything else that we know it and can’t tell it, for example I can claim that I know whether P and NP are equal or not but I can’t tell you, or that I know whether any given algorithm halts or not but I can’t tell you, and so on. Therefore, I would assume that if we can’t tell what number we selected and we can’t write it down, then we can’t make the selection. This is true for all practical purposes.

Now, let’s consider the ways we write down numbers. There are a few ways to write numbers: The most common way is decimal (or binary) representation (either fixed point or scientific representation). We can represent any real number with binary representation (or at any integer base). The problem is: with some numbers, this representation is infinite. For rational numbers, it’s periodic, but for irrational numbers it isn’t. Therefore, if we wanted to write down a real number which is not rational in the binary form, it would take us an infinite number of digits. Which leads to the question if such numbers really exist. This is a philosophical question. But if we assume they exist, we are able to write them down in alternative ways (not binary representation) – for example: e, PI, and the square root of 2.

Lets consider all the ways to tell a number or write it down. We can decode each way in the binary form and save it to a binary file. Everything can be encoded into binary files: text, graphics, voice etc. But with n binary bits, it’s possible to write down only 2ⁿ different files. Therefore, not more than 2ⁿ different numbers can be represented with n bits. The number 2ⁿ grows exponentially, but it’s still finite. It’s not possible to represent an infinite number of different values with a finite number of bits.

How is this related to selecting a real number in a given range, or with the axiom of choice? Well, there is only a finite number of different numbers we can write down or tell with a finite number of bits (or in a finite time). Therefore, the number of numbers we can ever write down or tell is countable (I think it’s what we call definable numbers). So if a set is uncountable (for philosophical reasons, I don’t think any uncountable set really exists, but this is another story) – then it must contain numbers which we will never be able to tell! Or in other words, we can define a set of all the definable numbers (numbers we can tell) and subtract it from the set of real numbers, and the result will be a set of numbers none of which we will ever be able to tell. And therefore, we are not able to select an arbitrary number from that set.

Now, what about rational numbers? Can we randomly select a rational number in a given range? I say we can, but we can’t give all the numbers the same probability. We can give each number a positive probability (more than 0), but if we insist in giving each number the same probability – we will still not be able to tell which number we have selected. Or to be more accurate, the probability that we will be able to tell which number we have selected is 0. This is because for each number of bits n, there are only a finite numbers that can be represented with up to n bits, but an infinite numbers which require more than n bits.

On the other hand, if we don’t require all the numbers to have the same probability, then we can definitely select a number within the given range. This is trivial and very easy to prove. We can just select bits at random, and after selecting each bit select randomly whether we should stop or keep selecting more bits. We can show that each number has a positive probability to be selected. This can be shown with any countable set, not just with rational numbers.