There are $2^{\aleph _{0}}$ many $H$-degrees in the random reals
HTML articles powered by AMS MathViewer
- by Liang Yu and Decheng Ding PDF
- Proc. Amer. Math. Soc. 132 (2004), 2461-2464 Request permission
Abstract:
We prove that there are $2^{\aleph _{0}}$ many $H$-degrees in the random reals.References
- Rodney G. Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity, in preparation.
- Rod G. Downey, Denis R. Hirschfeldt, and André Nies, Randomness, computability, and density, SIAM J. Comput. 31 (2002), no. 4, 1169–1183. MR 1919961, DOI 10.1137/S0097539700376937
- Rodney G. Downey, Denis R. Hirschfeldt, André Nies and Frank Stephan, Trivial reals. Electronic Notes in Theoretical Computer Science (ENTCS), 2002.
- Rod Downey and Guohua Wu, personal communication.
- Antonín Kučera and Theodore A. Slaman, Randomness and recursive enumerability, SIAM J. Comput. 31 (2001), no. 1, 199–211. MR 1857396, DOI 10.1137/S0097539799357441
- 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
- Robert M. Solovay, Draft of paper (or series of papers) on Chaitin’s work, unpublished notes, May, 1975, 215 pages.
- Liang Yu, Decheng Ding, and Rod Downey. The complexity of the random reals, submitted.
Additional Information
- Liang Yu
- Affiliation: Department of Mathematics, Nanjing University, Nanjing, Jiang Su, China
- MR Author ID: 725077
- Email: yuliang@mcs.vuwa.ac.nz
- Decheng Ding
- Affiliation: Department of Mathematics, Nanjing University, Nanjing, Jiang Su, China
- Email: dcding@nju.edu.cn
- 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.
- © Copyright 2004 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 132 (2004), 2461-2464
- MSC (2000): Primary 03D25
- DOI: https://doi.org/10.1090/S0002-9939-04-07417-9
- MathSciNet review: 2052426