[23] Let 1, 2,... be the effective enumeration of partial computable functions in Section 1.7. Define the uniform complexity of a finite string x of

[23] Let φ1, φ2,... be the effective enumeration of partial computable functions in Section 1.7. Define the uniform complexity of a finite string x of length n with respect to φ (occurring in the above enumeration) as Cφ(x; n) = min{l(p) : φ(m, p) = x1:m for all m ≤ n} if such a p exists, and ∞ otherwise. We can prove an invariance theorem to the effect that there exists a universal partial computable function φ0 such that for all φ there is a constant c such that for all x, n we have Cφ0 (x; n) ≤ Cφ(x; n) +

c. We choose a reference universal function φ0 and define the uniform Kolmogorov complexity as C(x; n) = Cφ0 (x; n).

(a) Show that for all finite binary strings x we have C(x) ≥ C(x; l(x)) ≥

C(x|l(x)) up to additive constants independent of x.

(b) Prove Theorems 2.1.1 to 2.3.3, with C(x) replaced by C(x; l(x)).

(c) Show that in contrast to the measure C(x|l(x)), no constant c exists such that C(x; l(x)) ≤ c for all n-strings (Example 2.2.5).

(d) Show that in contrast to C(x|l(x)), the uniform complexity is monotonic in the prefixes: if m ≤ n, then C(x1:m; m) ≤ C(x1:n; n), for all x.

(e) Show that there exists an infinite binary sequence ω and a constant c such that for infinitely many n, C(ω1:n; n) − C(ω1:n|n) > log n − c.

Comments. Item

(b) shows that the uniform Kolmogorov complexity satisfies the major properties of the plain Kolmogorov complexity. Items (c)

and

(d) show that at least two of the objections to the length-conditional measure C(x|l(x)) do not hold for the uniform complexity C(x; l(x)).

Hint for Item (c): this is implied by the proof of Theorem 2.3.1 and Item

(a). Item

(e) shows as strong a divergence between the measures concerned as one could possibly expect. Source: [D.W. Loveland, Inform.

Contr., 15(1969), 510–526].