Theory of Computation

5.2   AXT, LOOP PROGRAM, AND GRZEGORCZYK HIERARCHIES

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 that we will subdivide into an infinite sequence of increasingly more inclusive subclasses, S_i. A so-called hierarchy of classes of functions.

5.2.0.4 Definition. A sequence (S_i)_i≥0 of subsets of is a primitive recursive hierarchy provided all of the following hold:

(1) S_i ⊆ S_i+1, for all i ≥ 0

(2) = ⋃_i≥0 S_i.

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