Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(e) ISSN 0002-9939(p)

     

A minimal pair of $K$-degrees


Authors: Barbara F. Csima and Antonio Montalbán
Journal: Proc. Amer. Math. Soc. 134 (2006), 1499-1502
MSC (2000): Primary 03D30
Posted: October 4, 2005
MathSciNet review: 2199198
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We construct a minimal pair of $K$-degrees. We do this by showing the existence of an unbounded nondecreasing function $f$ which forces $K$-triviality in the sense that $\gamma\in 2^\omega$ is $K$-trivial if and only if for all $n$, $K(\gamma\upharpoonright n) \leq K(n) + f(n)+ \mathcal{O}(1)$.


References

  • [DH] Rod G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, to appear.
  • [DHL04] Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility, J. Comput. System Sci. 68 (2004), no. 1, 96-114. MR 2030512 (2004m:03165)
  • [DHNS03] Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences (Singapore), Singapore Univ. Press, 2003, pp. 103-131. MR 2051976 (2005a:03089)
  • [DHNT] Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, to appear.
  • [LV97] Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, second ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR 1438307 (97k:68086)
  • [YDD04] Liang Yu, Decheng Ding, and Rodney Downey, The Kolmogorov complexity of random reals, Ann. Pure Appl. Logic 129 (2004), no. 1-3, 163-180. MR 2078364

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D30

Retrieve articles in all journals with MSC (2000): 03D30


Additional Information

Barbara F. Csima
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Address at time of publication: Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
Email: csima@math.cornell.edu; csima@math.uwaterloo.ca

Antonio Montalbán
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Address at time of publication: Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Email: antonio@math.cornell.edu; antonio@math.uchicago.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-05-08086-X
PII: S 0002-9939(05)08086-X
Keywords: Minimal pair, relative randomness
Received by editor(s): November 19, 2004
Posted: October 4, 2005
Additional Notes: We thank Denis R. Hirschfeldt for bringing this question to our attention. The second author was partially supported by NSF Grant DMS-0100035.
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia