4 ms·

I wouldn’t have thought of that. 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 f

by ElFitz 3y ago

I wouldn’t have thought of that. 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).

MauranKilom 3y ago
That question makes pretty little sense without fixing some constraints like "what other files exist" and "what language are you allowed to reproduce them". 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.
- ElFitz 3y ago
  Absolutely, that is part of what I have come to understand while diving into the topic. That I first needed to answer quite a few other questions for that one to even make sense. Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
- guimplen 3y ago
  This is a misconception. The main result in the Kolmogorov complexity theory that there is precisely the "universal prior" that comes simply from the notion of computability.
  - Ono-Sendai 3y ago
    It's a misconception the "universal prior" is at all helpful.
    - guimplen 3y ago
      This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.
oh_sigh 3y ago
Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.
- ElFitz 3y ago
  Not at all! Having basically no knowledge in that area, aside from a vague understanding of the purpose and uses of information theory, it is more than welcome! For those interested also unfamiliar with it: - https://eprint.iacr.org/2021/1333.pdf https://eprint.iacr.org/2021/1333.pdf - https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/ https://matt.might.net/articles/why-infinite-or-guaranteed-f...

by ElFitz 3y ago

MauranKilom 3y ago

That question makes pretty little sense without fixing some constraints like "what other files exist" and "what language are you allowed to reproduce them". 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.

ElFitz 3y ago
Absolutely, that is part of what I have come to understand while diving into the topic. That I first needed to answer quite a few other questions for that one to even make sense. Thank you for the examples; they are much clearer and straightforward than most of those I’ve come across.
guimplen 3y ago
This is a misconception. The main result in the Kolmogorov complexity theory that there is precisely the "universal prior" that comes simply from the notion of computability.
- Ono-Sendai 3y ago
  It's a misconception the "universal prior" is at all helpful.
  - guimplen 3y ago
    This universal prior is both theoretically useful and help conceptualize the real-world compression techniques.

oh_sigh 3y ago

Not to be pedantic, but for any given file the answer is 0% compression, due to the pigeonhole principle.

ElFitz 3y ago
Not at all! Having basically no knowledge in that area, aside from a vague understanding of the purpose and uses of information theory, it is more than welcome! For those interested also unfamiliar with it: - https://eprint.iacr.org/2021/1333.pdf https://eprint.iacr.org/2021/1333.pdf - https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/ https://matt.might.net/articles/why-infinite-or-guaranteed-f...