[12] A Turing machine T computes an infinite sequence if there is a program p such that T (p, n) = 1:n for all

[12] A Turing machine T computes an infinite sequence ω if there is a program p such that T (p, n) = ω1:n for all n. Define C(ω) =

min{l(p) : U(p, n) = ω1:n for all n}, or ∞ if such a p does not exist.

Obviously, for all ω either C(ω) < ∞ or C(ω) = ∞.

(a) Show that C(ω) < ∞ iff 0.ω is a computable real number as in Exercise 1.7.22 on page 47. For the mathematical constants π and

e, C(π) < ∞ and C

(e) < ∞.

(b) Show that the reals 0.ω with C(ω) < ∞ form a countably infinite set and that the reals 0.ω with C(ω) = ∞ have uniform measure one in the total set of reals in the interval [0, 1).