O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required