[27] Prove Corollary 2.5.3 rigorously: = 12 ... is random in the sense of Martin-Lof with respect to the uniform measure iff there exists

• [27] Prove Corollary 2.5.3 rigorously: ω = ω1ω2 ... is random in the sense of Martin-L¨of with respect to the uniform measure iff there exists a constant c such that C(ω1:n|n) ≥ n − K(n) − c for all n.

Comments. Source: [P. G´acs, Z. Math. Logik Grundl. Math., 26(1980), 385–394], Corollary 5.4. Hint: Use that f is computable, K is the smallest upper semicomputable function, and 

n 2−f(n),



n 2K(n) < ∞.