[25] Consider the model class of total computable functions of Exercise 5.5.21. (a) Define the structure functions x, hx, x, the sufficient statistic, sufficiency line,

[25] Consider the model class of total computable functions of Exercise 5.5.21.

(a) Define the structure functions βx, hx, λx, the sufficient statistic, sufficiency line, and minimal sufficient statistic for a string x in this setting.

(b) The prefix complexity of the minimal sufficient statistic is called the ‘sophistication’ in Exercise 5.5.21.

Show that there are strings x of length n such that the sophistication is at least n − log n − 2 log log n − O(1).

(c) Let x be a string. Show that at every complexity level i, a total computable function p with K(p) ≤ i such that p

(d) = x with l

(d) minimal is the best model for x in the sense of having minimal randomness deficiency δ(x|p) as in Exercise 5.5.21 (up to O(log n) precision).

(d) Investigate in this setting the relations between the structure functions and the shapes that are possible.

(e) Investigate the computability properties of these structure functions and sophistication.

Comments. Source: [P.M.B. Vit´anyi, IEEE Trans. Inform. Theory, 52:10

(2006), 4617–4626; N.K. Vereshchagin and P.M.B. Vit´anyi, IEEE Trans.

Inform. Theory, 50:12(2004), 3265–3290].