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
DOI: https://doi.org/10.1090/S0002-9947-08-04395-X
Published electronically: January 10, 2008
MathSciNet review: 2379793
Full-text PDF

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?)

  • 1. Gregory J. Chaitin, On the length of programs for computing finite binary sequences: Statistical considerations, J. Assoc. Comput. Mach. 16 (1969), 145-159. MR 0237121 (38:5414)
  • 2. -, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329-340. MR 0411829 (53:15557)
  • 3. -, Incompleteness theorems for random reals, Adv. in Appl. Math. 8 (1987), no. 2, 119-146. MR 886921 (88h:68038)
  • 4. Barbara F. Csima, Rod G. Downey, Noam Greenberg, Denis R. Hirschfeldt, and Joseph S. Miller, Every $ 1$-generic computes a properly $ 1$-generic, Journal of Symbolic Logic. 71 (2006), 1385-1393. MR 2275865 (2007h:03083)
  • 5. R. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, Berlin, To appear.
  • 6. Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility (extended abstract), Mathematical foundations of computer science, 2001 (Mariánské Láznĕ), Lecture Notes in Comput. Sci., vol. 2136, Springer, Berlin, 2001, pp. 316-327. MR 1907022 (2003j:03051)
  • 7. -, Randomness and reducibility, J. Comput. System Sci. 68 (2004), no. 1, 96-114, See [6] for an extended abstract. MR 2030512 (2004m:03165)
  • 8. Rod G. Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin's halting probability, J. Math. Log. 5 (2005), no. 2, 167-192. MR 2188515 (2007e:68031)
  • 9. Péter Gács, Exact expressions for some randomness tests, Z. Math. Logik Grundlag. Math. 26 (1980), no. 5, 385-394. MR 82c:65004
  • 10. -, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186-192. MR 87k:03043
  • 11. A. N. Kolmogorov, Three approaches to the quantitative definition of information, Internat. J. Comput. Math. 2 (1968), 157-168. MR 0243922 (39:5240)
  • 12. Antonín Kučera, Measure, $ \Pi\sp 0\sb 1$-classes and complete extensions of $ {\rm PA}$, Recursion theory week (Oberwolfach, 1984), Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245-259. MR 87e:03102
  • 13. Antonín Kučera and Sebastiaan A. Terwijn, Lowness for the class of random sets, J. Symbolic Logic 64 (1999), no. 4, 1396-1402. MR 2001j:03082
  • 14. S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.
  • 15. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983, Local and global theory. MR 85h:03044
  • 16. L. A. Levin, Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Problems Inform. Transmission 10 (1974), no. 3, 206-210. MR 0469513 (57:9298)
  • 17. -, The concept of a random sequence, Soviet Math. Dokl. 212 (1973) (1974), 1413-1416. MR 366096 (51:2346)
  • 18. M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993. MR 94j:68121
  • 19. Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602-619. MR 0223179 (36:6228)
  • 20. -, Complexity oscillations in infinite binary sequences, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 19 (1971), 225-230. MR 0451322 (56:9609)
  • 21. Joseph S. Miller, Every $ 2$-random real is Kolmogorov random, J. Symbolic Logic 69 (2004), no. 3, 907-913. MR 2078929 (2005e:68108)
  • 22. Joseph S. Miller and Liang Yu, Oscillation in the initial segment complexity of random reals, In preparation.
  • 23. André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274-305. MR 2166184
  • 24. André Nies, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515-535. MR 2140044
  • 25. John C. Oxtoby, Measure and category, second ed., Graduate Texts in Mathematics, vol. 2, Springer-Verlag, New York, 1980, A survey of the analogies between topological and measure spaces. MR 81j:28003
  • 26. Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 32:4013
  • 27. Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987. MR 88m:03003
  • 28. R. J. Solomonoff, A formal theory of inductive inference, Information and Control 7 (1964), 1-22, 224-254.
  • 29. Robert M. Solovay, Draft of paper (or series of papers) on Chaitin's work, (1975), Unpublished notes, 215 pages.
  • 30. M. van Lambalgen, Random sequences, Ph.D. Dissertation, University of Amsterdam, 1987.
  • 31. Michiel van Lambalgen, The axiomatization of randomness, J. Symbolic Logic 55 (1990), no. 3, 1143-1167. MR 92f:68075
  • 32. Liang Yu and Decheng Ding, There are $ 2\sp {\aleph\sb 0}$ many $ H$-degrees in the random reals, Proc. Amer. Math. Soc. 132 (2004), no. 8, 2461-2464 (electronic). MR 2052426 (2004m:68109)
  • 33. Liang Yu, Decheng Ding, and Rod G. Downey, The Kolmogorov complexity of random reals, Ann. Pure Appl. Logic 129 (2004), no. 1-3, 163-180. MR 2078364 (2005e:68109)
  • 34. A. K. Zvonkin and L. A. Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Math. Surveys 25 (1970), no. 6, 83-124. MR 0307889 (46:7004)

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
Email: joseph.miller@math.uconn.edu

Liang Yu
Affiliation: Department of Mathematics, National University of Singapore, Singapore 117543
Email: yuliang.nju@gmail.com

DOI: https://doi.org/10.1090/S0002-9947-08-04395-X
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.

American Mathematical Society