Π 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

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

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.
Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Upper bounds on ideals in the computably enumerable Turing degrees.George Barmpalias & André Nies - 2011 - Annals of Pure and Applied Logic 162 (6):465-473.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Almost everywhere domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.
The degrees of conditional problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.
Degrees of unsolvability of continuous functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555-584.
Maximal Chains in the Turing Degrees.C. T. Chong & Liang Yu - 2007 - Journal of Symbolic Logic 72 (4):1219 - 1227.
Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Infima of d.r.e. degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
The existential theory of the poset of R.e. Degrees with a predicate for single jump reducibility.Steffen Lempp & Manuel Lerman - 1992 - Journal of Symbolic Logic 57 (3):1120-1130.

Analytics

Added to PP
2013-12-26

Downloads
32 (#488,786)

6 months
2 (#1,240,909)

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 9 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.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.

View all 8 references / Add more references