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...