Article
On the Convergence of Query-Bounded Computations and Logical Closure Properties of C.E. Sets
The Journal of Symbolic Logic
(2001)
Abstract
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
- logical closure properties,
- adversaries,
- bounded queries
Disciplines
Publication Date
2001
DOI
10.2307/2694961
Publisher Statement
Copyright 2001 Association for Symbolic Logic
Citation Information
Timothy 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/