**Authors: William Gasarch, Mark G. Pleszkoch, Frank Stephan and Mahendran Velauthapillai**.

Email: gasarch@cs.umd.edu

**Source: ***Annals of Mathematics and Artificial Intelligence*
Vol. 23, No. 1-2, 1998, 147-168.

**Abstract.**
Let A be a set of functions. A classifier for A is a way of telling, given 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 classifier 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) restrict the number of times the classifier can change its mind (thus decreasing the
classifiers information access). By varying these parameters we will gain a better understanding of
the contrast between computational power and informational access. We have determined exactly
(1) which sets are classifiable (theorem 3.6), (2) which sets are classifiable with queries to some
oracle (theorem 3.2), (3) which sets are classifiable with queries to some oracle and queries about f
(theorem 5.2), and (4) which sets are classifiable with queries to some oracle, queries about f and a
bounded number of mindchanges (theorem 5.2). The last two items involve the Borel hierarchy.

©Copyright 1998 Baltzer Science Publishers