More on Kolmogorov Complexity

There is a great Dilbert cartoon explaining the need for Kolmogorov complexity. Because of copyright issues, I won't put it here (but you might find it at the bottom of Sophie Laplante's web page). Reading the cartoon you might find it funny because not all strings seem equally random even if they are equally likely. Kolmogorov formalized this idea by measuring the randomness of a string x, denoted C(x), by the smallest program that generates x.

At this Dagstuhl workshop there are many talk on a number of variations of Kolmogorov complexity. John Tromp had a nice presentation on the basic notion. He showed, among other things, that for any x you can find a constant length y such that C(xy)>C(x). This seems obvious but it is pretty tricky tor prove. Tromp's proof works by defining a new C-based measure on strings and using that to show that any string x has a small number of programs generating x that have length close to C(x) and using that fact to get his result. He doesn't have a write-up yet, but I'll keep a lookout for it.