Page 251

		11 Learning with Oracles

		§11.1 Introduction

		In Chapters 3 and 4 we observed that unidentifiability can arise for two distinct reasons:

		1. there may be some information theoretic limitation inherent in the collection of underlying realities being identified; or

		2. the collection of underlying realities is in some way too complex for a computable scientist to identify.

		In this chapter we explore the second of these barriers. We do this by considering scientists that are allowed access to knowledge not obtainable through any computable process. We illustrate the key issues in the context of both functions and languages.

		In the case of function identification, we know that , the collection of computable functions, is identifiable by a noncomputable scientist (Proposition 3.43), but cannot be identified by any computable scientist (Theorem 4.28). This suggests that if some additional information of noncomputable nature were available to computable scientists, the collection might become identifiable. In this chapter such information is modeled as membership oracles for noncomputable sets, and through this we are able to classify the hardness of the problem of identifying .

		In the context of languages we have seen that any collection of r.e. languages that contains all the finite languages and an infinite language cannot be identified by any scientist, computable or noncomputable (Corollary 3.28). So a scientist will not be able to overcome such a barrier simply by having access to information about noncomputable processes. However, it is still interesting to investigate whether larger collections of languages become identifiable if a scientist is provided information about processes that are increasingly noncomputable.

		The results on these topics are primarily of technical interest, and this chapter provides only a brief survey, with proofs of some sample findings.

		§11.2 Oracle Scientists

		Consider a machine that, in addition to performing algorithmic computation, is allowed to ask membership queries about some that may not be recursive. Such machines