[32] We study the statistics of description length. By the coding theorem, Theorem 4.3.3, we have K(x) = log 1/QU(x) up to an additive constant. Informally, if an object has many long descriptions, then it also has a short one.

(a) Let f(x, n) be the number of binary strings p of length n with U(p) =

x, where U is the reference prefix machine of Theorem 3.1.1, page 206.

Show that for all n ≥ K(x), we have log f(x, n) = n − K(x, n) + O(1).

(b) Use Item

(a) to show that log f(x, K(x)) = K(x) − K(x, K(x)) +

O(1) = O(1). The number of shortest programs of any object is bounded by a universal constant.

Comments. Hint: In Item (b), use K(x) ≤ K(x, n) + O(1); substitute n = K(x) in the expression in Item

(a) to obtain log f(x, K(x)) =

K(x) − K(x, K(x)) + O(1) ≤ O(1). Source: [P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987].