Mass problems and randomness

Bulletin of Symbolic Logic 11 (1):1-27 (2005)
  Copy   BIBTEX

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,931

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.
Almost everywhere domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
The degrees of conditional problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.
Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.
Maximal contiguous degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.

Analytics

Added to PP
2009-01-28

Downloads
308 (#68,504)

6 months
14 (#201,098)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
Intermediate logics and factors of the Medvedev lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
Mass problems and almost everywhere domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.

View all 28 citations / Add more citations

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
Measure theory and weak König's lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.

View all 20 references / Add more references