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

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.