39.2 Optimal Compression, Kolmogorov Complexity
Kolmogorov Complexity
Languages and Complexity
This highlights a very deep fact about Kolmogorov complexity: most bitstreams are fundamentally incompressible no matter which language we choose for our compression algorithm.
Uncomputability
Another important fact regarding Kolmogorov complexity is that it is impossible to compute. A proof of this fact is provided here.
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!
Last updated