Abstract:
A uniform machine-independent description is given for a large number of classes of functions computable by Turing machines within, bounded space and time. Let $S$ and $T$ be the classes of nondecreasing functions satisfying conditions (S1)–(S3), (T1), (T2), (ST1)–(ST3). It is proved that the class of functions computable by a Turing machine within space bounded by a function belonging to $S$ and within time bounded by a function belonging to $T$ is equal to the class of functions obtainable from some simple initial functions by means of explicit transformation, substitution and recursion of the type ($*$) where $s\in S$, $t\in T$. Analogous descriptions of classes of functions computable within bounded space and classes of functions computable within bounded time are also presented.