[27] Let K+(x) be defined as in Example 3.2.2 on page 213. We know that K+(x) = n + K(n) + O(1).

(a) Show that there are infinitely many n, m, x of length n and y of length m with n n + log n + log log n and K+(y) < m + log log m.

(b) Show that K+(x) = max{K(y) : y ≤ x} + O(1), where ≤ is with respect to the integer interpretation of x, y. This implies that K+(x)

is monotonic nondecreasing with increasing x, up to an O(1) additive term.

(c) Show that there is a constant d > 0 such that for all n, there are at least 2n/d strings x of length n such that K(x) = K+(x).

Comment. Item

(b) gives an alternative definition of K+. Note that the monotonicity of K+ in Item

(b) only appears to be at odds with the seemingly fluctuating behavior in item (a). Compare Item

(c) with a similar result for plain Kolmogorov complexity, Exercise 2.2.6 on page 122.
Source: [G.J. Chaitin, Appl. Math. Comput., 59(1993), 97–100].