• [41] Occam’s razor states that the simplest object has the highest probability. In terms of prefix Kolmogorov complexity this is represented by m(x)=2−K(x)

. This exercise shows that, remarkably, the univeral discrete measure of a finite set is close to univeral discrete measure of the set’s simplest member (ignoring the information in the finite set about the halting problem). Let D ⊂ {0, 1}∗, d(D) < ∞ and m(D) = 

x∈D m(x). The information in x about y is I(x : y) =

K(x) + K(y) − K(x, y) + O(1) = K(x) − K(x|y,K(y)) + O(1). The infinite halting sequence χ is defined by χi = 1 if U(i) < ∞ and χi = 0 otherwise. The information in the set D about the halting sequence is I(D : χ) = K(D) − K(D|χ). Show that min x∈D K(x) = log 1/ max x∈D {m(x)} ≤ log 1/m(D) + I(D : χ)

= min x∈D{I(D : x)} + I(D : χ), where the first equality is up to a constant additive term and the last two (in)equalities are up to logarithmic additive terms of the right-hand side of the (in)equality.

Comments. Source: [L.A. Levin, Ann. Pure Appl. Logic, 167:10(2016), 897–900]. The exercise shows that the universal discrete measure of a set D is at most the maximum universal discrete measure of a member of D.

Their negative logarithms differ by at most D’s information j = I(D : χ)

about the halting sequence χ. Thus, if all x ∈ D have complexity K(x) >

k then D carries at least i bits of information for each x ∈ D where i+j ≈

k. Note that there are no ways (whether natural or artificial) in which we can generate D with significant I(D : χ). The result is an extension of

‘Occam’s razor’ to sets. Occam’s razor states that the simplest member of a set, say x, has the highest universal discrete measure m(x)=2−K(x)

.

While the simplest members of a set each have the highest universal discrete measure m, it may still be negligible compared to the combined discrete measure of the members in the set. The exercise shows, however, that the simplest member (with the least Kolmogorov complexity) has universal discrete measure at least that of the entire set except for the information the latter has about the halting sequence. Hint: The exercise is a follow-up to Exercise 8.1.13 on page 649.