Π 1 0 classes, L R degrees and Turing degrees

, &
Annals of Pure and Applied Logic 156 (1):21-38 (2008)
  Copy   BIBTEX

Abstract

We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2008.06.004

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 103,885

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

George Barmpalias, Andrew E. M. Lewis and Keng Meng NG. The importance of Π 0 1 classes in effective randomness. The Journal of Symbolic Logic, vol. 75 (2010), pp. 387–400. - George Barmpalias, Andrew E. M. Lewis and Frank Stephan. Π 0 1 classes, LR degrees and Turing degrees. Annals of Pure and Applied Logic, vol. 156 (2008), pp. 21–38. - Antonin Kučera. Measure, Π 0 1 classes and complete extensions of PA. Recursion Theory Week (Oberwofach, 1984). Lecture Notes in Mathematics, vol. 1141. Springer, Berlin, 1985, pp. 245–259. - Frank Stephan. Martin-Löf randomness and PA complete sets. Logic Colloquium '02. Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348. [REVIEW]Douglas Cenzer - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
The importance of Π1 0 classes in effective randomness.George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng - 2010 - Journal of Symbolic Logic 75 (1):387-400.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
The members of thin and minimal Π 1 0 classes, their ranks and Turing degrees.Rodney G. Downey, Guohua Wu & Yue Yang - 2015 - Annals of Pure and Applied Logic 166 (7-8):755-766.
Randomness, relativization and Turing degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
Hyperimmunity in 2\sp ℕ.Stephen Binns - 2007 - Notre Dame Journal of Formal Logic 48 (2):293-316.
Turing degrees of certain isomorphic images of computable relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.

Analytics

Added to PP
2013-12-26

Downloads
42 (#581,456)

6 months
2 (#1,356,011)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Andrew Lewis
Graduate Theological Union

Citations of this work

Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.
Low upper bounds in the LR degrees.David Diamondstone - 2012 - Annals of Pure and Applied Logic 163 (3):314-320.
Reductions between types of numberings.Ian Herbert, Sanjay Jain, Steffen Lempp, Manat Mustafa & Frank Stephan - 2019 - Annals of Pure and Applied Logic 170 (12):102716.

View all 8 citations / Add more citations

References found in this work

Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.

View all 7 references / Add more references