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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesHarold 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.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
