nucleation

LIT-229: Meaningful Information

2 min read

Properties5
StatusActive — read 2026-10-14 (NOTE-790) in full; worth reading as the short proof that splitting an individual string's information into structure and noise works only in a model class without a universal member: with partial recursive models every string's minimal sufficient statistic is trivial (Lemma 6.2), while with total recursive functions sophistication runs from about 0 for random strings to above n − log n − 2 log log n for some string of every length (Theorem 6.5), and agrees with the finite-set and probabilistic versions to within O(log n) (§VII). Read it knowing that everything holds only to within additive constants or logarithmic terms, that sophistication is uncomputable and not usefully approximable, that two steps rest on cited work (Gács–Tromp–Vitányi; Vereshchagin–Vitányi), and that the structure-function characterisation of §IX is stated, not proved.
Version2
Tagslearning-theory, information-theory, mathematics
Cited as “paper” byNOTE-212 — Meaningful information (sophistication), NOTE-790 — Vitányi — Meaningful Information
Cited as “source” byTHEORY-260 — An individual string's information splits non-trivially into structure and noise only in a model class without a universal member: with partial recursive models every string's minimal sufficient statistic is trivial, while with total recursive functions it is not, and the finite-set, computable-distribution and total-function classes agree to within logarithmic terms

Graph View

Paul M. B. Vitányi (2001), IEEE Transactions on Information Theory 52(10):4617–4626 (Oct 2006); earlier version in Proc. ISAAC 2002 (LNCS); first appeared as arXiv preprint — arXiv:cs/0111053

Key takeaways

From the reading, NOTE-790.

  • The two-part split. K(x) =⁺ min_T {K(T) + K(x | T)}. A total recursive f is a sufficient statistic for x when K(f) + l_x(f) =⁺ K(x), and sophistication is the least such K(f).
  • A universal model trivialises it. With partial recursive models, soph(x) =⁺ 0 for every x, because the universal machine absorbs every model into the data part (Lemma 6.2). Totality is what keeps the split non-trivial.
  • Both extremes occur. Random strings have sophistication about 0 (Theorem 6.5(ii)). For every n some string has sophistication above n − log n − 2 log log n (Theorem 6.5(iv)): nearly incompressible, yet almost all structure.
  • The model classes agree, asymmetrically. Finite-set → probabilistic → total-function sufficient statistics correspond within a constant (Lemma 7.1). The way back costs O(log n), in sufficiency too (Lemma 7.2).
  • Uncomputable. soph is not recursive (Theorem 8.1). A sufficient-statistic oracle computes K and the halting sequence (Theorem 8.3). The witness program is as hard to get from x as K(x) is (Theorem 8.5).
  • Stated, not proved here. Sophistication is where Kolmogorov’s structure function first reaches K(x) (§IX, deferred to Vereshchagin–Vitányi).

Standing in the record

Filed on 2026-09-26 at the owner’s request, from a list they grouped under the heading Relating K-complexity to minimum sufficient statistics. Read in full on 2026-10-14 in NOTE-790. It is the record’s statement of the minimal sufficient statistic for total-function models, and of why that class, not the universal one, is where the split into structure and noise makes sense. Its main results are filed as THEORY-260.

It is the predecessor of Vereshchagin and Vitányi’s structure-function paper (LIT-239), which holds the full finite-set theory this paper transfers. Read the two together. For THEORY-036 (Dennett’s real patterns) the reading adds a contrast: strings of near-maximal sophistication are nearly incompressible, so compressibility and meaningful structure come apart for an individual object. The Sefidgaran papers filed under the same heading (LIT-233, LIT-236) share none of its machinery. No instruction for machine-learning practice.

Backlinks