[25]

(a) Show that C

(a,

b) = K(a|C

(a, b)) + C(b|a, C

(a, b)) +

O(1).

(b) Show that if a =  then C

(b) = C(b|C(b)) + O(1).

(c) Show that if b =  then C

(a) = K(a|C(a)) + O(1) and this implies C(a|C(a)) = K(a|C(a)) + O(1).

Comments. This governs the additivity for plain Kolmogorov complexity. One can use this to prove that if an infinite sequence ω has infinitely many n such that C(x1:n) ≥ n − c then ω is 2-random obtaining the result of Exercise 3.5.19.

Moreover, for an infinite sequence ω if the right-hand side of the following equation exists then lim infn(n −

K∅

(ω1:n) ≤ lim infn(n − C(ω1:n). For large b this implies C(ab) ≤

C

(a,

b) = K(a|C

(a, b)) + C(b|a, C

(a, b)) ≤ K∅

(a) + l(b). Source: [B.

Bauwens and A.K. Shen, Theor. Comput. Syst., 52:2(2013), 297–302].