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)

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)

We show that the double jump is definable in the computably enumerable sets. Our main result is as follows: let [Formula: see text] is the Turing degree of a [Formula: see text] set J ≥T0″}. Let [Formula: see text] such that [Formula: see text] is upward closed in [Formula: see text]. Then there is an ℒ property [Formula: see text] such that [Formula: see text] if and only if there is an A where A ≡T F and [Formula: see text]. (...) A corollary of this is that, for all n ≥ 2, the high n computably enumerable degrees are invariant in the computably enumerable sets. Our work resolves Martin's Invariance Conjecture. (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)

We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.