Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Non-cupping and randomness
HTML articles powered by AMS MathViewer

by André Nies PDF
Proc. Amer. Math. Soc. 135 (2007), 837-844 Request permission

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
  • R. Downey, D. Hirschfeldt, J. Miller, and A. Nies. Relativizing Chaitin’s halting probability. To appear in J. Math. Logic.
  • Rod G. Downey and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer-Verlag, Berlin. To appear.
  • 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, DOI 10.1142/9789812705815_{0}005
  • D. Hirschfeldt, A. Nies, and F. Stephan. Using random sets as oracles. To appear.
  • Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
  • 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, DOI 10.2307/2586785
  • Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
  • J. Miller and A. Nies. Randomness and computability: open questions. To appear.
  • Joseph S. Miller and Liang Yu. On initial segment complexity and degrees of randomness. To appear in Trans. Amer. Math. Soc.
  • A. Nies. Computability and Randomness. Monograph, to appear.
  • André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
  • A. Nies. Eliminating concepts. To appear in Proceedings of IMS Workshop on Computational Prospects of Infinity, Singapore, 2005.
  • 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, DOI 10.1007/978-3-662-02460-7
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
  • MR Author ID: 328692
  • Email: andre@cs.auckland.ac.nz
  • 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
  • © Copyright 2006 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Proc. Amer. Math. Soc. 135 (2007), 837-844
  • MSC (2000): Primary 68Q30, 03D28
  • DOI: https://doi.org/10.1090/S0002-9939-06-08540-6
  • MathSciNet review: 2262880