[14] Show that there are infinite binary sequences such that the length of the shortest program for reference Turing machine U to compute the

[14] Show that there are infinite binary sequences ω such that the length of the shortest program for reference Turing machine U to compute the consecutive digits of ω one after another can be significantly shorter than the length of the shortest program to compute an initial n-length segment ω1:n of ω, for any large enough n.

Comments. Hint: Choose ω a computable sequence with shortest program of length O(1). Then C(ω1:n) = C(n) + O(1), which goes to ∞

with n.