Some Hierarchies of Primitive Recursive Functions on Term Algebras
Klaus‐Hilmar Sprenger · Mathematical logic quarterly · 1997
Abstract We compare two different Grzegorczyk hierarchies {Hnσ}n≥0 and {Lnσ}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 Rnσ and Snσ on term algebras shows {Hnσ}n≥0 to generalize Weihrauch's Grzegorczyk hierarchy on words {Enk}n≥0 to arbitrary term algebras. However, by regarding terms as words, {Lnσ}n≥1 turns out to be computationally equivalent to Weihrauch's hierarchy {Enσ}n≥0 on the whole. Especially, L2σ} is equivalent to polynomial time computability and contains several natural term algebra functions. This establishes a notion of feasible term algebra functions and predicates.