Inferring answers to queries

摘要

One focus of inductive inference is to infer a program for a function f from observations or queries about f. We propose a new line of research which examines the question of inferring the answers to queries. For a given class of computable functions, we consider the learning (in the limit) of properties of these functions that can be captured by queries formulated in a logical language L. We study the inference types that arise in this context. Of particular interest is a comparison between the learning of properties and the learning of programs. Our results suggest that these two types of learning are incomparable. In addition, our techniques can be used to prove a general lemma about query inference [W. Gasarch, C. Smith, Learning via queries, J. ACM 39 (1992) 649–676]. We show that I⊂J⇒QI(L)⊂QJ(L) for many standard inference types I, J and many query languages L. Hence any separation that holds between these inference types also holds between the corresponding query inference types. One interesting consequence is that[24,49]QEX0([Succ,<]2)−[2,4]QEX0([Succ,<]2)≠∅.