Maximal machine learnable classes

Authors: John Case, and Mark A. Fulk

Source: Journal of Computer and System Sciences Vol. 58, No. 1, 1999, 211 - 214.

Abstract. A class of computable functions is maximal iff it can be incrementally learned by some inductive inference machine (IIM), but no infinitely larger class of computable functions can be so learned. Rolf Wiehagen posed the question whether there exist such maximal classes. This question and many interesting variants are answered herein in the negative. Viewed positively, each IIM can be infinitely improved upon! Also discussed are the problems of algorithmically finding the improvements proved to exist.

©Copyright 1999, Academic Press