Journal of Symbolic Logic 66 (4):1543-1560 (2001)
Call a set A n-correctable if every set Turing reducible to A via a Turing machine that on any input makes at most n queries is Turing reducible to A via a Turing machine that on any input makes at most n-queries and on any input halts no matter what answers are given to its queries. We show that if a c.e. set A is n-correctable for some n ≥ 2, then it is n-correctable for all n. We show that this is the optimal such result by constructing a c.e. set that is 1-correctable but not 2-correctable. The former result is obtained by examining the logical closure properties of c.e. sets that are 2-correctable
|Keywords||Bounded Queries Logical Closure Properties Adversaries|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
On the Construction of Effectively Random Sets.Wolfgang Merkle & Nenad Mihailović - 2004 - Journal of Symbolic Logic 69 (3):862-878.
The Complexity of Oddan.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl & Frank Stephan - 2000 - Journal of Symbolic Logic 65 (1):1 - 18.
Observability of Turing Machines: A Refinement of the Theory of Computation.Yaroslav Sergeyev & Alfredo Garro - 2010 - Informatica 21 (3):425–454.
Learning Via Queries in $\Lbrack +, < \Rbrack$.William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53 - 81.
Randomness and Halting Probabilities.Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1411 - 1430.
Beyond the Universal Turing Machine.Jack Copeland - 1999 - Australasian Journal of Philosophy 77 (1):46-67.
Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
On the Commutativity of Jumps.Timothy H. McNicholl - 2000 - Journal of Symbolic Logic 65 (4):1725-1748.
Definability with a Predicate for a Semi-Linear Set.Michael Benedikt & H. Jerome Keisler - 2003 - Journal of Symbolic Logic 68 (1):319-351.
Added to index2009-01-28
Total downloads12 ( #374,536 of 2,163,904 )
Recent downloads (6 months)1 ( #348,100 of 2,163,904 )
How can I increase my downloads?