[19] Show that there exists an infinite binary sequence and a constant c > 0 such that lim infn C(1:n|n) c, but for

[19] Show that there exists an infinite binary sequence ω and a constant c > 0 such that lim infn→∞ C(ω1:n|n) ≤

c, but for any unbounded function f we have lim supn→∞ C(ω1:n|n) ≥ n − f(n).

Comments. The oscillations can have amplitude Ω(n). Hint: Use the nstrings as defined previously. Construct ω = y1y2 ... from finite strings yi. Let c be a fixed independent constant. For odd i choose yi such that y1 ...yi is an n-string, which implies that C(y1:i|l(y1:i)) <

c. For even i choose yi as a long enough random string so that C(y1:i|l(y1:n)) ≥

l(y1:n) − f(l(y1:n)). Source: [H.P. Katseff and M. Sipser, Theoret. Comput. Sci., 15(1981), 291–309].