Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6426044 | Advances in Mathematics | 2011 | 25 Pages |
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
Joseph S. Miller, Liang Yu,