[44] Show that every infinite sequence is Turing-reducible (Exercise 1.7.16 on page 43, with sets replaced by characteristic sequences of sets) to an infinite sequence that is Martin-L¨of random with respect to the uniform measure.

Comments. C.H. Bennett raised the question whether every infinite binary sequence can be obtained from an incompressible one by a Turing machine. He proved this for a special case. Philosophically, the result implied in the exercise allows us to view even very pathological sequencesproperty that the series 

i λ(Ai) < ∞ converges, ω is contained in only finitely many Ai. Show that for the ω’s defined this way, the Solovay random sequences are precisely the infinite binary sequences that are random in the sense of Martin-L¨of with respect to the uniform measure.

Comments. In Martin-L¨of’s definition of randomness (with respect to the uniform measure) of infinite binary sequences, he required that

λ(Ai) ≤ 2−i

. That definition is equivalent to stipulating the existence of some regulator of convergence f(i) → ∞ that is computable and nondecreasing such that λ(Ai) ≤ 2−f(i)

. Solovay’s definition has the advantage that it does not require such a regulator. Source: [R.M. Solovay, Lecture Notes, 1975, unpublished; G.J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987; A. K. Shen, Soviet Math. Dokl., 38:2(1989), 316–319].