Information as Description Length: Boltzmann, Shannon, Kolmogorov

A pedagogical unification showing that Boltzmann entropy, Shannon entropy, and Kolmogorov complexity are all the same idea wearing different clothes: information is the length of the shortest correct description of a state.

The core intuition is simple. You have a system that could be in many possible configurations (microstates). A macrostate is whatever partial description you have — "there are 5 pieces on the board," or "each pixel is on with probability 0.001," or "this image contains a cat." Entropy is then just the average number of bits you still need to pin down the exact microstate, given that partial description. The paper's contribution is to show that Boltzmann, Shannon, and Kolmogorov are not three separate theories — they are the same two-step recipe (describe the model, then index the residual) applied under increasingly powerful rules about what counts as a valid description.

The hierarchy works like this. Boltzmann/Hartley: you know nothing except that the microstate lives in a set of W equally likely possibilities. Cost: log₂ W bits, a flat index. Shannon: you know a probability distribution P over microstates. Now you can use variable-length codes — short codewords for likely outcomes, long ones for rare ones — and the optimal average cost drops to H(P) = −∑ P(x) log₂ P(x). Kolmogorov: you drop the probabilistic assumption entirely and ask for the shortest program that produces the specific object x. A two-part code — first describe a computable model M that captures the structure, then index x within M — gives K(x) ≈ min_M { K(M) − log₂ P_M(x) }. This recovers Hartley when P_M is uniform and Shannon in expectation when P is fixed.

The paper then adds a fourth level the authors call "formal/logical" description, parameterized by a formal language L and background theory T. The model cost becomes R_{L,T}(M), the length of the shortest L-formula that, relative to T, picks out exactly the macrostate M. This is strictly more expressive than Kolmogorov complexity: a short formula can specify an uncomputable target (like Chaitin's Ω or Busy Beaver values) without inflating the syntactic model cost. The two-part description length becomes L_formal(x; M) = R_{L,T}(M) + [−log₂ P_M(x)] + O(1), and all the classical cases fall out as special instances by choosing L and T appropriately. The paper cites a 2025 result by Jaakkola, Kuusisto, and Vilander explicitly connecting logical description complexity to Boltzmann/Shannon entropy as empirical support for this unification.

The worked examples are the clearest part of the paper. A sparse binary image where each pixel is on with probability p = 0.001 illustrates why knowing the distribution is powerful: instead of sending all N bits, you send where the rare "on" pixels are, costing roughly N·H₂(p) ≈ 0.011·N bits on average — about 90× compression. The "cat image" example then shows the Kolmogorov step: a computable generative model for cat images can compress far below what any fixed probability distribution would achieve, by exploiting learned structure. The paper is explicitly pedagogical in intent — it is a draft working note, not a research result — but the formal/logical extension and the unified two-part framework are the non-obvious contribution.