Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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
DOI: https://doi.org/10.1090/S0002-9939-05-08086-X
Published electronically: 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 [Enhancements On Off] (What's this?)

  • [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: https://doi.org/10.1090/S0002-9939-05-08086-X
Keywords: Minimal pair, relative randomness
Received by editor(s): November 19, 2004
Published electronically: 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 28 years after publication.

American Mathematical Society