### 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 ...

Get *Theory of Computation* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.