Codable Sets and Orbits of Computably Enumerable Sets
Harrington, Leo ; Soare, Robert I.
J. Symbolic Logic, Tome 63 (1998) no. 1, p. 1-28 / Harvested from Project Euclid
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 $\varepsilon$ denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$. We previously exhibited a first order $\varepsilon$-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 $\in \varepsilon$ there exists B in the orbit of A such that X $\leq_T$ B under relative Turing computability ($\leq_T$). We produce B using the $\Delta^0_3$-automorphism method we introduced earlier.
Publié le : 1998-03-14
Classification: 
@article{1183745453,
     author = {Harrington, Leo and Soare, Robert I.},
     title = {Codable Sets and Orbits of Computably Enumerable Sets},
     journal = {J. Symbolic Logic},
     volume = {63},
     number = {1},
     year = {1998},
     pages = { 1-28},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745453}
}
Harrington, Leo; Soare, Robert I. Codable Sets and Orbits of Computably Enumerable Sets. J. Symbolic Logic, Tome 63 (1998) no. 1, pp.  1-28. http://gdmltest.u-ga.fr/item/1183745453/