[28] Let U be the reference universal prefix machine. The cost of two-way conversion between x and y in the sense of a new distance E5 is defined by E5(x, y) = min{l(p) : U(x, p, r) = y, U(y, p, q) = x}, the minimum taken over all p, q, r such that l(p) + l(q) + l(r) ≤ E(x, y).

This definition separates out r as the extra information for x, and q as the extra information for y.

(a) Show that E5(x, y) = min{K(x|y), K(y|x)}, up to an O(log l(xy))

additive term, which we will ignore.

(b) Show that E5(x, y) does not satisfy the triangle inequality.

(c) Show that E5(x, y) satisfies the density conditions in Equation 8.10 on page 668 only for x’s with K(x) ≥ l(x) + O(1). This is perhaps not a surprise, since the sum distance E4(x, y) is equal to E5(x, y) + E1(x, y).

In the new metric E5, ‘good guys’ (Kolmogorov simple objects) have even more neighbors than in E4.

(d) Show that E5(x, y) = max{K(x), K(y)} − I(x : y).

(e) Define emin(x, y) = min{K(x|y), K(y|x)}/ min{K(x), K(y)}. (Thus, emin(x, y) = E5(x, y)/ min{K(x), K(y)}.) Show that emin(x, y) ≤ e(x, y).

(f) Define e

min(x, y) = E5(x, y)/ min{l(x), l(y)}. Prove the following universality statement: For every computable distance d satisfying the density condition d({y : l(y) = n, d(x, y) ≤ δ ≤ 1}) ≤ 2δn we have e

min(x, y) ≤ d(x, y) + O(1/n) with n = min{l(x), l(y)}.

(g) Show that emin = 1 − (I(x : y) − Δ)/ min{K(x), K(y)} with Δ =

|K(x) − K(y)|.

Comments. In question–answer systems on the Internet distances are measured with partial information; therefore it is unreasonable to require the triangle inequality to hold. Also, popular concepts have a much larger neighborhood and as a consequence the density condition in Exercise 8.3.1 on page 679 may also not hold. Furthermore, between two concepts, there is a large quantity of irrelevant information we may wish to get rid of. The earlier definition of emin deals with this practical situation. Hint: for Item (a), use the proof ideas of Theorem