[33] (a) Show that there exists an infinite binary sequence that is random with respect to the uniform measure, but for each constant c

[33]

(a) Show that there exists an infinite binary sequence ω

that is random with respect to the uniform measure, but for each constant c there are only finitely many n such that C(ω1:n|n) > n − c (the condition of Theorem 2.5.6 does not hold).

(b) Show that there exists an infinite binary sequence ω satisfying (i)
C(ω1:n) > n − f(n) from some n onward and 2−f(n) converges computably (the condition in Theorem 2.5.5 holds), and (ii) ω is not random with respect to the uniform measure.
Comments. Thus, each containment in the nested sequence of sets of infinite binary sequences that satisfy the condition in Theorem 2.5.5, randomness according to Martin-L¨of, and the condition in Theorem 2.5.6, as in Figure 2.5, is proper. Source: [C.P. Schnorr, Math. Systems Theory, 5(1971), 246–258].