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.

## No comments:

## Post a Comment