David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 54 (2):376-395 (1989)
Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turning functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that $(W \bigoplus A)'$ is forced to disagree with Φ(-; A'). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a "moderately" deep degree: There is a low nonzero degree whose join with any other low degree is not high
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
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.
Citations of this work BETA
Michael A. Jahn (1996). Σ5-Completeness of Index Sets Arising From the Recursively Enumerable Turing Degrees. Annals of Pure and Applied Logic 79 (2):109-137.
Similar books and articles
Dev K. Roy (1993). Recursive Versus Recursively Enumerable Binary Relations. Studia Logica 52 (4):587 - 593.
Theodore A. Slaman (1986). On the Kleene Degrees of Π11 Sets. Journal of Symbolic Logic 51 (2):352 - 359.
Iraj Kalantari & Allen Retzlaff (1979). Recursive Constructions in Topological Spaces. Journal of Symbolic Logic 44 (4):609-625.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
Peter Cholak, Marcia Groszek & Theodore Slaman (2001). An Almost Deep Degree. Journal of Symbolic Logic 66 (2):881-901.
A. M. Dawes (1982). Splitting Theorems for Speed-Up Related to Order of Enumeration. Journal of Symbolic Logic 47 (1):1-7.
Stephan Wehner (1999). On Recursive Enumerability with Finite Repetitions. Journal of Symbolic Logic 64 (3):927-945.
Wolfgang Maass (1982). Recursively Enumerable Generic Sets. Journal of Symbolic Logic 47 (4):809-823.
Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
Michael E. Mytilinaios & Theodore A. Slaman (1988). Σ2-Collection and the Infinite Injury Priority Method. Journal of Symbolic Logic 53 (1):212 - 221.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Recent downloads (6 months)0
How can I increase my downloads?