Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to contemporary (...) computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way. (shrink)

The description for this book, Degrees of Unsolvability. (AM-55), Volume 55, will be forthcoming.

We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, (...) we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (shrink)

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from small (...) time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

We prove that for every ${\mathrm{\Sigma }}_{2}^{0}$ enumeration degree b there exists a noncuppable ${\mathrm{\Sigma }}_{2}^{0}$ degree a > 0 e such that b′ ≤ e a′ and a″ ≤ e b″. This allows us to deduce, from results on the high/low jump hierarchy in the local Turing degrees and the jump preserving properties of the standard embedding l: D T → D e , that there exist ${\mathrm{\Sigma }}_{2}^{0}$ noncuppable enumeration degrees at every possible—i.e., above low₁—level of the high/low (...) jump hierarchy in the context of D e. (shrink)

We show that there is a limit lemma for enumeration reducibility to 0 e ', analogous to the Shoenfield Limit Lemma in the Turing degrees, which relativises for total enumeration degrees. Using this and `good approximations' we prove a jump inversion result: for any set W with a good approximation and any set X< e W such that W≤ e X' there is a set A such that X≤ e A< e W and A'=W'. (All jumps are enumeration degree jumps.) (...) The degrees of sets with good approximations include the Σ0 2 degrees and the n-CEA degrees. (shrink)