Show that ln > l∗(n)− 2 log∗ n for infinitely many n.

(b) Show that log∗ n is unbounded and primitive computable. In particular, show that although log∗ n grows very slowly, it does not grow more slowly than any unbounded primitive computable function.

Comments. Hint: use exercises in Section 1.7. Because log∗ n grows very slowly, we conclude that l

∗(n) is not far from the least asymptotic upper bound on the code-word-length set for all probability sequences on the positive integers. In this sense it plays a similar role for binary prefixcodes as our one-to-one pairing of natural numbers and binary strings in Equation 1.3 plays with respect to arbitrary binary codes. Source: [J.

Rissanen, Ibid.].