|
NeuroCOLT
Technical Report NC-TR-98-012
The Separation Theorem for the
Relation Classes Associated to the Extended Grzegorczyk Classes
Jean-Sylvestre Gakwaya
Dept of Computer and Mathematics
University of Mons-Hainaut
Keywords:
Grzegorczyk Classes; Blum-Shub-Smale model
Received:
29-MAR-98
Abstract
The Grzegorczyk function classes E^n have been studied
in the classical theory of computability and structurized into a strict
hierarchy. To these classes $\E^n$, the relation classes $\RE^n$ are
associated. They also constitute a hierarchy which is proved
not to collapse from n=2: \RE^2 \subsetneq \RE^3 \subsetneq
....\subsetneq \RE^n \subsetneq .....]
In [GAKWAYA,1997], the definition of the Grzegorczyk classes has been
extended into a new model of computability: the BSS setting. Some
results are provided, in particular that these new classes, called
$\overline{\mathcal{E}}^n_R$, make a strict hierarchy. The aim
of this paper is to show that a well chosen extension of the classes
$\overline{\mathcal{E}}^n_R$
allows us to define a universal function~$\Phi$. This function $\Phi$
distinguishes some relation classes associated to the extended classes
$\overline{\mathcal{E}}^n_R$ in a very similar way to the classical
case.
Download Compressed Postscript
|