• [27] Construct an example of candidate explanations (p0, S0)

and (p1, S1) for data x, with pi a program computing set Si x (i =

0, 1), such that (i) the two-part MDL codes satisfy l(p1) + log d(S1) <

l(p0) + log d(S0) − c log n (c a fixed constant); and (ii) the randomness deficiencies satisfy δ(x|S1) > δ(x|S0).

Comments. The example shows that shorter MDL code does not necessarily mean a better model. The situation is thus as follows: (i) By Theorem 5.5.1 on page 416 the process of finding shorter and shorter MDL codes will in the limit give us the approximately best-fitting model; (ii)

since λx is upper semicomputable, but not computable, we cannot know when we are close to the limit; and (iii) during the approximation process the randomness deficiency of the candidate models may fluctuate wildly. Compare Lemma 5.5.4 on page 424. Hence, premature termination may result in a worse-fitting model than some models that preceded the terminal one. Source: [P. Adriaans and P.M.B. Vit´anyi, Ibid.].