[37] An infinite binary sequence is n-random if it is MartinLof random in n1. That is, 1-randomness is Martin-Lof randomness. Show that =

[37] An infinite binary sequence ω is n-random if it is MartinL¨of random in ∅n−1. That is, 1-randomness is Martin-L¨of randomness.

Show that ω = ω1ω2 ... is 2-random iff C(ω1:n) ≥ n − O(1) for infinitely many n.

Comments. This interprets and explains Theorem 2.5.6 on page 154.

Some authors call ω satisfying C(ω1:n) ≥ n − O(1) for infinitely many n Kolmogorov random. This definition was essentially proposed by [D.W.

Loveland, Proc. ACM 1st Symp. Theory Comput., 1969, 61–65], using uniform Kolmogorov complexity in the definition. That definition is robust enough that uniform, length-conditional, and plain Kolmogorov complexity all give the same class. Source for the ‘if’ side: [L. Yu, D.

Ding, and R.G. Downey, Ann. Pure Appl. Logic, 129:1-3(2004), 163–180]
analyzed an argument of [R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished] to show that all 3-random reals are Kolmogorov random;
source for the ‘only if’ side: [J.S. Miller, J. Symbol. Logic, 69(2004), 907–
913]. Independently, the full ‘iff’ statement was proved in [A. Nies, F.
Stephan, and S.A. Terwijn, J. Symbol. Logic, 70:2(2005), 515–535].