# Enumerating levels of Grzegorczyk-hierarchy

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}$?

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.
To get an enumeration of $E_{n+1} \setminus E_n$ has the following problem: define $f(m) = 0$ if Goldbach's 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.
• I had the idea of using $min$-function but rejected it for some reason. I can't, however, see now why that wouldn't work. Thanks for bringing that up, I need to re-check my previous work. I don't understand the last paragraph of your answer. I need to think about it. (Its not clear to me how $f$ is actually syntactically defined.) Thank you, especially for the safe recursion -pointer. – user10891 Jan 24 '11 at 7:33
• The idea in last paragraph can be used to prove impossibility theorem for enumeration of $E_{n+1}\setminus E_n$ in a constructive theory like ${\bf HA}$, but I'm not sure how it can lead to impossibility theorem in a classical theory. – Erfan Khaniki Oct 7 '16 at 18:22