[29] Let be an infinite binary sequence that is Martin-Lof random with respect to the uniform measure (for example, the halting probability of

[29] Let ω be an infinite binary sequence that is Martin-L¨of random with respect to the uniform measure (for example, the halting probability Ω of Section 3.5.2).

(a) Show that ω is von Mises–Wald–Church random (Section 1.9).

(b) Show that ω is effectively unpredictable. That is, let f be a computable function that given an arbitrary finite binary string predicts

“the next bit is one,” “the next bit is zero,” or “no prediction.” Then if f predicts infinitely many bits of ω, it does no better than chance because in the limit the relative frequency of both correct predictions and incorrect predictions is 1 2 .

(c) Use Item

(b) to show that the zeros and ones have limiting relative frequency 1 2 .

(d) Show that ω is normal in base two in the sense of Borel: each of the 2k possible blocks of k bits in ω has limiting relative frequency 1/2k.

(e) Show that the law of the iterated logarithm, Exercise 1.10.5 on page 65, applies to the relative frequency of correct and incorrect predictions of bits of ω.

Comments. Hint for Item (c): predict the next bit of ω by a total computable function that always has value one. Source: [G.J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987].