Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
3  
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 Dec 10 '13 at 21:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.