CLASSIFICATION USING INFORMATION

Let A be a set of functions. A classifier for A is a way of telling, g iven a function f, if f is in A. We will define this notion formally. We will then modify our definition in three ways: (1) allow the classi fier to ask questions to an oracle A (thus increasing the classifiers computational power), (2) allow the classifier to ask questions about f (thus increasing the classifiers information access), and (3) restri ct the number of times the classifier can change its mind (thus decrea sing the classifiers information access). By varying these parameters we will gain a better understanding of the contrast between computatio nal power and informational access. We have determined exactly (1) whi ch sets are classifiable (theorem 3.6), (2) which sets are classifiabl e with queries to some oracle (theorem 3.2), (3) which sets are classi fiable with queries to some oracle and queries about f (theorem 5.2), and (4) which sets are classifiable with queries to some oracle, queri es about f and a bounded number of mindchanges (theorem 5.2). The last two items involve the Borel hierarchy.