Item

(e) means that in contrast to the differences between the measures C(·; l(·)) and C(·|l(·))

exposed by the contrast between Items

(c) and (d), Item

(b) holds also for C(·|l(·)). Items

(f) and (g) show a complexity gap, because C(n) can be much lower than l(n). Hint for Item (h): use Item (d). Source for Items

(b) through (e), and (h): [D.W. Loveland, Inform. Contr., 15(1969), 510–526]. Loveland attributes Item

(e) to A.R. Meyer. The equivalence between bounded length-conditional complexity and bounded uniform complexity for prefixes of infinite strings is stated by A.K. Zvonkin and L.A. Levin in [Russ. Math. Surv., 25:6(1970), 83–124]. Source for Items

(f) and (g); [G.J. Chaitin, Theoret. Comput. Sci., 2(1976), 45–48]. For the prefix complexity K introduced in Chapter 3, there are incomputable

ω such that K(ω1:n) ≤ K(n)+O(1) for all n by a result of R.M. Solovay in Exercise 3.5.9 on page 232.