Codable Sets and Orbits of Computably Enumerable Sets
Abstract
A set X of nonnegative integers is computably enumerable, also called recursively enumerable, if there is a computable method to list its elements. Let $\varepsilon$ denote the structure of the computably enumerable sets under inclusion, $\varepsilon = $. We previously exhibited a first order $\varepsilon$-definable property Q such that Q guarantees that X is not Turing complete. Here we show first that Q implies that X has a certain "slowness" property whereby the elements must enter X slowly 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 $\in \varepsilon$ there exists B in the orbit of A such that X $\leq_T$ B under relative Turing computability. We produce B using the $\Delta^0_3$-automorphism method we introduced earlier.