I was more interested in learning about the possible theory behind such a limit, to see if we had a way to actually know how far such optimisations can go. Basically, for any given file, what would be the absolute best we could hope for (without resorting to losing information).
In a world where every single file is exactly "abcd", it takes zero bits to represent the file - you don't need any information to know that the file contains "abcd" because all files do.
In theory, the language you use to output the file could have a one-bit coding '0' for "produce the file 'there are comments on HN'" (and all other commands starting with '1...'). So in the world we live in, the smallest a file can be compressed to is 1 bit - if you just use the right language.
None of these are practical in general, but the point is that Kolmogorov Complexity is not meaningful without specifying more assumptions/priors.
Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
For those interested also unfamiliar with it:
- https://eprint.iacr.org/2021/1333.pdf
- https://matt.might.net/articles/why-infinite-or-guaranteed-f...
All major compression libraries that I know of essentially work by "factoring out" statistical regularities in the input string--i.e. repeating patterns. But many strings have regularity that can't be captured statistically. For example, the sequence 1, 2, 3, 4, ... has an entropy rate of 1, because all digits and all subsequences of digits occur with equal frequency, so most modern compression libraries are going to be unable to compress it to any significant degree [1]. However, it obviously has a very compact representation as a program in your favourite language.
If you want to go down a bit of a rabbit hole, this video from a researcher in this field gives an overview, as well as some proposed methods for approximating Kolmogorov Complexity in a reasonable way (even though in a technical sense approximating it with known, fixed bounds is I believe impossible): https://www.youtube.com/watch?v=HXM3BUXsY4g. This paper also discusses a theory that decomposes KC into a statistical part (Shannon entropy) and a "computational part": https://csc.ucdavis.edu/~cmg/compmech/pubs/CalcEmergTitlePag....
[1]: Note that if you encode it as ASCII or even N-bit integers there will be significant redundancy in the encoding. To properly test it you'd have to encode the numbers in a packed binary encoding with no padding.
Encoding algorithms end up getting specialised for particular types of data because different data exhibits different patterns.