Annals of Pure and Applied Logic 94 (1-3):273-296 (1998)

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 (QEX[Succ], QEX[ 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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00077-8
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,259
Through your library

References found in this work BETA

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
Degrees Joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.

View all 11 references / Add more references

Citations of this work BETA

Learning Via Queries and Oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
Automata Techniques for Query Inference Machines.William Gasarch & Geoffrey R. Hird - 2002 - Annals of Pure and Applied Logic 117 (1-3):169-201.

Add more citations

Similar books and articles

Complexity of the -Query Tautologies in the Presence of a Generic Oracle.Toshio Suzuki - 2000 - Notre Dame Journal of Formal Logic 41 (2):142-151.
Oracles, Visions, and Oral Tradition: Calvin on the Foundation of Scripture.Randall C. Zachman - 2009 - Interpretation: A Journal of Bible and Theology 63 (2):117-129.
On the Commutativity of Jumps.Timothy H. McNicholl - 2000 - Journal of Symbolic Logic 65 (4):1725-1748.


Added to PP index

Total views
15 ( #700,725 of 2,518,587 )

Recent downloads (6 months)
1 ( #408,186 of 2,518,587 )

How can I increase my downloads?


My notes