[38] Let be an infinite binary sequence that is random with respect to the uniform measure. Let g be a computable function such that

[38] Let ω be an infinite binary sequence that is random with respect to the uniform measure. Let g be a computable function such that the series 

n 2−g(n) diverges, for example, g(n) = log n. Let h be a computable function that is monotone and unbounded, such as h(n) = log log n. Show that for infinitely many n we have K(n) ≥ g(n)

and K(ω1:n) ≤ n + h(n).

Comments. Note that this does not imply that the greatest monotonic nondecreasing lower bound on K(Ω1:n) − n is unbounded. Nonetheless,

this is true. Source: [R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished].