Available in electronic format
Available in print format		 Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

A minimal pair of $K$-degrees

Author(s): Barbara F. Csima; Antonio Montalbán
Journal: Proc. Amer. Math. Soc. 134 (2006), 1499-1502.
MSC (2000): Primary 03D30
Posted: October 4, 2005
Retrieve article in: PDF

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: 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.
Copyright of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google