[12]

(a) Show that C(x + C(x)) ≤ C(x) + O(1).

(b) Show that if m ≤ n, then m + C(m) ≤ n + C(n) + O(1).

Comments. Hint for Item (a): if U(p) = x with l(p) = C(x), then p also suffices to reconstruct x + l(p). Hint for Item (b): use Item (a). Source:

[P. G´acs, Ibid.], result attributed to C.P. Schnorr.