[23] Let 1 < r, s < ∞ be integers. Show that a real number in the unit interval [0, 1] expressed in r-ary expansion (equivalently, infinite sequence over r letters) is Martin-L¨of random with respect to the uniform distribution in base r iff it is random expressed in s-ary expansion with respect to the uniform distribution in base s.

Comments. Hint: By Exercise 3.1.4 we have for each pair of integers r, s ≥ 2 that |Kr(x) − Ks(x)| ≤ cr,s for all x ∈ N and some constant cr,s independent of x. Use the fact that an infinite binary sequence ω is random with respect to the uniform distribution iff K(ω1:n) ≥ n − c for some constant c and all n, Schnorr’s theorem, Theorem 3.5.1.

(Note: K ≡

K2.) The argument cannot be too trivial, since a total computable 1–1 function f can map ω = ω1ω2 ... to ζ = ω10ω20 ... . Then f −1(ζ) = ω.

But ζ is not random, even if ω is. Source: [C. Calude and H. J¨urgenson, pp. 44–66 in: H. Maurer, J. Karhumaki, and G. Rozenberg, eds., Results and Trends in Theoretical Computer Science, Springer-Verlag, Berlin, 1994]. This result is a special case of the simple and much more general approach of Exercise 4.5.15 on page 334, and is folklore.