Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



On initial segment complexity and degrees of randomness

Authors: Joseph S. Miller and Liang Yu
Journal: Trans. Amer. Math. Soc. 360 (2008), 3193-3210
MSC (2000): Primary 68Q30, 03D30, 03D28
Published electronically: January 10, 2008
MathSciNet review: 2379793
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define $ X\leq_K Y$ to mean that $ (\forall n)\; K(X\upharpoonright n)\leq K(Y\upharpoonright n)+O(1)$. The equivalence classes under this relation are the $ K$-degrees. We prove that if $ X\oplus Y$ is $ 1$-random, then $ X$ and $ Y$ have no upper bound in the $ K$-degrees (hence, no join). We also prove that $ n$-randomness is closed upward in the $ K$-degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the $ \textit{vL}$-degrees. Unlike the $ K$-degrees, many basic properties of the $ \textit{vL}$-degrees are easy to prove. We show that $ X\leq_K Y$ implies $ X\leq_{\textit{vL}} Y$, so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for $ \leq_C$, the analogue of $ \leq_K$ for plain Kolmogorov complexity.

Two other interesting results are included. First, we prove that for any $ Z\in 2^\omega$, a $ 1$-random real computable from a $ 1$-$ Z$-random real is automatically $ 1$-$ Z$-random. Second, we give a plain Kolmogorov complexity characterization of $ 1$-randomness. This characterization is related to our proof that $ X\leq_C Y$ implies $ X\leq_{\textit{vL}} Y$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 68Q30, 03D30, 03D28

Retrieve articles in all journals with MSC (2000): 68Q30, 03D30, 03D28

Additional Information

Joseph S. Miller
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269-3009

Liang Yu
Affiliation: Department of Mathematics, National University of Singapore, Singapore 117543

Received by editor(s): May 30, 2006
Published electronically: January 10, 2008
Additional Notes: The first author was partially supported by the Marsden Fund of New Zealand and by an NSF VIGRE postdoctoral fellowship at Indiana University
The second author was supported by a postdoctoral fellowship from the New Zealand Institute for Mathematics and its Applications, NSF of China No.10471060 and No.10420130638, and by No.R-146-000-054-123 of Singapore: Computability Theory and Algorithmic Randomness. Both authors were supported by the Institute for Mathematical Sciences, National University of Singapore, during the Computational Aspects of Infinity program in 2005.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.