[Solved]: Kolmogorov Complexity: Why would you need more bytes than the string itself?

Problem Detail: 

I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states:

It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself.

Why would you ever need anything more than the string itself to describe it?

Asked By : loneboat

Answered By : Gilles

The exact value of the Kolmogorov complexity depends on the language chosen to represent strings. This language has to be Turing complete, so representing all strings as themselves isn't an option.

By the pigeonhole principle, if there is at least one string of length at most $n$ whose representation is shorter than itself, then there is also at least one string of length at most $n$ whose representation is longer than itself. (The representation is a compression algorithm.)

You can have a description language where each string has a representation that's at most one bit longer than itself: start each representation with a bit that indicates either "print literally" or "interpret". Not all description languages are that simple though.

A more formal statement is given further down in the Wikipedia article, in the invariance theorem section. There are optimal description languages, such that for any given language, there is a constant $C$ such that the description of any string in the optimal language (no matter what its length is) is at most $C$ bits longer than in that other language. Intuitively, write an interpreter for the other language in the optimal language.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18842