4 ms·
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
by 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 agoAbsolutely, 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 agoThis 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 agoIt's a misconception the "universal prior" is at all helpful.
- guimplen 3y agoThis universal prior is both theoretically useful and help conceptualize the real-world compression techniques.