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