[31] Let be an infinite binary sequence. Show that if there exists a constant c such that K(1:n) n c for all

[31] Let ω be an infinite binary sequence. Show that if there exists a constant c such that K(ω1:n) ≥ n − c for all n, then for all k we have K(ω1:n) − n ≥ k from some n onward.

Comments. Hint: This follows easily from Exercise 3.5.4 Item (a), and can be seen as a strengthening of that result. Not only is the limit of K(ω1:n)−n infinite when ω is Martin-L¨of random, but it goes to infinity fast enough to make the series in Exercise 3.5.4, Item (a), diverge. In Schnorr’s theorem, Theorem 3.5.1, we showed that an infinite binary sequence is random with respect to the uniform measure iff K(ω1:n) ≥ n−c for some c and all but finitely many n. There is not only a sharp dividing line but a wide complexity gap that separates the random infinite sequences from the nonrandom infinite sequences. With respect to the uniform measure, we have in Exercise 2.5.10 defined the notion of a Solovay test for randomness, and shown that a sequence ω is Martin-L¨of random iff it is Solovay random. Call ω weakly Chaitin random if there is a constant c such that for all n, we have K(ω1:n) ≥ n −

c. The results referred to and this exercise show that the sets of infinite sequences defined by all of these definitions coincide precisely. That different points of departure attempting to formalize an intuitive notion (like randomness)

turn out to define the same objects is commonly viewed as evidence that the formalization correctly represents our intuition. Source: [G.J.

Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987], attributed to C.P. Schnorr.