A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$ . We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show first that Q(X) implies that X has (...) a certain "slowness" property whereby the elements must enter X slowly (under a certain precise complexity measure of speed of computation) even though X may have high information content. Second we prove that every X with this slowness property is computable in some member of any nontrivial orbit, namely for any noncomputable A ∈ ε there exists B in the orbit of A such that X ≤ T B under relative Turing computability (≤ T ). We produce B using the Δ 0 3 -automorphism method we introduced earlier. (shrink)

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...) We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions. (shrink)

We give a proof of a theorem of Harrington that there is no orbit of the lattice of recursively enumerable sets containing elements of each nonzero recursively enumerable degree. We also establish some degree theoretical extensions.

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)

We state and prove the Translation Theorem. Then we apply the Translation Theorem to Soare's Extension Theorem, weakening slightly the hypothesis to yield a theorem we call the Modified Extension Theorem. We use this theorem to reprove several of the known results about orbits in the lattice of recursively enumerable sets. It is hoped that these proofs are easier to understand than the old proofs.