[39] We improve on Exercise 3.5.3, Item (b). As usual, n∗ denotes the shortest program for n, and if there is more than one, then the first one in standard enumeration. Let f be a function.

(a) Show that if 

n 2−f(n)−K(f(n)|n∗) < ∞, then K(ω1:n) ≥ n+K(n)−

f(n) for all but finitely many n, for almost every ω ∈ {0, 1}∞.

(b) Show that if 

n 2−f(n)−K(f(n)|n∗) = ∞, then K(ω1:n) < n+K(n)−

f(n) for infinitely many n, for almost every ω ∈ {0, 1}∞.

(c) Show that if f is computable and 

n 2−f(n) = ∞, then K(ω1:n) <

n + K(n) − f(n) for infinitely many n, for every ω ∈ {0, 1}∞.

(d) Show that there is a function f such that 

n 2−f(n)−K(f(n)|n∗) < ∞

but 

n 2−f(n) = ∞.

(e) Show that there is a function f with 

n 2−f(n) = ∞ but K(ω1:n) ≥

n+K(n)−f(n) for all but finitely many n, for almost every ω ∈ {0, 1}∞.

(f) If 

n 2−f(n) < ∞ then there exist infinitely many n such that K(ω1:n) < n + f(n), for almost every ω ∈ {0, 1}∞.

Comments. This gives a necessary and sufficient condition on the downward oscillations of a function f to ensure that for almost all ω the complexity K(ω1:n) drops below n + K(n) − f(n) infinitely often. Source:

[J.S. Miller and L. Yu, Ibid.].