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 describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...) _\alpha ^0 $ orbit (from the proof). (shrink)

We investigate the orbit of a low computably enumerable set under automorphisms of the partial order of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of mapping A to a set B such that CTB. Thus, the orbit in of the low set A cannot be contained in the upper cone above C. This complements a result of Harrington, (...) who showed that the orbit of a noncomputable c.e. set cannot be contained in the lower cone below any incomplete c.e. set. (shrink)

Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating ∄-definable properties (...) of A , like maximal, hh-simple, atomless, to the information content of A . Harrington and Soare gave an answer to Post's program for definable properties by producing an ∄-definable property Q which guarantees that A is incomplete and noncomputable, but developed a new Δ 3 0 -automorphism method to prove certain other properties are not ∄-definable. In this paper we introduce new ∄-definable properties relating the ∄-structure of A to deg, which answer some open questions. In contrast to Q we exhibit here an ∄-definable property T which allows such a rapid flow of elements into A that A must be complete even though A may possess many other properties such as being promptly simple. We also present a related property NL which has a slower flow but fast enough to guarantee that A is not low, even though A may possess virtually all other related lowness properties and A may simultaneously be promptly simple. (shrink)

We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low2. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.

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.

We prove conjectures of Herrmann and Stob by showing that the dense simple sets are orbit complete w.r.t. the simple sets.

The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.We will work in the structure of the computably enumerable sets. The language is just inclusion, (...) ⊆. This structure is called ε.All sets will be computably enumerable non-computable sets and all degrees will be computably enumerable and non-computable, unless otherwise noted. Our notation and definitions are standard and follow Soare [1987]; however we will warm up with some definitions and notation issues so the reader need not consult Soare [1987]. Some historical remarks follow in Section 2.1 and throughout Section 3.We will also consider the quotient structure ε modulo the ideal of finite sets, ε*. ε* is a definable quotient structure of ε since “Χ is finite” is definable in ε; “Χ is finite” iff all subsets of Χ are computable. We use A* to denote the equivalent class of A under the ideal of finite sets. (shrink)

Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...) which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project. In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world. (shrink)