REVIEW 2 cited by
Shannon Information and Kolmogorov Complexity
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and where they are fundamentally different. We discuss and relate the basic notions of both theories: Shannon entropy versus Kolmogorov complexity, the relation of both to universal coding, Shannon mutual information versus Kolmogorov (`algorithmic') mutual information, probabilistic sufficient statistic versus algorithmic sufficient statistic (related to lossy compression in the Shannon theory versus meaningful information in the Kolmogorov theory), and rate distortion theory versus Kolmogorov's structure function. Part of the material has appeared in print before, scattered through various publications, but this is the first comprehensive systematic comparison. The last mentioned relations are new.
Forward citations
Cited by 2 Pith papers
-
How much do language models memorize?
A compression-based measurement puts GPT-style model memorization capacity at roughly 3.6 bits per parameter, with membership inference success following a sigmoid in the dataset-to-capacity ratio.
-
Breaking through the classical Shannon entropy limit: A new frontier through logical semantics
The authors state a Shannon-style rate bound for communication with deductive reasoning, governed by a function they call logical semantic entropy, but provide no proof in this text.
Discussion (0). Continue with ORCID to comment.