# Kolmogorov Complexity: Why would you need more bytes than the string itself?

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?

## 2 Answers

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.

The description of a string considered here is an input to some universal Turing machine. You can think of it as a C program. The string hello world does not, by itself, form a C program, but the following one does: int main(int argc, char *argv[]) { printf("hello world"); }. As you can see, the overhead is constant but not zero.

• As an added subtlety, it is not possible in C (or an idealized Turing-complete C) to print arbitrary strings with O(1) space overhead, because some characters in string literals need quoting. – Gilles 'SO- stop being evil' Dec 10 '13 at 21:57