[18] Define the function complexity of a function f : N→N , restricted to a finite domain D, as C(f|D) = min{l(p) : ∀x∈D[U(p, x) = f(x)]}.

(a) Show that for all computable functions

f, there exists a constant cf such that for all finite D ⊆ N , we have C(f|D) ≤ cf .

(b) Show that for all partial computable functions, for all D = {i : i ≤
n}, we have C(f|D) ≤ log n + cf , where cf depends on f but not on D.
Comments. Compare Theorem 2.7.2.

Source: [J.M. Barzdins, Soviet Math.

Dokl., 9(1968), 1251–1254].