On the Convergence of Query-Bounded Computations and Logical Closure Properties of C.E. Sets
McNicholl, Timothy H.
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 1543-1560 / Harvested from Project Euclid
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 $\geq$ 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.
Publié le : 2001-12-14
Classification:  Bounded Queries,  Logical Closure Properties,  Adversaries
@article{1183746611,
     author = {McNicholl, Timothy H.},
     title = {On the Convergence of Query-Bounded Computations and Logical Closure Properties of C.E. Sets},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 1543-1560},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746611}
}
McNicholl, Timothy H. On the Convergence of Query-Bounded Computations and Logical Closure Properties of C.E. Sets. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  1543-1560. http://gdmltest.u-ga.fr/item/1183746611/