Primitive recursion in the abstract

摘要

Recurrence can be used as a function definition schema for any nontrivial free algebra, yielding the samecomputational complexity in all cases. We show that primitive-recursive computing is in fact independentof free algebras altogether, and can be characterized by a generic programming principle, namely thecontrol of iteration by the depletion of finite components of the underlying structure.