[39] Let = 12 ... and = 12 ... be two infinite binary sequences. Let = mean that 2i

• [39] Let ω = ω1ω2 ... and ζ = ζ1ζ2 ... be two infinite binary sequences. Let ω ⊕ ζ = η mean that η2i = ωi and η2i+1 = ζi, for all i.

(a) Show that ω ⊕ζ is random in the sense of Martin-L¨of iff ζ is random in Martin-L¨of’s sense and ω is Martin-L¨of random in ζ (that is, given ζ

as an oracle).

(b) Show that ω ⊕ ζ is random in Martin-L¨of’s sense iff K(ω1:n) +

C(ζ1:n) ≥ 2n − O(1).

Comments. Item

(a) is the important van Lambalgen’s theorem. Source:

[M. van Lambalgen, Random Sequences, Ph.D. thesis, University of Amsterdam, 1987; J. Symb. Logic, 52(1987), 725–755]. Source for Item (b):

[J.S. Miller and L. Yu, Advances Math., 226:6(2011), 4816–4840].