[32] Let P be a (possibly incomputable) probability mass function.

(a) Show that 0 ≤ 

x P(x)K(x|P)−H(P) = O(1), where the O(1) term is independent of P and depends only on the reference prefix machine.

(b) Show that 0 ≤ 

x P(x)K(x|P)−H(P) < 1 for all P for some appropriate reference prefix machine. This achieves exactly the optimum expected code-word length of the noiseless coding theorem, Theorem 1.11.2 on page 77.

Comments. Hint: In Item

(a) use a universal prefix machine with an oracle for (x, P(x)) pairs. With an O(1) program to compute a Shannon–

Fano code, this machine when given an input y determines whether y is the Shannon–Fano code word for some x. By Lemma 4.3.3 on page 276 such a code word has length log 1/P(x) + O(1). If this is the case, then the machine outputs x; otherwise, it halts without output. Therefore, K(x|P) ≤ log 1/P(x) + O(1). This establishes the upper bound. The lower bound follows as usual from the noiseless coding theorem, Theorem