[19] Consider infinite binary sequences with respect to the uniform measure. Show that if f is a computable function and 2f(n) converges rcomputably and

[19] Consider infinite binary sequences ω with respect to the uniform measure. Show that if f is a computable function and 2−f(n)

converges rcomputably and C(ω1:n) ≥ n − c for some constant c and infinitely many n, then C(ω1:n) ≥ n − f(n) for all but finitely many n.

Comments. This formulation establishes a connection between upward and downward oscillations of the complexity of prefixes of almost all

(random) infinite binary sequences. For f we can take f(n) = 2 log n, or f(n) = log n + 2 log log n, and so on. Hint: Combine Theorems 2.5.5 and 2.5.6.

Source: [P. Martin-L¨of, Ibid.].