test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
We define a hierarchy IT 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
websites: Arnold Beckmann