How to prove that the exponential function is primitive recursive?

Question

I know that we can define the exponential by a function $f: \mathbb{N}^2 \rightarrow \mathbb{N}$ by letting:

$f(m,o) = 1$ and $f(m,n+1) = f_x(m^n,m)$ where $f_x$ is the multiplication function, which we know is recursive.

I would then let $g = s(z)$ and hence $g(n) = 1$ for each $n \in \mathbb{N}$ , and let $h = f_x$

However I am unsure where to go from here in order to complete a recursive definition for the exponential function. Could somebody please guide me into the approach to finish this proof?

Answer 1

• $f(x)=1$ - a constant function which is prim.rec. by definition.

• $h(0,x)=f(x)=1$.

• $h(S(y),x)=h(y,x).S(x)= g(y,h(y,x),x)$

So we can define $g(y,h(y,x),x) = h(y,x).S(x)$

Answer 2

According to Martin Davis Computability, complexity, and languages, and the way he solves this kind of problem. with the following steps, we can prove Exponential function is primitive recursive

$f(x,y) = x.y\ which\ f \ is \ prim.rec.\\ h(x,y) = x^y\\ h(x,0) = 1\\ h(x,y+1) = x^{y+1} = g(y,h(x,y),x)\\ g(x_1,x_2,x_3) = f(\bigcup^3_2(x_1,x_2,x_3),\bigcup^3_3(x_1,x_2,x_3))\\ \bigcup^n_i(x_1,...,x_n) = x_i (1\leq i \leq n) $

These steps show that we build the exponential function with initial functions so it's prim.rec.