Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-13T09:19:58.448Z Has data issue: false hasContentIssue false
  • English
  • Français

Learning via queries in [+, <]

Published online by Cambridge University Press:  12 March 2014

William I. Gasarch ,
Mark G. Pleszkoch  and
Robert Solovay
William I. Gasarch
Affiliation:
Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, E-mail: [email protected] Department of Computer Science, University of Maryland, College Park, Maryland 20742, E-mail: [email protected]
Mark G. Pleszkoch
Affiliation:
Department of Computer Science, University of Maryland, College Park, Maryland 20742, E-mail: [email protected] Application Solutions Division, IBM Corporation Gaithersburg, Maryland 20877
Robert Solovay
Affiliation:
Department of Mathematics, University of California, Berkeley, California 94720, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols [+ , <]. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in [+, <]. Additionally, we resolve an open question in [7] about passive versus active learning.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 1 , March 1992 , pp. 53 - 81
Copyright
Copyright © Association for Symbolic Logic 1992

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]Case, J. and Smith, C. H., Comparison of identification criteria for machine inductive inference, Theoretical Computer Science, vol. 25 (1983), pp. 193–220.CrossRefGoogle Scholar
[2]Daley, R. P. and Smith, C. H., On the complexity of inductive inference, Information and Control, vol. 69 (1986), pp. 12–40.CrossRefGoogle Scholar
[3]Enderton, H. B., A mathematical introduction to logic, Academic Press, New York, 1972.Google Scholar
[4]Ershov, Y. L., Lavrov, I. A., Taimanov, A. D., and Taitslin, M. A., Elementary theories, Russian Mathematical Surveys, vol. 20 (1965), no. 4, pp. 35–105.CrossRefGoogle Scholar
[5]Fulk, M. A., Saving the phenomena: requirements that inductive inference machines not contradict known data, Information and Computation, vol. 79 (1988), pp. 193–209.CrossRefGoogle Scholar
[6]Gasarch, W. I.et al., Learning via queries, teams, and anomalies, Machine Learning (submitted); a shorter version appeared in the Proceedings of the third annual conference on computational learning theory, Morgan Kaufmann, San Mateo, California, 1990, pp. 327–337.Google Scholar
[7]Gasarch, W. I. and Smith, C. H., Learning via queries, Journal of the Association of Computing Machinery (to appear); a shorter version appeared in the Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Washington, D.C., 1988, pp. 130–137.Google Scholar
[8]Gold, E. M., Language identification in the limit, Information and Control, vol. 10 (1967), pp. 447–474.CrossRefGoogle Scholar
[9]Pitt, L. and Smith, C. H., Probability and plurality for aggregations of learning machines, Information and Computation, vol. 77 (1988), pp. 77–92.CrossRefGoogle Scholar
[10]Smith, C. H., The power of pluralism for automatic program synthesis, Journal of the Association for Computing Machinery, vol. 29 (1982), pp. 1144–1165.CrossRefGoogle Scholar