Oscillation in the initial segment complexity of random reals |
| |
Authors: | Joseph S Miller Liang Yu |
| |
Institution: | aDepartment of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA;bInstitute of Mathematical Sciences, Nanjing University, PR China;cThe State Key Lab for Novel Software Technology, Nanjing University, 210093, PR China |
| |
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)<n+g(n) for almost every X∈ω2. The proof of this result uses an improvement of Chaitin's counting theorem—we give a tight upper bound on the number of strings σ∈n2 such that K(σ)<n+K(n)−m.The work on upward oscillations has applications to the K-degrees. Write XK?Y to mean that K(X?n)?K(Y?n)+O(1). The induced structure is called the K-degrees. We prove that there are comparable () 1-random K-degrees. We also prove that every lower cone and some upper cones in the 1-random K-degrees have size continuum.Finally, we show that it is independent of ZFC, even assuming that the Continuum Hypothesis fails, whether all chains of 1-random K-degrees of size less than ℵ02 have a lower bound in the 1-random K-degrees. |
| |
Keywords: | MSC: primary 03D32 secondary 68Q30 03D30 03E35 |
本文献已被 ScienceDirect 等数据库收录! |
|