most recent 30 from http://mathoverflow.net 2013-05-19T19:53:07Z http://mathoverflow.net/feeds/question/52606 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52606/enumerating-levels-of-grzegorczyk-hierarchy Frank 2011-01-20T12:04:55Z 2011-01-22T01:11:52Z

<p>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.</p> <p>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}$?</p>

http://mathoverflow.net/questions/52606/enumerating-levels-of-grzegorczyk-hierarchy/52806#52806 Daniel Mehkeri 2011-01-22T01:11:52Z 2011-01-22T01:11:52Z

<p>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. </p> <p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3374" rel="nofollow">safe recursion</a>. </p> <p>To get an enumeration of $E_{n+1} \setminus E_n$ has the following problem: define $f(m) = 0$ if <a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture" rel="nofollow">Goldbach's conjecture</a> 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. </p>