Learning via queries to an oracle

Abstract

We study the effect of additional computational power on passive inductive inference. Specifically, we investigate whether allowing IIM's (Inductive Inference Machines) access to an oracle A extends the sets of functions which can be inferred. If we restrict the IIM's to make a finite number of queries to A , then it is the case that A can be of help iff it is not recursive in the halting set (i.e. A ≰ T K ). If an unrestricted number of queries to A is allowed, then any oracle A that is not low (i.e. A′ ≰ T K ) can be used to infer any set of functions which cannot be inferred by a non-oracle IIM. We also study the interaction between additional computational power and bounding the number of times that an IIM is allowed to change its mind. In this context, we have a strict double hierarchy: additional computational power always helps; increasing the number of mind changes allowed always helps; no amount of additional computational power can totally compensate for the extra benefit of one more mind change; and no increase in the number of mind changes allowed can overcome the extra benefit of additional computational power.