[15] Let (x, y) be a computable function. (a) Show that K((x, y)) K(x) + K(y) + c, where c is a constant depending

[15] Let φ(x, y) be a computable function.

(a) Show that K(φ(x, y)) ≤ K(x) + K(y) + cφ, where cφ is a constant depending only on φ.

(b) Show that

(a) does not hold for C-complexity.

Comments. Hint: In Item

(b) use the fact that the logarithmic error term in Theorem 2.8.2, page 192, cannot be improved.