# Kleene normal form : elementary?

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

• 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. – user138530 Oct 25 '14 at 19:13
• @ChristianRemling Yes, I understand, but why being so vague as "primitive recursive" when you can be more accurate ? – Xoff Oct 25 '14 at 19:36
• Well, when it was first done, "elementary functions" weren't around. It seems an interesting question, though. – user138530 Oct 25 '14 at 19:38
• If you are still interested, Odifreddis Classical recursion theory includes a "improved normal form theorem" where both $T$ and $U$ are polynomial time computable. – 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.