Grzegorczyk has divided the class of primitive recursive functions to Grzegorczyk-hierarchy by their rate of growth. In this hierarchy $E\_i\subset E\_{i+1}$ and the subset-relation is strict. Also $\cup\_{i}E\_i = Pr$, i.e. the union of all levels is equal to the class of primitive recursive functions.


I know that primitive recursive functions are recursively enumerable, but I wonder if the levels of Grzegorczyk-hierarchy are recursively enumerable, i.e. is it possible to "scan through" some level $E\_i$ or, even better, functions in $E\_i\setminus E\_{i-1}$?



Enumerating levels of Grzegorczyk-hierarchy
The usual definition of $E\_n$ is in terms of basic functions, the $n$'th generator function, closed under composition, and bounded recursion. I take it that you see how an enumeration could easily be constructed from some sort of a syntax tree, except for the difficulty that the restriction on the scheme of bounded recursion is non-syntactic. A simple idea that occurs to me is to get around this by rewording the restriction of the scheme, e.g. given $f$,$g$,$h$, define $j$:
$$j(x,0) = min(h(x,0),f(x))$$
$$j(x,n+1) = min(h(x,n+1),g(x,j(x,n)))$$
Thus there is no syntactic restriction on bounded recursion, but the value of the new function $j$ is still semantically bounded by the prior function $h$, and therefore I'm fairly sure this is equivalent to the usual scheme of bounded recursion. 


There are also alternate characterisations of the levels of the Grzegorczyk hierarchy that are more naturally syntactic and from which an enumeration can easily be constructed. I have in mind the characterisation by Marc Wirz in terms of [safe recursion](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3374). 


To get an enumeration of $E\_{n+1} \setminus E\_n$ has the following problem: define $f(m) = 0$ if [Goldbach's conjecture](http://en.wikipedia.org/wiki/Goldbach%27s_conjecture) holds up to $m$, otherwise $f(m)$ is equal to the $m$'th value of the $n+1$'st generator function. Now syntactically we see $f \in E\_{n+1}$, but semantically we see $f$ is constant-zero (therefore in $E\_0$ iff Goldbach's conjecture is true. I'm fairly sure this idea can be turned into an impossibility theorem. 


