On the convergence of query-bounded computations and logical closure properties of C.e. Sets

Journal of Symbolic Logic 66 (4):1543-1560 (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

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,856

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
26 (#444,425)

6 months
1 (#386,040)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references

Citations of this work

No citations found.

Add more citations