[37] What is the difference between semimeasure M and any (not necessarily lower semicomputable) measure ? (a) Show that 1/M(x) differs from 1/(x), for infinitely

• [37] What is the difference between semimeasure M and any

(not necessarily lower semicomputable) measure μ?

(a) Show that 1/M(x) differs from 1/μ(x), for infinitely many x, as the busy beaver function BB(n) differs from n (Exercise 1.7.19 on page 45)

for every measure μ.

(b) Show the same about M(x) versus M(x0) + M(x1).

Comments. This shows that the normalization Mnorm must distort the measure M. Exercise 4.5.7 shows that this is rare. Hint: take the maximal running time T (k) of those among the first k programs that halt.

Note that T (k) is the longest running time of a halting program among the first k programs and is related to BB(k). The following procedure effectively generates the desired x from k (even though T is only lower semicomputable) such that M(x0) + M(x1) < 1/T (k). Start with the empty prefix y =  of x. Find its extension y = y0 or y = y1 (whichever you find first) such that M(y

) > 1/(2T (k)). Extend y to differ from y

.

Repeat as long as you can (up to 2T (k) times). The resulting string x (of length < 2T (k)) will have both extensions of M-semimeasure

< 1/(2T (k)). Since x is described by k and an O(1) program, for large enough random k we have 1/k2 ≤ M(x). See also ‘History and References,’ Section 4.7. Source: One of us (PV) asked L.A. Levin; Levin asked R.M. Solovay, and returned Solovay’s solution on September 12, 1989, by e-mail.