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)



Non-cupping and randomness

Author: André Nies
Journal: Proc. Amer. Math. Soc. 135 (2007), 837-844
MSC (2000): Primary 68Q30, 03D28
Published electronically: August 31, 2006
MathSciNet review: 2262880
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ Y \in \Delta^0_2 $ be Martin-Löf-random. Then there is a promptly simple set $ A$ such that for each Martin-Löf-random set $ Z$, $ Y \le_T A \oplus Z \Rightarrow Y \le_T Z$. When $ Y = \Omega$, one obtains a c.e. non-computable set $ A$ which is not weakly Martin-Löf cuppable. That is, for any Martin-Löf-random set $ Z$, if $ \emptyset' \le_T A \oplus Z$, then $ \emptyset' \le_T Z$.

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

  • 1. R. Downey, D. Hirschfeldt, J. Miller, and A. Nies.
    Relativizing Chaitin's halting probability.
    To appear in J. Math. Logic.
  • 2. Rod G. Downey and Denis R. Hirschfeldt.
    Algorithmic randomness and complexity.
    Springer-Verlag, Berlin.
    To appear.
  • 3. Rod G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan.
    Trivial reals.
    In Proceedings of the 7th and 8th Asian Logic Conferences, pages 103-131, Singapore, 2003. Singapore Univ. Press. MR 2051976 (2005a:03089)
  • 4. D. Hirschfeldt, A. Nies, and F. Stephan.
    Using random sets as oracles.
    To appear.
  • 5. A. Kucera.
    Measure, $ \Pi\sp 0\sb 1$-classes and complete extensions of $ {\rm PA}$.
    In Recursion theory week (Oberwolfach, 1984), volume 1141 of Lecture Notes in Math., pages 245-259. Springer, Berlin, 1985. MR 0820784 (87e:03102)
  • 6. A. Kucera and S. Terwijn.
    Lowness for the class of random sets.
    J. Symbolic Logic, 64:1396-1402, 1999. MR 1780059 (2001j:03082)
  • 7. M. Lerman.
    Degrees of Unsolvability.
    Perspectives in Mathematical Logic. Springer-Verlag, Heidelberg, 1983. MR 0708718 (85h:03044)
  • 8. J. Miller and A. Nies.
    Randomness and computability: open questions.
    To appear.
  • 9. Joseph S. Miller and Liang Yu.
    On initial segment complexity and degrees of randomness.
    To appear in Trans. Amer. Math. Soc.
  • 10. A. Nies.
    Computability and Randomness.
    Monograph, to appear.
  • 11. A. Nies.
    Lowness properties and randomness.
    Adv. in Math., 197:274-305, 2005. MR 2166184
  • 12. A. Nies.
    Eliminating concepts.
    To appear in Proceedings of IMS Workshop on Computational Prospects of Infinity, Singapore, 2005.
  • 13. R. Soare.
    Recursively Enumerable Sets and Degrees.
    Perspectives in Mathematical Logic, Omega Series. Springer-Verlag, Heidelberg, 1987. MR 0882921 (88m:03003)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 68Q30, 03D28

Retrieve articles in all journals with MSC (2000): 68Q30, 03D28

Additional Information

André Nies
Affiliation: Department of Computer Science, Private Bag 92019, Auckland, New Zealand

Keywords: Cupping, randomness, $K$-trivial
Received by editor(s): June 17, 2005
Received by editor(s) in revised form: October 10, 2005
Published electronically: August 31, 2006
Additional Notes: The author was partially supported by the Marsden Fund of New Zealand, grant no. 03-UOA-130.
Communicated by: Julia F. Knight
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society