[43] Consider x(i) as a two-argument function as in Example 5.5.12. (a) Show that x(i) is upper semicomputable, but not computable. (b) Show that x

[43] Consider λx(i) as a two-argument function as in Example 5.5.12.

(a) Show that λx(i) is upper semicomputable, but not computable.

(b) Show that λx is not computable, given x, K(x), even in an approximate sense: There is no function λ that is computable given x, K(x), such that λx(i) follows the shape of λ(i) with error at most l(x)/(10 log l(x)), in the sense of Definition 5.5.8 on page 415.

(c) Show that given x, K(x), and i0 such that λx(i0) ≈ K(x), but λx(i)

significantly greater than K(x) for i significantly less than i0 (so that i0 is the complexity of the minimal sufficient statistic), then we can compute λx over all of its domain. This result underlines the significance of the information contained in the minimal sufficient statistic. Formally, there is a constant c ≥ 0 and an algorithm that given any x, k, i0 with K(x) ≤ k ≤ λx(i0) finds a nonincreasing function λ defined on [0, k] such that λx(i) follows the shape of λ with error λx(i0)− K(x) + O(1) on the interval [i0 − i1 + c log k, k], where i1 = min{i : λx(i) ≤ k + c log k}.
Comments. What holds for λx(i) here equally holds for hx(i) and the finite set witnessing its value. Source: [N.K. Vereshchagin and P.M.B.
Vit´anyi, Ibid.]. Item

(c) is attributed to An.A. Muchnik.