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