• [25]

(a) Show that if we recode data x by its shortest program x∗, then this can change the structure functions.

(b) Let f be a computable permutation of the set of strings (one-to-one, total, and onto). Show that the graph of hf(x) follows the shape of hx with error at most K

(f) + O(1).

Comments. If the structure functions could change under common recodings of the data, clearly our claim that the structure functions represent the stochastic properties of the data would be false: One doesn’t believe that those properties change under common recoding. Hint for Item (a):

since x∗ is incompressible, it is a typical element of the set of all strings of length l(x∗) = K(x), and hence hx∗ (i) drops to the sufficiency line Lx(i) = K(x) − i already for some i ≤ K(K(x)), so almost immediately

(and it stays within logarithmic distance of that line henceforth). That is, ignoring logarithmic additive terms, hx∗ (i) +i = K(x) irrespective of the (possibly quite different) shape of hx. Since the Kolmogorov complexity function K(x) = l(x∗) is not computable, the recoding function f(x) = x∗ is also not computable. Moreover, while f is one-to-one and total, it is not onto. However, the structure function is invariant under

‘proper’ recoding of the data as in Item (b). Source: [N.K. Vereshchagin and P.M.B. Vit´anyi, Ibid.]. Item

(a) was first observed by O. Watanabe.