On the Convergence of Query-Bounded Computations and Logical Closure Properties of C.E. SetsThe Journal of Symbolic Logic (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.
- logical closure properties,
- bounded queries
Citation InformationTimothy H. McNicholl. "On the Convergence of Query-Bounded Computations and Logical Closure Properties of C.E. Sets" The Journal of Symbolic Logic Vol. 66 Iss. 4 (2001) p. 1543 - 1560
Available at: http://works.bepress.com/timothy-mcnicholl/22/