Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-28T13:40:21.728Z Has data issue: false hasContentIssue false
  • English
  • Français

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
Timothy H. McNicholl*
Affiliation:
Department of Mathematics, University of Dallas, Irving, Texas 75062, USA, E-Mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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

Bounded querieslogical closure propertiesadversaries
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 4 , December 2001 , pp. 1543 - 1560
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. 206–217.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