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

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


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.

Download options


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

External links

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

Through your library


Added to PP

18 (#614,383)

6 months
1 (#386,001)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Robert Solovay
University of California, Berkeley

References found in this work

No references found.

Add more references

Citations of this work

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