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)

 

 

There are $2^{\aleph_{0}}$ many $H$-degrees in the random reals


Authors: Liang Yu and Decheng Ding
Journal: Proc. Amer. Math. Soc. 132 (2004), 2461-2464
MSC (2000): Primary 03D25
Published electronically: March 25, 2004
MathSciNet review: 2052426
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that there are $2^{\aleph_{0}}$ many $H$-degrees in the random reals.


References [Enhancements On Off] (What's this?)

  • 1. Rodney G. Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity, in preparation.
  • 2. Rod G. Downey, Denis R. Hirschfeldt, and André Nies, Randomness, computability, and density, SIAM J. Comput. 31 (2002), no. 4, 1169–1183. MR 1919961, 10.1137/S0097539700376937
  • 3. Rodney G. Downey, Denis R. Hirschfeldt, André Nies and Frank Stephan, Trivial reals. Electronic Notes in Theoretical Computer Science (ENTCS), 2002.
  • 4. Rod Downey and Guohua Wu, personal communication.
  • 5. Antonín Kučera and Theodore A. Slaman, Randomness and recursive enumerability, SIAM J. Comput. 31 (2001), no. 1, 199–211 (electronic). MR 1857396, 10.1137/S0097539799357441
  • 6. Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
  • 7. Robert M. Solovay, Draft of paper (or series of papers) on Chaitin's work, unpublished notes, May, 1975, 215 pages.
  • 8. Liang Yu, Decheng Ding, and Rod Downey. The complexity of the random reals, submitted.

Similar Articles

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

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


Additional Information

Liang Yu
Affiliation: Department of Mathematics, Nanjing University, Nanjing, Jiang Su, China
Email: yuliang@mcs.vuwa.ac.nz

Decheng Ding
Affiliation: Department of Mathematics, Nanjing University, Nanjing, Jiang Su, China
Email: dcding@nju.edu.cn

DOI: https://doi.org/10.1090/S0002-9939-04-07417-9
Received by editor(s): April 17, 2003
Received by editor(s) in revised form: May 28, 2003
Published electronically: March 25, 2004
Additional Notes: We thank Professor Rodney Downey for his nice comments. Both of the authors are supported by NSF of China No.19931020, 60310213 and the Ph.D. project of the State Education Ministry of China. The first author is also supported by a postdoctoral fellowship of the New Zealand Institute for Mathematics and its Applications, Centre of Research Excellence.
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2004 American Mathematical Society