Classes of Predictably Computable Functions

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. It is known that the class F of numerical functions computable by finite automata includes addition and is closed under explicit transformations^) and composition. In particular then, it contains the linear functions (4). This class, F, is taken as a basic class since these functions are computed "as swiftly as possible;" as soon as the input has been scanned, the output is printed. To get a larger class, we consider the class of functions computable (in binary notation) by Turing machines which use an amount of tape bounded by a simpler function, namely one in F. We call this new class Ft. Continuing in this way, we define F; to be the class of functions computable by Turing machines which use in their computations an amount of tape bounded by a function in Ft-i. That is, we