Comment on page
39.2 Optimal Compression, Kolmogorov Complexity
We define the Kolmogorov complexity of a bitstream
Bto be the shortest bitstream
B. Let the Java-Kolmogorov complexity
be the shortest Java program that generates
Note that for any bitstream
definitely exists. However, finding and proving
might be difficult or even impossible.
An important thing to note is that Kolmogorov complexity is language-independent. To run any program in one language in another, all I have to do is write an interpreter. For example, if I want to run a Python program that is not easily translatable to Java, I could instead just write a Java interpreter to read the text of the Python program and run it. In this case,
is the length of the interpreter (a constant value).
This highlights a very deep fact about Kolmogorov complexity: most bitstreams are fundamentally incompressible no matter which language we choose for our compression algorithm.
Consider a bitstream of 1,000,000 bits. Out of all compression algorithms possible, only 1 in
bitstreams have a change of being compressed by more than 50% (499,999 bits or less).
Practically, this means that it is impossible to write a "perfect" (optimal) compression algorithm, since we can't even compute the length of the shortest program!