[41] Let U0, U1,..., Uk ⊆ {0, 1}∞ for all k ≥ 0 denote a sequential universal Martin-L¨of test as in Section 2.5.2.

Let λ denote the uniform measure on {0, 1}∞. Note that U0 = {0, 1}∞ by definition and

λ(U0) = 1. Lower semicomputable reals are defined in Exercise 3.5.15.

A sequence r1, r2,... of reals is uniformly lower semicomputable if there is a total computable function f(k, i) such that for every k ≥ 1, we have f(k, i + 1) ≥ f(k, i) for all i and limi→∞ f(k, i) = rk.

(a) Show that for every sequential universal Martin-L¨of test U0, U1,..., the uniform measure λ(Uk) is a Martin-L¨of random real.

(b) Show that for every lower semicomputable Martin-L¨of random real r



, there is a sequential universal Martin-L¨of test U0, U1,... such that ∞

k=1 λ(Uk) equals r.

(c) Let r1, r2,... be a uniformly lower semicomputable sequence of reals such that rn ≤ 1/2n for every n ≥ 1, and let λ be the uniform measure on {0, 1}∞. Show that rk is a Martin-L¨of random real for every k ≥ 1 iff there is a universal sequential Martin-L¨of randomness test U0, U1,...

with λ(Uk) = rk for every k ≥ 1.

Comments. In this way, the measure-theoretic treatment of randomness in Martin-L¨of’s sense provides a second characterization of natural examples of Martin-L¨of random sequences (or reals) that are lower semicomputable. In fact, it is a curious connection between infinite binary sequences that are members of the complement of the universal constructive null set, Section 2.5.2, and the binary expansions of the real numbers that are uniform measures of the constituent elements of a universal sequential Martin-L¨of test, which elements themselves have infinite binary sequences as members. Source for Items

(a) and (b): [A.

Kuˇcera and T.A. Slaman, Ibid.] (according to R.G. Downey, Item

(a) is due to A. Kuˇcera alone). Source for Item (c): (only if side) [A. Kuˇcera and T.A. Slaman, Ibid.]; (if side) [W. Merkle, N. Mihailovic and T.A.

Slaman, Theor. Comput. Syst., 39(2006), 707–721].