[31] Consider two complexity measures for infinite binary sequences . Let C() be the minimal length of a program p such that p(n) = 1:n

[31] Consider two complexity measures for infinite binary sequences ω. Let C∞(ω) be the minimal length of a program p such that p(n) = ω1:n for all sufficiently large n. Let Cˆ∞(ω) be defined as lim supn→∞ C(ω1:n|n). Prove that C∞(ω) ≤ 2Cˆ∞(ω) + O(1), and that this bound is tight (the constant 2 cannot be replaced by a smaller one).

Comments. Source: [B. Durand, A.K. Shen, and N.K. Vereshchagin, Theoret. Comput. Sci., 171(2001), 47–58].