[21] Let A be an infinite computably enumerable set of natural numbers. Show that if we define = nA 2K(n), then K(1:n)

[21] Let A be an infinite computably enumerable set of natural numbers. Show that if we define θ = 

n∈A 2−K(n), then K(θ1:n) ≥

n − O(1) for all n. (Therefore, θ is a random infinite sequence in the sense of Martin-L¨of by Schnorr’s theorem, Theorem 3.5.1.)

Comments. It follows that θ is not a computable number. Because θ

is not a computable real number it is irrational and even transcendental. Source: [G.J. Chaitin, Algorithmic Information Theory, Cambridge Univ. Press, 1987].