We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.

A proof is given that 0′ is definable in the structure of the degrees of unsolvability. This answers a long-standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator.

We present a necessary and sufficient condition for the embeddability of a principally decomposable finite lattice into the computably enumerable degrees. This improves a previous result which required that, in addition, the lattice be ranked. The same condition is also necessary and sufficient for a finite lattice to be embeddable below every non-zero computably enumerable degree.

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)

The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question (...) is equivalent to: Given a computer with access to an oracle which will answer membership questions about a setA, can a program be written which will correctly compute the answers to all membership questions about a setB? If the answer is yes, then we say thatBisTuring reducibletoAand writeB≤TA. We say thatB≡TAifB≤TAandA≤TB. ≡Tis an equivalence relation, and ≤Tinduces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called thedegrees of unsolvability, and elements of this poset are calleddegrees.Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. (shrink)

We prove that every countable jump upper semilattice can be embedded in.

The biinterpretability conjecture for the r.e. degrees asks whether, for each sufficiently large k, the [Formula: see text] relations on the r.e. degrees are uniformly definable from parameters. We solve a weaker version: for each k ≥ 7, the [Formula: see text] relations bounded from below by a nonzero degree are uniformly definable. As applications, we show that Low 1 is parameter definable, and we provide methods that lead to a new example of a ∅-definable ideal. Moreover, we prove that (...) automorphisms restricted to intervals [d, 1], d ≠ 0, are [Formula: see text]. We also show that, for each c ≠ 0, can be interpreted in [0, c] without parameters. (shrink)

The contributions in the book examine the historical and contemporary manifestations of organized crime, the symbiotic relationship between legitimate and ...

Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any (...) ideal of the r.e. degrees. (shrink)

Recent results on initial segments of the Turing degrees are presented, and some conjectures about initial segments that have implications for the existence of nontrivial automorphisms of the Turing degrees are indicated.