[35] (a) Show that for every positive constant c there is a positive constant c such that {1:n : C(1:n; n) n c}{1:n

[35]

(a) Show that for every positive constant c there is a positive constant c such that {ω1:n : C(ω1:n; n) ≥ n − c}⊆{ω1:n :

C(ω1:n|n) ≥ n − c

}.

(b) Use the observation in Item

(a) to show that Theorem 2.5.5 holds for the uniform complexity measure C(·; l(·)).

(c) Show that if f is a computable function and 2−f(n) = ∞, then for all infinite ω we have C(ω1:n; n) ≤ n − f(n) for infinitely many n.

Hence, Theorem 2.5.1 holds for uniform complexity.

Comments. Hint for Item (a): Define the notion of a (universal) uniform test as a special case of Martin-L¨of’s (universal) test. Compare this result with the other exercises to conclude that whereas the uniform complexity tends to be higher in the low-complexity region, the lengthconditional complexity tends to be higher in the high-complexity region.

Source: [D.W. Loveland, Inform. Contr., 15(1969), 510–526].