Maximal Machine Learnable Classes

摘要

A class of computable functions ismaximaliff 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.