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 Free Access

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. Antonín Kučera, Measure, Π⁰₁-classes and complete extensions of 𝑃𝐴, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784,
  • 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. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718
  • 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. Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921

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.