Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy - MathOverflow

Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy

2012-11-14T01:57:04Z

It is well known that recursively enumerable sets 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).

On the other hand, primitive recursive functions can be presented in an stratified way using Grzegorczyk-hierarchy.

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.

Answer by Joel David Hamkins for Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy

2012-11-14T02:40:23Z

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ö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.

(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$.)

Answer by Emil Jeřábek for Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy

2012-11-14T12:30:38Z

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.

For example, the function can be made uniform $\mathrm{AC}^0$, in other words, computable by a logarithmic-time alternating Turing machine with constantly many alternations (actually, 1 or 2 alternations should be enough, but I would have to check).

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.)