Pure Iteration and PeriodicityA Note on Some Small Sub-recursive Classes

摘要

We define a hierarchy IT - ∪_n IT~n of small sub-recursive classes, based on the schema of pure iteration. IT is compared with a similar hierarchy, based on primitive recursion, for which a collapse is equivalent to a collapse of the small Grzegorczyk-classes. Our hierarchy does collapse, and the induced relational class is shown to have a highly periodic structure; indeed a unary predicate is decidable in IT iff it is definable in Presburger Arithmetic. The concluding discussion contrasts our findings to those of Kutylowski [12].