The Kleene normal form explains there are primitive recursive functions $T$ (a predicate indeed) and $U$ such that for any computable function $\phi_n$, and for any $x\in\mathbb N$ : $$\phi_n(x)=U(\mu_yT(n,x,y)) $$

This is a very basic theorem of computability. I was wondering recently if $T$ and $U$ could be considered to be in the elementary function class.

As $U$ is very simple, and if the "program trace" $y$ is encoded with a simple method, I have no doubt that $U$ can be made elementary. Is there any reference to this fact ?

Even $T$ (a predicate that can be seen as a function into $\{0,1\}$) juste compute the program $\phi_n$ from $n$ and verify that $y$ seen as a list of actions is indeed coherent with $\phi_n$ and $x$. Even that seems to be very simple enough for elementary, if you consider that the encoding of $\phi_n$ into $n$ is simple. But I found nowhere the fact that $T$ can be elementary.

So, am I wrong into thinking that $T$ and $U$ can be considered elementary or did I miss well known references about that fact ?

Can it be considered even simpler (like lower elementary or even lower) ?

  • $\begingroup$ I don't know about your actual question, but the reason you can't find anything in the literature might be that it's really not very relevant here whether or not $T$ is elementary as you have the unbounded search for a computation $y$ coming up. $\endgroup$ – user138530 Oct 25 '14 at 19:13
  • $\begingroup$ @ChristianRemling Yes, I understand, but why being so vague as "primitive recursive" when you can be more accurate ? $\endgroup$ – Xoff Oct 25 '14 at 19:36
  • $\begingroup$ Well, when it was first done, "elementary functions" weren't around. It seems an interesting question, though. $\endgroup$ – user138530 Oct 25 '14 at 19:38
  • 1
    $\begingroup$ If you are still interested, Odifreddis Classical recursion theory includes a "improved normal form theorem" where both $T$ and $U$ are polynomial time computable. $\endgroup$ – user361949 Jan 10 '18 at 13:22

In this book, it proved there exists a Elementary function $C(a,b,c,d)$ such that for every $n$ and $k$: $$\phi_n^k(a_1,...,a_k)=r\Leftrightarrow\exists q\:C(n,<a_1,...,a_k>,r,q)=1$$ and $<a_1,...,a_k>=\prod_{i=0}^{k}P_i^{a_i+1}$ So we can define $U(n)=\pi_1(n)$, and $$T(n,x,y)\simeq C(n,x,\pi_1(y),y)$$ $<n,m>$, $\pi_1(n)$ and $\pi_2(n)$ are Cantor Pairing function and its decoding functions. So $T$ and $U$ can defined Elementary. But $T$ can defined in smaller class of function. Let $E$ be the smallest class of functions such that:

  1. $\left \{S(n),Z(n),+(n,m),*(n,m),=(n,m),P^i_k(n_1,...,n_k) \right \}\subseteq E$
  2. $\left \{ g(n_1,...,n_k),f_1(\vec{x}),...,f_k(\vec{x}) \right \}\subseteq E\Rightarrow g(f_1(\vec{x}),...,f_k(\vec{x}))\in E$
  3. $f(\vec{x},n)\in E\Rightarrow g(\vec{x},n)=\min y\leq n [f(\vec{x},y)=1]\in E$

Ii is easy to see that $<n,m>$, $\pi_1(n)$ and $\pi_2(n)$ are elements of $E$. Define $D^1_1(n)=\pi_2(n)$, then for every $k>1$ define $D^1_k(n)=\pi_2(D^1_{k-1}(n))$. Also Define $D^2_1(n)=\pi_1(n)$, then for every $k>1$ define $D^2_k(n)=\pi_1(D^1_{k-1}(n))$.

We know $C(n,x,\pi_1(y),y)$ is a recursive function, so by MRDP Theorem there exists two polynomial $t_1(n,x,y,r,q_1,...,q_u)$ and $t_2(n,x,y,r,q_1,...,q_u)$ with natural coefficients such that: $$C(n,x,r,y)=1\Leftrightarrow \exists q_1,...,q_u(t_1(n,x,r,y,q_1,...,q_u)=t_2(n,x,r,y,q_1,...,q_u))$$ Now define $$L(n,x,y)=t_1(n,x,D^2_1(y),D^2_2(y),D^2_3(y),...,D^2_{u+2}(y))$$ $$R(n,x,y)=t_2(n,x,D^2_1(y),D^2_2(y),D^2_3(y),...,D^2_{u+2}(y))$$ Therefore $$T(n,x,y)\simeq\:=(L(n,x,y),R(n,x,y))$$ and $U(n)=\pi_1(n)$. It is easy to check that $\phi_n(x)\simeq U(\mu_y T(n,x,y))$ Also $U$ and $T$ are in $E$ which is a smaller class then elementary functions.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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