[19]

(a) Show that there is a constant d > 0 such that for every n there are at least 2n/d strings x of length n with C(x|n) ≥ n and C(x) ≥ n.

(b) Show that there are constants

c, d > 0 such that for every large enough n there are at least 2n/d

 strings x of length n − c ≤ l(x) ≤ n with C(x|n) > n and C(x) > n.

(c) Assume that we have fixed a reference universal Turing machine such that for every n, we have C(x), C(x|n) ≤ n+ 1 for all strings x of length n. Show that in this case Item

(b) holds with l(x) = n.

Comments. Hint for Item (a): There are at most 2n −1 binary programs of length less than n and 2n strings of length n. Hence, there is a string x of length n with C(x|n) ≥ n. Let there be m ≥ 1 such strings. Given m and n we can enumerate all 2n − m strings x of length n and complexity C(x|n) < n by dovetailing the running of all programs of length smaller than n. The lexicographic first string of length n not in the list satisfies log m + O(1) ≥ C(x|n) ≥ n. The unconditional result follows similarly by padding the description of x up to length n. Hint for Item (b): For every n there are equally many strings of length at most n to be described and potential programs of length at most n to describe them. Since some programs do not halt (Lemma 1.7.5 on page 34) for every large enough n, there exists a string x of length at most n that has C(x|n), C(x) > n (and C(x|n), C(x) ≤ l(x) + c). The remaining argument is similar to that of Item (a). Source: [H. Buhrman, T. Jiang, M. Li, and P.M.B.
Vit´anyi, Theoret. Comput. Sci., 235:1(2000), 59–70]. Also reported by M. Kummer and L. Fortnow. Compare with the similar Exercise 3.2.1 for prefix Kolmogorov complexity on page 213. In the source of that exercise, some form of the result of the current exercise is attributed to G.J. Chaitin in the early 1970s.