Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:12:02Z http://mathoverflow.net/feeds/question/112337 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112337/recursively-enumerable-sets-as-range-sets-of-functions-in-grzegorczyk-hierarchy Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy boumol 2012-11-14T01:57:04Z 2012-11-14T12:30:38Z <p>It is well known that <a href="http://en.wikipedia.org/wiki/Recursively_enumerable_set" rel="nofollow">recursively enumerable sets</a> can be defined (among many other equivalent alternatives) as the range sets of primitive recusive functions (except for the trivial case of the empty set).</p> <p>On the other hand, primitive recursive functions can be presented in an stratified way using <a href="http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy" rel="nofollow">Grzegorczyk-hierarchy</a>.</p> <p>I am wondering what it is known about whether recursively enumerable sets can be presented as the range sets of functions in some particular level of Grzegorczyk-hierarchy. </p> http://mathoverflow.net/questions/112337/recursively-enumerable-sets-as-range-sets-of-functions-in-grzegorczyk-hierarchy/112339#112339 Answer by Joel David Hamkins for Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy Joel David Hamkins 2012-11-14T02:40:23Z 2012-11-14T03:23:59Z <p>It seems to me that every nonempty computably enumerable set will be the range of a primitive recursive function that is very low in the Grzegorczyk hierarchy, and it seems that even $\cal {E}^1$ suffices. The reason is that if $A$ is a nonempty c.e. set, then it is the domain of some computable function $\varphi_e$, with Turing machine program $e$. Let $k_0$ be the smallest element of $A$. Let $p$ be the primitive recursive function defined so that $p(n)=k$ if $n$ is a G&ouml;del code of the entire computation sequence of program $e$ on input $k$, and this computation sequence successfully attains the halt state, and otherwise $p(n)=k_0$ if $n$ is not such a code. The graph of this function is $\Delta_0$-definable and so $p$ really is primitive recursive. Furthermore, $p$ is not at all a fast growing function, since $p(n)$ is much less than $\max\{n,k_0\}$, and so $p$ arises in very low levels of the Grzegorczyk hierarchy. Specifically, $p(n)$ is definable by recursions that do not need to consult numbers larger than $\max\{n,k_0\}$. So it seems that $p$ is in level $\cal{E}^1$, at the bottom of the hierarchy. Meanwhile, the range of $p$ is precisely $A$, as desired.</p> <p>(Note that we may slow the growth of $p$ down further, as much as desired, by requiring $n$ to code much more information, before giving the comparatively tiny output $k$.) </p> http://mathoverflow.net/questions/112337/recursively-enumerable-sets-as-range-sets-of-functions-in-grzegorczyk-hierarchy/112375#112375 Answer by Emil Jeřábek for Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy Emil Jeřábek 2012-11-14T12:30:38Z 2012-11-14T12:30:38Z <p>Gregorczyk hierarchy is not suitable to classify functions of very low complexity. The answer here is that for any r.e. set, you can take the enumerating function from pretty much as low a complexity class as you can imagine, as long as the class can compute anything nontrivial.</p> <p>For example, the function can be made <a href="http://en.wikipedia.org/wiki/AC0" rel="nofollow">uniform $\mathrm{AC}^0$</a>, in other words, computable by a logarithmic-time <a href="http://en.wikipedia.org/wiki/Alternating_Turing_machine" rel="nofollow">alternating</a> <a href="http://en.wikipedia.org/wiki/Random-access_Turing_machine" rel="nofollow">Turing machine</a> with constantly many alternations (actually, 1 or 2 alternations should be enough, but I would have to check).</p> <p>For another notion of simplicity, if $A$ is an r.e. set and $a_0$ is its least element, then $A$ is the range of a function $f\colon\mathbb N^k\to\mathbb N$ of the form $$f(\vec x)=\max\{p(\vec x),a_0\}$$ where $p$ is a polynomial with integer coefficients. (This follows from the MRDP theorem.)</p>