[37] Consider Clim(x) = min{l(p) : p(n) = x for all but finitely many n} and Clim sup(x) = min{m : for all but finitely many n there exists a p with l(p) ≤ m and p(n) = x}. Let C

(x) denote the plain Kolmogorov complexity relativized to 0 (that is, the program is allowed to ask an oracle whether a given Turing machine terminates on given input).

(a) Prove that Clim(x) = C

(x) + O(1).

(b) Prove that Clim sup(x) = C

(x) + O(1).

Comments. Source: [N.K. Vereshchagin, Theoret. Comput. Sci., 271(2002), 59–67]. Item

(b) is the more difficult one; Item

(a) is attributed to An.A.
Muchnik and S.Y. Positselsky.