• [32] Let x, y ∈ {0, 1}∗. There are at least two ways to define the conditional discrete universal distribution m(x|y). We used in Definition 4.3.4 the multiplicative domination of every lower semicomputable discrete semimeasure. In turn, a lower semicomputable discrete semimeasure P(x|y) was defined in Definition 4.3.3 as a lower semicomputable function f(x, y) such that for each fixed y we have 

x f(x, y) ≤ 1.

Another way is to define a conditional discrete universal distribution m
(x|y) according to the Kolmogorov Axioms by m
(x|y) = m(x)/m(y).

(a) Prove Theorem 4.3.2 by construction of the conditional discrete universal distribution.

(b) Show that for every integer n > 0 there is a y with |y| = n such that − log m
(x|y) ≥ K(x|y) + Ω(log n).

(c) Is m(x|y) = m
(x|y)? Or is it larger or smaller?

(d) Show that m
(x|y) is not lower semicomputable.
Comments. Hint for Item (a): a similar construction as for the unconditional discrete universal distribution in the proof of Theorem 4.3.1 while taking into consideration the requirements of the conditional case. Hint for Item (b): use the Kolmogorov Axioms and the symmetry of information. Hint for Item (c): this follows from Item

(b) together with the conditional coding Theorem 4.3.4 on page 278. Hint for Item (d): assume the contrary. We have − log m
(x|y) = K(x)−K(y) by definition (ignoring the constant terms) and by the unconditional coding Theorem 4.3.1.
Moreover, from the contrary assumption follows that − log m
(x|y) is upper semicomputable. Fix x such that K(x) = |x|. Since K(y) is upper semicomputable K(x) − K(y) is lower semicomputable and therefore m
(x|y) is upper semicomputable. Since m
(x|y) is not computable (even for fixed x) it is also not lower semicomputable: contradiction.
Item

(b) shows that the conditional coding Theorem 4.3.4 does not hold for m
(x|y). Source for Items (a),

(b) and (c): [P.M.B. Vit´anyi, Theor.
Comput. Sci., 501(2013), 93–100].