[28] Show that the universal distribution m has infinite entropy:

H(m) = 

x m(x) log 1/m(x) = ∞, where the summation is over all x ∈ {0, 1}∗.

Comments. Hint: By the coding theorem, Theorem 4.3.3 on page 275, it suffices to show that 

x 2−K(x)

K(x) = 

n



l(x)=n 2−K(x)

K(x) = ∞.

The exercise follows because there are at least 2n−1 strings x of length n with n − 1 ≤ K(x) ≤ n + 2 log n + O(1).