Journal of Symbolic Logic 63 (1):1-28 (1998)

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 56,903
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

On N -Tardy Sets.Peter A. Cholak, Peter M. Gerdes & Karen Lange - 2012 - Annals of Pure and Applied Logic 163 (9):1252-1270.

Add more citations

Similar books and articles

Classes Bounded by Incomplete Sets.Kejia Ho & Frank Stephan - 2002 - Annals of Pure and Applied Logic 116 (1-3):273-295.
Difference Sets and Computability Theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
Orbits of Computably Enumerable Sets: Low Sets Can Avoid an Upper Cone.Russell Miller - 2002 - Annals of Pure and Applied Logic 118 (1-2):61-85.
Computably Enumerable Sets Below Random Sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
On Orbits, of Prompt and Low Computably Enumerable Sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
The Computable Lipschitz Degrees of Computably Enumerable Sets Are Not Dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
On the Orbits of Hyperhypersimple Sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.


Added to PP index

Total views

Recent downloads (6 months)

How can I increase my downloads?


Sorry, there are not enough data points to plot this chart.

My notes