Classes of Predictably Computable Functions

Abstract

In this paper we study a sequence of classes of computable functions for which a prediction of the complexity of the calculation may be made in a comparatively simple fashion. The class of recursive functions is accepted as being the class of just those functions for which there is a mechanical procedure for obtaining the values from the arguments. However, this class, since it involves all computations, must involve arbitrarily complex computations. Various more restricted classes of functions have been proposed as being somehow more easily computable, but the greater ease of computation has largely been left on the level of intuition. The notable exception to this is the class F of functions computable(2) by finite automata. However, this class is too severely restricted; it does not even include multiplication. We present a hierarchy of more inclusive classes of functions, each defined as the class of functions whose computational complexity is "predictable" by a function in the preceding class.