[35] Recall that a sequence is computable iff C(1:n) C(n) + O(1), Example 2.3.4. If is computable, then for all n we

• [35] Recall that a sequence ω is computable iff C(ω1:n) ≤

C(n) + O(1), Example 2.3.4.

If ω is computable, then for all n we have K(ω1:n|n) = O(1) and K(ω1:n) ≤ K(n) + O(1).

(a) Show that if K(ω1:n|n) ≤

c, for some c and all n, then ω is computable.

(b) Show that if K(ω1:n) ≤ K(n) +

c, for some c and all n, then ω is computable in 0

, the Turing degree of the halting problem.

(c) Show that there are incomputable ω’s satisfying K(ω1:n) ≤ K(n)+c, for some c and all n.

(d) Show that for each constant

c, there are at most O(2c) many ω such that for all n, K(ω1:n) ≤ K(n) + c.

Comments. The constants c in Items

(a) through

(c) may depend on ω.
Item

(b) is attributed to G.J. Chaitin, Item

(c) to R.M. Solovay. Source:
[R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished] and personal communication. For Item

(d) and other discussion on this topic, see [D. Zambella, On sequences with simple initial segments, ITLI Tech.
Rept. ML-90-05, Fac. Wiskunde en Informatica, University of Amsterdam, 1990].