Pith. sign in

REVIEW 3 cited by

Shannon Information and Kolmogorov Complexity

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv cs/0410002 v1 pith:T2Z22PBJ submitted 2004-10-01 cs.IT math.IT

Shannon Information and Kolmogorov Complexity

Peter Grunwald (CWI) , Paul Vitanyi (CWI , University of Amsterdam) This is my paper
classification cs.IT math.IT
keywords kolmogorovinformationshannonversuscomplexitytheoryalgorithmicmutual
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method

    cs.IT 2026-06 unverdicted novelty 7.0

    A new BDM variant formalizes reuse of program code across blocks as an NP-hard optimization problem, relates gains to algorithmic mutual information, and proves improvement over independent block descriptions under st...

  2. Manifold Steering Reveals the Shared Geometry of Neural Network Representation and Behavior

    cs.LG 2026-05 unverdicted novelty 7.0

    Manifold steering along activation geometry induces behavioral trajectories matching the natural manifold of outputs, while linear steering produces off-manifold unnatural behaviors.

  3. Forget BIT, It is All about TOKEN: Towards Semantic Information Theory for LLMs

    cs.IT 2025-11 unverdicted novelty 5.0

    Proposes a semantic information theory for LLMs that substitutes the token for the bit as the atomic carrier of meaning, recasts the Transformer as an energy-based model, and derives directed rate-distortion and rate-...