[20] Define Chaitin’s conditional complexity as in Example 3.8.2 by Kc(x|y) = K(x|y∗) with y∗ = y,K(y) , or y∗ is the first enumerated shortest program for y. When there is more than one object in the conditional then define Kc(x|y, z) := Kc(x|y, z ) := K(x|y, z ∗), and so on. Define Kc(x) = K(x) and Kc(x, y) = K(x, y ) = K(x, y). Prove the following identities (up to an additive constant):

(a) Kc(x, y) = Kc(y, x).

(b) Kc(x|x) = 0.

(c) Kc(Kc(x)|x) = 0. (Contrast this with Theorem 3.7.1.)

(d) Kc(x) ≤ Kc(x, y).

(e) Kc(x|y) ≤ Kc(x).

(f) Kc(x, y) = Kc(x)+Kc(y|x). (Contrast this with the case for K(x, y), Theorem 3.8.1.)

(g) We have defined I(x; y) = Kc(x) − Kc(x|y). Show that I(x; y) ≥ 0, I(x; x) = Kc(x), and I(; x) = I(x; ) = 0.

(h) I(x; y) = Kc(x) +Kc(y)−Kc(x, y) +O(1) = I(y; x) +O(1). (In fact, I(x; y) is the symmetric quantity of mutual information of objects x and y; see Definition 3.8.2.)

(i) Kc(x, Kc(x)) = Kc(x). (Hint: use

(f) and (c). Contrast this derivation with the identical but differently formulated Equation 3.10.)

(j) Kc(x, y) = Kc(x, y, Kc(x), Kc(y|x)).

(k) Kc(Kc(x), Kc(y|x)|x, y) = 0.

(l) Kc(Kc(x), Kc(y), Kc(y|x), Kc(x|y), Kc(x, y)|x, y) = 0.

(m) Kc(I(x; y)|x, y) = 0.

(n) Kc(x) ≤ Kc(x|y) + Kc(y|z) + Kc(z).

(o) Kc(x, y, z) = Kc(x|y, z) + Kc(y|z) + Kc(z).

(p) Show that Kc(x|y) is not upper semicomputable. (Hint: use Theorem 3.7.1.) This contrasts with K(x|y), which is upper semicomputable.

Comments. See also Example 3.8.2 in Section 3.8.1.

Essentially, we have now at our disposal the entire calculus of information theory. In fact, the Kc calculus is somewhat richer, since it contains rules like Items

(c) and

(i) that have no counterpart in classical information theory. Note that the difference between K and Kc is the conditional form K(x|y) versus Kc(x|y). Kc complexity was introduced by G.J. Chaitin in [J. Assoc.
Comp. Mach. 22(1975), 329–340], and a more recent expos´e appears in [Algorithmic Information Theory, Cambridge Univ. Press, 1987].