[28] Let B be a finite nonempty set of basic symbols. Let 0(|) be a universal sequential -test for sequences in B distributed according to

[28] Let B be a finite nonempty set of basic symbols. Let

δ0(ω|μ) be a universal sequential μ-test for sequences in B∞ distributed according to a computable measure μ. Let φ be a monotone function as in Definition 4.5.3 on page 303, that is μ-regular as in Definition 4.5.5.

(a) Show that δ0(ω|μ) ≥ δ0(φ(ω)|μφ) + K(φ).

(b) Show that if μφ is a computable measure, then there exists a μφregular monotone function ψ such that μψφ = μ and δ0(φ(ω)|μφ) ≥

δ0(ω|μ) + K(ψ).

Comments. This generalizes Exercise 3.5.2 on page 229. In particular it shows that a real number has a random binary representation iff it has a random representation in every base r ≥ 2. Note that a sequence is not random in itself, but random with respect to a particular measure. Thus, if we computably transform a sequence, then its randomness properties and the complexities of its initial segments are preserved up to an additive constant with respect to the transformed measure. Source:

[L.A. Levin, Problems Inform. Transmission, 10:3(1974), 206–210; Inform. Contr., 61(1984), 15–37].