Re:Shannon’s Source Coding Theorem (Foundations of Informati...
by ElFitz on Sunday June 18, 2023 @11:40AM
(#36381238)
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.
Re:Shannon’s Source Coding Theorem (Foundations of Informati...
by guimplen on Sunday June 18, 2023 @05:58PM
(#36384939)
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.
Re:Shannon’s Source Coding Theorem (Foundations of Informati...
by Ono-Sendai on Monday June 19, 2023 @12:45AM
(#36387397)
It's a misconception the "universal prior" is at all helpful.
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.