8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ In case you're interested, the last theorem in Grzegorczyk's paper Some classes of recursive functions, where the hierarchy is introduced, proves that $\mathcal{E}_0$ suffices, as is shown in the answer. $\endgroup$
    – user10891
    Feb 19, 2013 at 12:35

2 Answers 2

9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This was my guess (concerning a very low level), so I was expecting to be able to find some literature where the level is exactly determined. An alternative way to suspect that a low level would be enough is to think that all recursively enumerable sets are known to be diophantine (by the solution to Hilbert 10th problem), and it seems quite clear that polynomials are very low in the hierarchy. There is one small issue here and it is that diophantine definition provides a polynomial p with integer coefficients, so it is not a total function, but considering max{0,p} solves this issue. $\endgroup$
    – boumol
    Nov 14, 2012 at 2:49
  • $\begingroup$ I should have said, "the graph of this function is $\Delta_0$-definable and it is bounded by a primitive recursive function, so $p$ really is primitive recursive." There are very fast-growing functions with $\Delta_0$-definable graphs, but which are not primitive recursive. $\endgroup$ Nov 14, 2012 at 16:32
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.