[26] Let A N be a computably enumerable set, and let = 12 ... be its characteristic sequence. We use the uniform complexity

• [26] Let A ⊆ N be a computably enumerable set, and let χ =

χ1χ2 ... be its characteristic sequence. We use the uniform complexity C(χ1:n; n) of Exercise 2.3.2 on page 130.

(a) Show that C(χ1:n; n) ≤ log n + O(1) for all A and n.

(b) Show that there exists an A such that C(χ1:n; n) ≥ log n for all n.

Comments. This implies Theorem 2.7.2.

It is the original Barzdins’s lemma. Source: [J.M. Barzdins, Soviet Math. Dokl., 9(1968), 1251–1254].