Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-26T01:43:56.555Z Has data issue: false hasContentIssue false

On the convergence of query-bounded computations and logical closure properties of c.e. sets

Published online by Cambridge University Press:  12 March 2014

Timothy H. McNicholl*
Affiliation:
Department of Mathematics, University of Dallas, Irving, Texas 75062, USA, E-Mail: [email protected]

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.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Beigel, R., Gasarch, W., Kummer, M., Martin, G., McNicholl, T., and Stephan, F., On the query complexity of classes, Proceedings of the 21st international symposium, mathematical foundations of computer science, Lecture Notes in Computer Science, no. 1113, 1996, pp. 206217.Google Scholar
[2]Gasarch, W. and Martin, G., Bounded queries in recursion theory. Springer Verlag. New York. 1998.Google Scholar
[3]Soare, R. I., Recursively enumerable sets and degrees, 1st ed., Springer-Verlag, Berlin, Heidelberg, 1987.CrossRefGoogle Scholar