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, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore Univ. Press, Singapore, 2003, pp. 103–131. MR 2051976,
  • 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. Antonín Kučera and Sebastiaan A. Terwijn, Lowness for the class of random sets, J. Symbolic Logic 64 (1999), no. 4, 1396–1402. MR 1780059,
  • 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. André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. 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