|
A minimal pair of -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 -degrees. We do this by showing the existence of an unbounded nondecreasing function which forces -triviality in the sense that is -trivial if and only if for all , .
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.
|