[27] Far from being a nuisance, the complexity oscillations actually enable us to discern a fine structure in the theory of random sequences. A sequence ω is Δ0 2 definable if the set {n : ωn = 1} is Δ0 2 definable, Exercise 1.7.21 on page 46. We consider infinite binary sequences that are Δ0 2 definable (such as the halting probability Ω, Section 3.5.2).

(a) Show that if ω is Δ0 2 definable, then limn→∞ n − K(ω1:n|n) = ∞.

(This is, of course, interesting only for random ω’s.)

(b) Show that if ω is Δ0 2 definable, then limn→∞ n+K(n)−K(ω1:n) = ∞.

(c) Show that if there is a constant c such that for infinitely many n we have n + K(n) − K(ω1:n) ≤

c, then ω is not Δ0 2 definable. That is, if such an ω is random, then it is not a simply definable random sequence.
Comments. Hint for Item (b): use Item (a). Items

(a) and

(b) delimit the upswing of the complexity oscillations for Δ0 2 definable ω. Hint for Item (c): use Exercise 3.5.3.

The Δ0 2 definable random sequences are rather atypical random sequences. (An example is the halting probability Ω.)

The K-complexity allows us to distinguish between easily definable random sequences and those that are not so easily definable. Source: [M. van Lambalgen Random Sequences, Ph.D. thesis, University of Amsterdam, 1987; J. Symb. Logic, 54(1989), 1389–1400].