NUK - logo
E-resources
Peer reviewed Open access
  • Learning via queries and or...
    Stephan, Frank

    Annals of pure and applied logic, 10/1998, Volume: 94, Issue: 1
    Journal Article

    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 (QEXSucc, QEX< and QEX+) together with membership queries to some oracle. The results for each of these three models of query-inference are the same: If an oracle is 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 cannot overcome differences between oracles and the query-inference degrees are a proper refinement of the EX-degrees. In the case of finite learning, the query-inference degrees coincide with the Turing degrees. Furthermore oracles can not close the gap between the different types of queries to a teacher.