Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Pure iteration and periodicity

Speaker: Mathias Barra
Slot: Array, 17:30-17:50, col. 5


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 Arithmetic.

websites: Arnold Beckmann 2008-05-18