Non-cupping and randomness

Author:
André Nies

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

Published electronically:
August 31, 2006

MathSciNet review:
2262880

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be Martin-Löf-random. Then there is a promptly simple set such that for each Martin-Löf-random set , . When , one obtains a c.e. non-computable set which is not weakly Martin-Löf cuppable. That is, for any Martin-Löf-random set , if , then .

**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, -classes and complete extensions of .

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)**

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:
https://doi.org/10.1090/S0002-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

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.