David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
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
Stephen Binns & Stephen G. Simpson (2004). Embeddings Into the Medvedev and Muchnik Lattices of Π0 1 Classes. Archive for Mathematical Logic 43 (3):399-414.
Xiaokang Yu & Stephen G. Simpson (1990). Measure Theory and Weak König's Lemma. Archive for Mathematical Logic 30 (3):171-180.
Stephen Binns (2003). A Splitting Theorem for the Medvedev and Muchnik Lattices. Mathematical Logic Quarterly 49 (4):327.
Antonín Kučera (1993). On Relative Randomness. Annals of Pure and Applied Logic 63 (1):61-67.
Douglas Cenzer & Peter G. Hinman (2003). Density of the Medvedev Lattice of Π0 1 Classes. Archive for Mathematical Logic 42 (6):583-600.
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.
Andrea Sorbi & Sebastiaan A. Terwijn (2008). Intermediate Logics and Factors of the Medvedev Lattice. Annals of Pure and Applied Logic 155 (2):69-85.
Kojiro Higuchi (2012). Effectively Closed Mass Problems and Intuitionism. Annals of Pure and Applied Logic 163 (6):693-697.
Stephen G. Simpson & Frank Stephan (2015). Cone Avoidance and Randomness Preservation. Annals of Pure and Applied Logic 166 (6):713-728.
Sebastiaan A. Terwijn (2008). On the Structure of the Medvedev Lattice. Journal of Symbolic Logic 73 (2):543 - 558.
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 downloads194 ( #17,493 of 1,911,313 )
Recent downloads (6 months)52 ( #11,538 of 1,911,313 )
How can I increase my downloads?