[36]

(a) Use the notation of Exercise 3.3.1.

Show that there are infinitely many x such that if K(x) = K+(x), then C(x) = C+(x).

(b) Show that for some constant c ≥ 0 there exist infinitely many x

(l(x) = n) with C(x) ≥ n − c and K(x) ≤ n + K(n) − log2 n + c log3 n.

(c) Show that for some constant c ≥ 0 and every n there are strings x of length n with C(x) ≥ n − c and K(x) ≤ n + K(n) − K(K(n)|n)) +

3K(K(K(n)|n)|n)) +

c. Show first that K(K(n)|n) = log2 n + O(1).

Comments. Source for Items

(a) and (b): [R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished]. Source for Item (c): [B. Bauwens and A.K.

Shen, J. Symbol. Logic, 79:2(2014), 620–632].