Mass problems and randomness

Bulletin of Symbolic Logic 11 (1):1-27 (2005)
Abstract
A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/bsl/1107959497
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 26,188
Through your library
References found in this work BETA
Measure Theory and Weak König's Lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
Vitali's Theorem and WWKL.Douglas K. Brown, Mariagnese Giusto & Stephen G. Simpson - 2002 - Archive for Mathematical Logic 41 (2):191-206.
On Relative Randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.

View all 10 references / Add more references

Citations of this work BETA
Intermediate Logics and Factors of the Medvedev Lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
Effectively Closed Mass Problems and Intuitionism.Kojiro Higuchi - 2012 - Annals of Pure and Applied Logic 163 (6):693-697.
Cone Avoidance and Randomness Preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
Inside the Muchnik Degrees I: Discontinuity, Learnability and Constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.

View all 11 citations / Add more citations

Similar books and articles
More About Uniform Upper Bounds on Ideals of Turing Degrees.Harold T. Hodes - 1983 - Journal of Symbolic Logic 48 (2):441-457.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2010 - Notre Dame Journal of Formal Logic 52 (1):21-38.
Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Wtt-Degrees and T-Degrees of R.E. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
The Degrees of Conditional Problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.
Almost Everywhere Domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.

Monthly downloads

Added to index

2009-01-28

Total downloads

198 ( #20,300 of 2,153,864 )

Recent downloads (6 months)

1 ( #398,005 of 2,153,864 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums