Kolmogorov Complexity
Written by Mike James   
Thursday, 26 July 2018
Article Index
Kolmogorov Complexity
Random Numbers

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.

Kolmogorov Directions

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


Related Articles

The Programmer's Guide To The Transfinite

Confronting the unprovable

Non-computable numbers


What is a Turing Machine?

Axiom Of Choice - The Programmer's Guide 



A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP



  1. What Is Computable?
  2. Finite State Machines
  3. What is a Turing Machine? 
  4. Computational Complexity
  5. Non-computable numbers
  6. The Transfinite
  7. Axiom Of Choice
  8. Lambda Calculus
  9. Grammar and Torture
  10. Reverse Polish Notation - RPN
  11. Introduction to Boolean Logic
  12. Confronting The Unprovable - Gödel And All That
  13. The Programmer's Guide to Fractals
  14. The Programmer's Guide to Chaos*
  15. Prime Numbers And Primality Testing
  16. Cellular Automata - The How and Why
  17. Information Theory
  18. Coding Theory
  19. Kolmogorov Complexity

*To be revised

kotlin book



or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.





Last Updated ( Thursday, 25 October 2018 )