Computability in Europe 2008
Logic and Theory of Algorithms
|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|