Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Pure iteration and periodicity

Edit abstract data

Speaker: Mathias Barra
Slot: Wed, 17:30-17:50, Room 19 (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 Valid HTML 4.01! Valid CSS!