• [31] We can derive K(x) in another way. Define a complexity function F(x) to be a function on the natural numbers with the property that the series 2−F (x) ≤ 1 and such that F(x) is upper semicomputable. That is, the set {(m, x) : F(x) ≤ m} is computably enumerable. (If F(x) = ∞, then 2−F (x) = 0.)

(a) Show that the number of x’s for which F(x) ≤ m is at most 2m.

(b) Show that there is an additively optimal (minimal) complexity F such that for each complexity F there is a constant c depending only on F and F but not on x such that F(x) ≤ F

(x) +

c. This is the invariance theorem corresponding to Theorem 3.1.1.

(c) Show that F(x) = K(x)+O(1), where F(x) is the optimal complexity in Item (b).

Comments. Hint for Item (b): Define F(x) = mink{1, Fk(x) + k}, where Fk is the complexity resulting from the kth partial computable function after modifying it to satisfy the requirements above. This approach has been proposed by L.A. Levin in a sequence of papers: [Russ. Math.

Surv., 25:6(1970), 83–124, Sov. Math. Dokl., 14(1973), 1413–1416, and Problems Inform. Transmission, 10(1974), 206–210 (where the equivalence with the prefix machine approach is established)]. See also [P. G´acs, Sov. Math. Dokl., 15(1974), 1477–1480]. G.J. Chaitin [J. Assoc. Comp.

Mach., 22(1975), 329–340] used the prefix machine approach to define K(x) but gave a different interpretation to the conditional complexity, resulting in the Kc version in Example 3.8.2 and Exercise 3.9.3.