Journal of Symbolic Logic 66 (4):1543-1560 (2001)
AbstractCall 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
Added to PP
Historical graph of downloads
References found in this work
No references found.
Citations of this work
No citations found.
Similar books and articles
On the Commutativity of Jumps.Timothy H. McNicholl - 2000 - Journal of Symbolic Logic 65 (4):1725-1748.
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.
Beyond the Universal Turing Machine.Jack Copeland - 1999 - Australasian Journal of Philosophy 77 (1):46-67.
Randomness and Halting Probabilities.VeróNica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1411 - 1430.
Learning Via Queries in $\lbrack +, < \rbrack$.William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53 - 81.
Observability of Turing Machines: A Refinement of the Theory of Computation.Yaroslav Sergeyev & Alfredo Garro - 2010 - Informatica 21 (3):425–454.
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.
On the Construction of Effectively Random Sets.Wolfgang Merkle & Nenad Mihailović - 2004 - Journal of Symbolic Logic 69 (3):862-878.
Definability with a Predicate for a Semi-Linear Set.Michael Benedikt & H. Jerome Keisler - 2003 - Journal of Symbolic Logic 68 (1):319-351.