Random and Pseudo Random

It is also worth spending a moment to consider what all this means for the generation of random sequences. A pseudo random number generator is usually a small program, which means that that the numbers it produces might well be statistically random but they are clearly not algorithmically random as their Kolmogorov complexity is low. 

So how could we create an algorithmic random number generator? 

You can probably notice the paradox in attempting to build a random number generator that is algorithmic but larger than the sequence it produces. Perhaps this is the key to the difference between pseudo random and physically random numbers. 

The annoying thing about Kolmogorov complexity is that it is easy to understand and yet in any given case you really can't measure it in any absolute sense. Even so, it seems to say a lot about the nature of the physical world and our attempts to describe it.

You will notice that at the core of this understanding is the idea of a program that generates the sequence of behavior. It is tempting to speculate that many of the problems we have with, say, modern physics is due to there simply not being enough programs to go around or, what amounts to the same thing, too many random sequences. 

So to return to the xkcd cartoon.

The minimum form of the directions to get to a location gives its Kolmogorov complexity and is the most compact representation of the information. In this case what is offered is a program that generates the directions, but as you can appreciate this is not the most useful form of "how to get there" from the point of view of a typical human. One more reason we should all learn to program.... 

<ASIN:3642071651>
<ASIN:0387339981>
<ASIN:1852334177>

<ASIN:1400077974>