• [42] Does a similar result to that in Exercise 3.5.19 hold for prefix complexity? We know that the maximal complexity of K(x) is K+(x) = l(x) + K(l(x)) + O(1), Example 3.2.2 on page 213. Moreover, if K(x) = K+(x) is maximal then C(x) = C+(x) by Exercise 3.3.4 on page 218. An infinite binary sequence ω is called strongly Chaitin random if K(ω1:n) ≥ n + K(n) − O(1) for infinitely many n.

(a) Show that every strongly Chaitin random infinite binary sequence is 2-random.

(b) Show that every 2-random infinite binary sequence is strongly Chaitin random.

Comments. Hint for Item (a): use Exercises 3.5.19 and  3.3.4.

Source for item (a): [R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished].

Source for Item (b): [J.S. Miller, Notre Dame J. Formal Logic, 50:4(2009), 381–391].