Learning Via Queries in $\lbrack +, < \rbrack$

Journal of Symbolic Logic 57 (1):53 - 81 (1992)

Robert Solovay
University of California, Berkeley
We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols $\lbrack +, < \rbrack$. 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 $\lbrack +, < \rbrack$. Additionally, we resolve an open question in [7] about passive versus active learning.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275176
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,987
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Learning Via Queries and Oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
Automata Techniques for Query Inference Machines.William Gasarch & Geoffrey R. Hird - 2002 - Annals of Pure and Applied Logic 117 (1-3):169-201.

Add more citations

Similar books and articles


Added to PP index

Total views
16 ( #576,374 of 2,310,435 )

Recent downloads (6 months)
1 ( #754,118 of 2,310,435 )

How can I increase my downloads?


My notes

Sign in to use this feature