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