Archive for Mathematical Logic 29 (2):69-84 (1989)

LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/BF01620618
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: 71,489
Through your library

References found in this work BETA

Limiting Recursion.E. Mark Gold - 1965 - Journal of Symbolic Logic 30 (1):28-48.
The Method of Alternating Chains.J. W. Addison - 1965 - In The Theory of Models. Amsterdam: North-Holland Pub. Co.. pp. 1--16.
Enumeration Reducibility Using Bounded Information: Counting Minimal Covers.S. Barry Cooper - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (6):537-560.

View all 8 references / Add more references

Citations of this work BETA

Nondeterministic Bounded Query Reducibilities.Richard Beigel, William Gasarch & Jim Owings - 1989 - Annals of Pure and Applied Logic 41 (2):107-118.
A Proof of Beigel's Cardinality Conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.

Add more citations

Similar books and articles

The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
A Hierarchy of Hereditarily Finite Sets.Laurence Kirby - 2008 - Archive for Mathematical Logic 47 (2):143-157.
An Analysis of the W -Hierarchy.Yijia Chen, Jörg Flum & Martin Grohe - 2007 - Journal of Symbolic Logic 72 (2):513 - 534.
P-Hierarchy on Β Ω.Andrzej Starosolski - 2008 - Journal of Symbolic Logic 73 (4):1202-1214.
Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.
On the Commutativity of Jumps.Timothy H. McNicholl - 2000 - Journal of Symbolic Logic 65 (4):1725-1748.
Borel-Amenable Reducibilities for Sets of Reals.Luca Motto Ros - 2009 - Journal of Symbolic Logic 74 (1):27-49.


Added to PP index

Total views
35 ( #327,703 of 2,520,806 )

Recent downloads (6 months)
1 ( #405,623 of 2,520,806 )

How can I increase my downloads?


My notes