July 19, 2010

Your name, my name, someone's name and its Kolmogorov Complexity

While I was reading across a paper on Compression and Machine Learning, I came across the concept of Similarity/Dissimilarity measures and how they are defined empirically in terms of the Kolmogorov Complexity(KC). The term can be put in simple terms as the length of a program or algorithm required to output the particular string for which the complexity is being calculated. So in that case, assuming that we are using the natural language (english in this case) to output the required string, the KC for my name : "Satish Kumar Eerpini" is 20, since there are 20 characters. Now if I consider some other name then the KC for that name would be the number of characters in the english representation of that name, so on so forth !
Now what really struck me was, that it should be possible to write a program in some arbitrary language which can output any name, that is the KC is constant for any name. Now how can that be done ? ... keep thinking, while I try my best to come up with something !