1
$\begingroup$

The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and summation. Are the lower elementary functions closed under limited recursion? More precisely, if $g(k_0,\dots,k_{n-1})$, $h(k_0,\dots,k_{n+1})$, and $j(k_0,\dots,k_n)$ are lower elementary, is the function $f(k_0,\dots,k_n)$ defined below lower elementary? \begin{align*} f(k_0,\dots,k_{n-1},0) & = g(k_0,\dots,k_{n-1}),\\ f(k_0,\dots,k_{n-1},i+1) & = h(k_0,\dots,k_{n-1},i,f(k_0,\dots,k_{n-1},i)),\\ f(k_0,\dots,k_n) & \leqslant j(k_0,\dots,k_n). \end{align*}

This is an open question in the book Subrecursion by H.E. Rose (see p. 119, Open Problem 2), but I want to know whether it is still open now.

Another related open question in the book (see p. 121, Open Problem 3) is that in the definition of the lower elementary functions, whether we can replace the operation of summation by the operation of limited minimum (and at the same time add the multiplication function to the basic functions). Is this question still open now?

$\endgroup$
3
  • $\begingroup$ I'm pretty certain the answer is yes, this problem is still open, though it would take me some time to recall the details. The question might run into complexity-theoretic separations, cf. cstheory.stackexchange.com/questions/14664/… $\endgroup$
    – Siddharth
    Commented Nov 7, 2023 at 21:46
  • $\begingroup$ I thought about this many years ago and had some idea for how to attack this. It didn't go anywhere, but there might be something there. I'm happy to share. $\endgroup$
    – Siddharth
    Commented Nov 7, 2023 at 21:50
  • $\begingroup$ @Siddharth Thank you very much! $\endgroup$ Commented Nov 7, 2023 at 22:57

0

You must log in to answer this question.

Browse other questions tagged .