Journal of Symbolic Logic 63 (1):1-28 (1998)
Abstract |
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
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.2307/2586583 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Classes of Recursively Enumerable Sets and Degrees of Unsolvability.Donald A. Martin - 1966 - Mathematical Logic Quarterly 12 (1):295-310.
Citations of this work BETA
Definable Properties of the Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.
Some Orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.
The Complexity of Orbits of Computably Enumerable Sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - Bulletin of Symbolic Logic 14 (1):69 - 87.
2011 North American Annual Meeting of the Association for Symbolic Logic.Itay Neeman - 2012 - Bulletin of Symbolic Logic 18 (2):275-305.
On N -Tardy Sets.Peter A. Cholak, Peter M. Gerdes & Karen Lange - 2012 - Annals of Pure and Applied Logic 163 (9):1252-1270.
View all 6 citations / Add more citations
Similar books and articles
Implicit Measurements of Dynamic Complexity Properties and Splittings of Speedable Sets.Michael A. Jahn - 1999 - Journal of Symbolic Logic 64 (3):1037-1064.
The Complexity of Orbits of Computably Enumerable Sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - Bulletin of Symbolic Logic 14 (1):69 - 87.
On Orbits, of Prompt and Low Computably Enumerable Sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.
On the Orbits of Hyperhypersimple Sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
Definable Incompleteness and Friedberg Splittings.Russell Miller - 2002 - Journal of Symbolic Logic 67 (2):679-696.
Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - Journal of Symbolic Logic 71 (4):1394 - 1410.
Isomorphisms of Splits of Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2003 - Journal of Symbolic Logic 68 (3):1044-1064.
Splitting Theorems for Speed-Up Related to Order of Enumeration.A. M. Dawes - 1982 - Journal of Symbolic Logic 47 (1):1-7.
Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
Analytics
Added to PP index
2009-01-28
Total views
17 ( #633,454 of 2,499,674 )
Recent downloads (6 months)
1 ( #418,206 of 2,499,674 )
2009-01-28
Total views
17 ( #633,454 of 2,499,674 )
Recent downloads (6 months)
1 ( #418,206 of 2,499,674 )
How can I increase my downloads?
Downloads