[41] Consider an infinite binary sequence as a real number r = 0.. Recall that is lower semicomputable if there is a total

[41] Consider an infinite binary sequence ω as a real number r = 0.ω. Recall that ω is lower semicomputable if there is a total computable function f : N→Q such that f(i + 1) ≥ f(i) and limi→∞ f(i) = r. We call ω an Ω-like real number if (i) there is a lower semicomputable function g such that g(n)=0.ω1:n for every n; and (ii)

K(ω1:n) = K(Ω1:n) + O(1). A real number ω is arithmetically random

(with the uniform measure understood) if every arithmetic property of

ω (viewed as an infinite sequence of zeros and ones) holds for some set of reals of uniform measure one. In other words, ω is arithmetically random iff ω does not belong to any arithmetic set of reals of uniform measure zero. Since the arithmetic sets are Borel sets, and the union of countably many Borel sets of uniform measure zero is again a Borel set of uniform measure zero, the set of arithmetically random reals has uniform measure one. Let m(n) be the greatest monotonic lower bound on K(n), that is, m(n) = min{K(x) : x ≥ n}. By the same argument as in the proof of Theorem 2.3.2 on page 127, for any computable function φ(n)
that goes to infinity monotonically with n, we have m(n) < φ(n) from some n onward.

(a) Show that Ω is Ω-like.

(b) Show that Ω-like reals are Martin-L¨of random.

(c) Show that arithmetically random reals are Martin-L¨of random.

(d) Show that since Ω-like reals are Δ0 2 definable, they are not even 2-random in the sense of Exercise 3.5.19, so the set of Ω-like reals has uniform measure zero.

(e) Show that if ω is arithmetically random, then there is a constant c (depending on ω) such that for infinitely many n we have K(ω1:n) ≥
n + K(n) − c.

(f) Show that the ‘then’ property in Item

(e) holds for ω’s that are 2-random in the sense of Exercise 3.5.19.
(g) Show that if ω is Ω-like then K(ω1:n) ≤ n+K(n)−m(n)+O(log m(n)).
(h) Show that if ω is arithmetically random, then K(ω1:n) ≥ n+m(n)+
O(log m(n)).
Comments. Hint for Item (g): compute Ωm(n) effectively from n by doing n steps in the computation of Ω. R.M. Solovay credits this idea to C.P. Schnorr. Source: [R.M. Solovay, Lecture Notes, UCLA, 1975, unpublished]. Source for Item (f): [J.S. Miller, Notre Dame J. Formal Logic, 50:4(2009), 381–391].