Inferring answers to queries
William I. Gasarch, Andrew Chak Yiu Lee · 1997
The usual focus of recursion-theoretic inductive inference is to infer a program (resp.grammar) for a function f (resp.language A) from observations and/or queries about f (resp.A).We propose a new line of research which examines the question of inferring the answers to querzes.For a given class of recursive funct,ions, we consider t,he learning (in the limit) of propwtzes of these funct,ions that can be captured by queries formulated in a logical language L. We st,udy t,he inference types that arise in this context, and we present preliminary results.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 addit,ion, our techniques can be used to prove a general theorem about query inference IGS92].We show that ZcJ* QW) c QJ'P)for many standard inference t)ypes 1, J and many query languages L. Hence any separation that, holds between these inference types also holds between the corresponding query inference types.One bizarre consequence is that [24,49lQEX,([S ucc, <I')-[2,4]QEX,([Succ, <12)# 0. IntroductionWhen scientist,s look at data, they may be trying to answer some question about, the dat,a (e.g., "Is the shape l