A minimal pair of $K$-degrees
HTML articles powered by AMS MathViewer
- by Barbara F. Csima and Antonio Montalbán PDF
- Proc. Amer. Math. Soc. 134 (2006), 1499-1502 Request permission
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
- Rod G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, to appear.
- Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility, J. Comput. System Sci. 68 (2004), no. 1, 96–114. MR 2030512, DOI 10.1016/j.jcss.2003.07.004
- Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore Univ. Press, Singapore, 2003, pp. 103–131. MR 2051976, DOI 10.1142/9789812705815_{0}005
- Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, to appear.
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR 1438307, DOI 10.1007/978-1-4757-2606-0
- 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, DOI 10.1016/j.apal.2004.01.006
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
- MR Author ID: 735103
- 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
- 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.
- © Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 134 (2006), 1499-1502
- MSC (2000): Primary 03D30
- DOI: https://doi.org/10.1090/S0002-9939-05-08086-X
- MathSciNet review: 2199198