[23] Assume the terminology in Exercise 6.8.7. Consider defined in the proof for Item (ii) of Barzdinss lemma, Theorem 2.7.2. Essentially, i = 1

[23] Assume the terminology in Exercise 6.8.7.

Consider χ defined in the proof for Item (ii) of Barzdins’s lemma, Theorem 2.7.2.

Essentially, χi = 1 if the ith bit of U(i) < ∞ is 0, and χi = 0 otherwise.

Here U is the reference universal Turing machine of Theorem2.1.1.

Let A be the language with χ as its characteristic sequence.

(a) Show that A is a computably enumerable set and its characteristic sequence satisfies C(χ1:n) ≥ log n, for all n.

(b) Let χ be as in Item (a). Define a sequence h by h = χ102χ2022 ...χi02i χi+1 ... .
Prove that C(h1:n) = O(C(n)) + Θ(log log n). Therefore, if h is the characteristic sequence of a set B, then B is not computable, but more sparsely incomputable, as is A.
Comments. Item

(a) follows from the proof of Barzdins’s lemma, Theorem 2.7.2.

Source: [J.M. Barzdins, Soviet. Math. Dokl., 9(1968), 1251–

1254; D.W. Loveland, Proc. 1st ACM Symp. Theory Comput., 1969, pp.

61–66].