[19] The probability that the universal prefix machine U halts on self-delimiting binary input p, randomly supplied by tosses of a fair coin, is Ω (0 < Ω < 1). Let v1, v2,... be an effective enumeration without repetitions of Σ∗. Define L ⊆ Σ∗ such that vi ∈ L iff Ωi = 1. Section 3.5.2 implies that K(Ω1:n) ≥ n for all but finitely many n. Show that L and its complement are not computably enumerable.

Comments. It can be proved that L ∈ Δ0 2 −(Σ0 1

 Π0 1), in the arithmetic hierarchy. See Section 3.5.2, page 226, and Exercise 1.7.21, page 46.