Article ID Journal Published Year Pages File Type
6426044 Advances in Mathematics 2011 25 Pages PDF
Abstract

We study oscillation in the prefix-free complexity of initial segments of 1-random reals. For upward oscillations, we prove that ∑n∈ω2−g(n) diverges iff (∃∞n)K(X↾n)>n+g(n) for every 1-random X∈2ω. For downward oscillations, we characterize the functions g such that (∃∞n)K(X↾n)

Related Topics
Physical Sciences and Engineering Mathematics Mathematics (General)
Authors
, ,