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

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI http://projecteuclid.org/euclid.jsl/1183745453
Options
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.

Analytics

Added to PP index
2017-02-21

Total views
0

Recent downloads (6 months)
0

How can I increase my downloads?

Downloads

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

My notes