8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – user10891 Jan 24 '11 at 7:33
  • $\begingroup$ 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. $\endgroup$ – Erfan Khaniki Oct 7 '16 at 18:22
1
$\begingroup$

I published a developed version of the above answer to that question (in spanish). It is contained in the book "AVANCES Y APLICACIONES DE SISTEMAS INTELIGENTES Y NUEVAS TECNOLOGIAS", CONSEJO DE PUBLICACIONES DE LA UNIVERSIDAD DE LOS ANDES, 2016 with the title "LA CLASE 0 DE LA JERARQUIA DE GZREGORCZYK ES RECURSIVAMENTE ENUMERABLE".

I always wondered, however, why the quoted paper of Wirz regarding safe recursion was rejected for its publication. It seems fully correct in my understanding and represents a key point in characterizations of recursive hierarchies.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy