[35] We have characterized the regular languages using Kolmogorov complexity. It is immediately obvious how to characterize computable languages in terms of Kolmogorov complexity. If L ⊆ Σ∗ and

Σ∗ = {v1, v2,...} is an effective enumeration, then we define the characteristic sequence χ = χ1χ2 ... of L by χi = 1 if vi ∈ L and χi = 0 otherwise. A language L is computable if χ is a computable sequence.

(a) If a set L ⊆ Σ∗ is computable then there exists a constant cL (depending only on L) such that for all n, we have C(χ1:n|n) < cL.

(b) If L is computably enumerable, then there is a constant cL such that for all n, we have C(χ1:n|n) ≤ log n + cL.

(c) There exists a computably enumerable set L such that C(χ1:n) >

log n, for all n.

Comments. Item

(a) is straightforward. Its converse is hard: see the text preceding the proof of Claim 6.8.1 on page 502. This converse is given by Item

(e) of Exercise 2.3.4 on page 131. Items

(b) and

(c) are Barzdins’s lemma, Theorem 2.7.2, restated. It quantitatively characterizes all computably enumerable languages in terms of Kolmogorov complexity. Hint for Item (c): Exercise 2.3.4.

With L as in Item (c), Σ∗ − L also satisfies Item (b), so Item

(b) cannot be extended to a Kolmogorov complexity characterization of computably enumerable sets.