Some Hierarchies of Primitive Recursive Functions on Term Algebras

We compare two different Grzegorczyk hierarchies { H n σ } n ≥0 and { L n σ } n ≥1 on term algebras, which grow according to the height and length of terms, respectively. The solution of almost all inclusion problems among the Grzegorczyk classes and the (simultaneous) recursion number classes R n σ and S n σ on term algebras shows { H n σ } n ≥0 to generalize Weihrauch's Grzegorczyk hierarchy on words { E n k } n ≥0 to arbitrary term algebras. However, by regarding terms as words, { L n σ } n ≥1 turns out to be computationally equivalent to Weihrauch's hierarchy { E n σ } n ≥0 on the whole. Especially, L 2 σ } is equivalent to polynomial time computability and contains several natural term algebra functions. This establishes a notion of feasible term algebra functions and predicates.