I first seriously contemplated writing a book on degree theory in 1976 while I was visiting the University of Illinois at Chicago Circle. There was, at that time, some interest in ann-series book about degree theory, and through the encouragement of Bob Soare, I decided to make a proposal to write such a book. Degree theory had, at that time, matured to the point where the local structure results which had been the mainstay of the earlier papers in the area (...) were finding a steadily increasing number of applications to global degree theory. Michael Yates was the first to realize that the time had come for a systematic study of the interaction between local and global degree theory, and his papers had a considerable influence on the content of this book. During the time that the book was being written and rewritten, there was an explosion in the number of global theorems about the degrees which were proved as applications of local theorems. The global results, in turn, pointed the way to new local theorems which were needed in order to make further progress. I have tried to update the book continuously, in order to be able to present some of the more recent results. It is my hope to introduce the reader to some of the fascinat ing combinatorial methods of Recursion Theory while simultaneously showing how to use these methods to prove some beautiful global theorems about the degrees. (shrink)

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. (shrink)

This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...) ∃-theories. (shrink)