Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
     

Non-cupping and randomness

Author(s): André Nies
Journal: Proc. Amer. Math. Soc. 135 (2007), 837-844.
MSC (2000): Primary 68Q30, 03D28
Posted: August 31, 2006
Retrieve article in: PDF DVI PostScript

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:

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
Email: andre@cs.auckland.ac.nz

DOI: 10.1090/S0002-9939-06-08540-6
PII: S 0002-9939(06)08540-6
Keywords: Cupping, randomness, $K$-trivial
Received by editor(s): June 17, 2005
Received by editor(s) in revised form: October 10, 2005
Posted: 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 of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google