|
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 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 .
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, -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)
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.
|