Learning via queries and oracles
Frank Stephan · 1995
Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a non-recursive oracle.This paper combines these two types it considers three basic models of queries to a teacher, namely QEX[SUCC], QEX[<] and QEX[+], together with membership queries to some oracle.The results for these three models of queryinference are very similar: If an oracle is already omniscient for query-inference, then it is already omniscient for EX.There is an oracle of trivial EX-degree, which allows nontrivial query-inference.Furthermore, queries to a teacher can not overcome differences between oracles and the query-inference degrees are a proper refinement of the EX-degrees.