test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
We introduce two hierarchies of unknown ordinal height.
The hierarchies are induced by natural fragments of a
calculus based on
finite types and Godel's $T$,
and all the classes in the hierarchies are uniformly defined without referring
bounds. Deterministic complexity classes like $\logspace$, $\classp$,
$\pspace$, $\linspace$ and $\exptime$ are captured by the hierarchies.
Typical subrecursive classes are also captured, e.g.\
the small relational Grzegorczyk classes $\calE^0_*$, $\calE^1_*$
websites: Arnold Beckmann