• [46] How are K and C precisely related? Is K just a pumpedup C-version? The following formulas relate C and K:

(a) Show that K(x) = C(x) + C(C(x)) + O(C(C(C(x)))).

(b) Show that C(x) = K(x) − K(K(x)) − O(K(K(K(x)))).

(c) Show that C(C(x)) − K(K(x)) = O(K(K(K(x)))).

(d) Show that K(K(K(x))) ∼ C(C(C(x))).

Comments. Clearly, we can replace C(C(x)) by K(C(x)) in the equality of Item (a). Granted Items

(c) and (d), it follows that Items

(a) and (b)

are equivalent. These formulas express the number of extra bits needed to convert a minimal-length program for the reference machine for Ccomplexity into a minimal-length program for the reference machine of K-complexity. Source: [R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished], and quoted in [R.M. Solovay, Non-Classical Logics, Model Theory and Computability, A.I. Aruda, N.C.A. da Costa and R. Chaqui, eds., North-Holland, 1977, 283–307].