[35] Let be an infinite binary string. We call computable if there exists a computable function such that (i) = i for

• [35] Let ω be an infinite binary string. We call ω computable if there exists a computable function φ such that φ(i) = ωi for all i > 0.

Prove the following:

(a) If ω is computable, then there is a constant c such that for all n, C(ω1:n; n) < c, C(ω1:n|n) < c, C(ω1:n) − C(n) < c.

This is easy. The converses also hold but are less easy to show. They follow from Items (b), (e), and (f).

(b) For each constant

c, there are only finitely many ω such that for all n, C(ω1:n; n) ≤

c, and each such ω is computable.

(c) For each constant

c, there are only finitely many ω such that for infinitely many n, C(ω1:n; n) ≤

c, and each such ω is computable.

(d) There exists a constant c such that the set of infinite ω that satisfy C(ω1:n|n) ≤ c for infinitely many n, has the cardinality of the continuum.

(e) For each constant

c, there are only finitely many ω such that for all n, C(ω1:n|n) ≤

c, and each such ω is computable.

(f) For each constant

c, there are only finitely many ω with C(ω1:n) ≤

C(n) + c for all n, and each such ω is computable.

(g) For each constant

c, there are only finitely many ω with C(ω1:n) ≤

l(n) + c for all n, and each such ω is computable.

(h) There exist incomputable ω for which there exists a constant c such that C(ω1:n) ≤ C(n) + c for infinitely many n.
Comments. Clearly Item

(c) implies Item (b). In Item

(d) conclude that not all such ω are computable. In particular, the analogue of Item (c)
for C(ω1:n|n) does not hold. Namely, there exist incomputable ω for which there exists a constant c such that for infinitely many n we have C(ω1:n|n) ≤

c. Hint for Item (d): Exhibit an one-to-one coding of subsets of N into the set of infinite binary strings of which infinitely many prefixes are n-strings—in the sense of Example