David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Bulletin of Symbolic Logic 11 (1):1-27 (2005)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama (2014). Propagation of Partial Randomness. Annals of Pure and Applied Logic 165 (2):742-758.
Kojiro Higuchi (2012). Effectively Closed Mass Problems and Intuitionism. Annals of Pure and Applied Logic 163 (6):693-697.
Andrea Sorbi & Sebastiaan A. Terwijn (2008). Intermediate Logics and Factors of the Medvedev Lattice. Annals of Pure and Applied Logic 155 (2):69-85.
K. Higuchi & T. Kihara (2014). Inside the Muchnik Degrees I: Discontinuity, Learnability and Constructivism. Annals of Pure and Applied Logic 165 (5):1058-1114.
K. Higuchi & T. Kihara (2014). Inside the Muchnik Degrees II: The Degree Structures Induced by the Arithmetical Hierarchy of Countably Continuous Functions. Annals of Pure and Applied Logic 165 (6):1201-1241.
Similar books and articles
Harold T. Hodes (1983). More About Uniform Upper Bounds on Ideals of Turing Degrees. Journal of Symbolic Logic 48 (2):441-457.
Peter Cholak, Rod Downey & Stephen Walk (2002). Maximal Contiguous Degrees. Journal of Symbolic Logic 67 (1):409-437.
Harold T. Hodes (1981). Upper Bounds on Locally Countable Admissible Initial Segments of a Turing Degree Hierarchy. Journal of Symbolic Logic 46 (4):753-760.
Paul Shafer (2010). Characterizing the Join-Irreducible Medvedev Degrees. Notre Dame Journal of Formal Logic 52 (1):21-38.
Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
Michael Stob (1983). Wtt-Degrees and T-Degrees of R.E. Sets. Journal of Symbolic Logic 48 (4):921-930.
André Nies, Frank Stephan & Sebastiaan A. Terwijn (2005). Randomness, Relativization and Turing Degrees. Journal of Symbolic Logic 70 (2):515 - 535.
Su Gao (1994). The Degrees of Conditional Problems. Journal of Symbolic Logic 59 (1):166-181.
Natasha L. Dobrinen & Stephen G. Simpson (2004). Almost Everywhere Domination. Journal of Symbolic Logic 69 (3):914-922.
Joseph S. Miller (2004). Degrees of Unsolvability of Continuous Functions. Journal of Symbolic Logic 69 (2):555 - 584.
Added to index2009-01-28
Total downloads61 ( #54,279 of 1,725,574 )
Recent downloads (6 months)59 ( #19,246 of 1,725,574 )
How can I increase my downloads?