Complexity Oscillations in Random Reals
Cong Liu, K. Tanaka · IEICE Transactions on Information and Systems · 2008
The C-oscillation due to Martin-Löf shows that {α|∀n[C(α↑n)≥n-O(1)]}=0, which also follows {α|∀n[K(α↑n)≥n+K(n)-O(1)]}=0. By generalizing them, we show that there does not exist a real α such that ∀n(K(α↑n)≥n+λK(n)-O(1))for any λ>0.