Computable functions can have some quite complex definitions. For example, a loop programmable function might be given via a loop program that has depth of nesting of the loop-end pair, say, equal to 200. Now this is complex! Or a function might be given via an arbitrarily complex sequence of primitive recursions, with the restriction that the computed function is majorized by some known function, for all values of the input (for the concept of majorization see Subsection 2.4.3).

But does such definitional—and therefore, “static” —complexity have any bearing on the computational—dynamic—complexity of the function? We will see that it does, and we will connect definitional and computational complexities quantitatively.

Our study will be restricted to the class Images that we will subdivide into an infinite sequence of increasingly more inclusive subclasses, Si. A so-called hierarchy of classes of functions. Definition. A sequence (Si)i≥0 of subsets of Images is a primitive recursive hierarchy provided all of the following hold:

(1) SiSi+1, for all i ≥ 0

(2) Images = ⋃i≥0 Si.

The hierarchy is proper or nontrivial iff SiSi+1, for all but ...

Get Theory of Computation now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.